此僞代碼的運行時間

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)