time - 此伪代码的运行时间

Question

1 for i = 1 to n
2    for j = i to n
3       for k = 1 to j
4          statements which take O(1) time

请帮我找出以下代码段的时间复杂度。是 O(n^3) 吗？我认为不是因为第 3 行取决于第 2 行。我真的很难过，我需要你的帮助。请提供解决方案。非常感谢！

Answer 1

最初的想法：我认为是 n*n*logN？

编辑：最里面的 k 将击中 1，然后下一次，1 和 2，然后下一次，1 和 2 和 3 ......这是线性的......它只是在一定的间隔处停止。由于它是线性的，我自然会说 N ...

那么，想了想，O(n^3)？

Answer 2

你可以这样想：

在循环中取一半时

 i = n/2
for i = 1 to n
    for j = i to n
       for k = 1 to j
          statements which take O(1) time

第一个正在运行

n/2 times

第二个也运行

n/2 times(n-n/2)

第三个也运行

n/2 times (1 to n/2)

因此，在这种情况下，哪个n/2*n/2*n/2是给予(n^3)/8

O(n^3)