此伪代码的运行时间

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和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)