如何找到 3 个嵌套循环的复杂性

Question

我有以下 for 循环：

for i = 1 to n
  for j = i to n
    for k = i to j+1

我认为第一个和第二个循环的复杂度分别是 n 和 n(n+1)/2 但我真的很困惑如何计算第三个循环的复杂度。当初始值和最终值都依赖于之前的循环时，我该如何找到它的复杂性？

Answer 1

首先用求和替换每个循环。做一些数学...

PS: 这些可以帮助：