嵌套循環的大O運行時間？

Question

你如何計算這段代碼的大O運行時效率？我的直覺告訴我這是O（n^3），但我不確定，因爲我不確定這些循環是獨立的還是依賴的。

for (i=1; i<=n; i++) 
    for (j=1; j<=n; j++) 
     for (k=1; k<=n; k++) 
      print ("%d %d %d/n", i, j, k); 

Answer 1

你的直覺是對的。你有三個嵌套for循環遍歷n，所以對於前n個循環中的每一個，你都會創建另外n個循環，每個循環又循環n個循環。因此O（n^3）。

編輯：想想這將如何發揮 - 我是第一個1，j 1，然後k循環1到n。只有在k經歷了整個循環後，j纔會增加到2，然後k再次經歷循環，依此類推。

Answer 2

是的，這個函數將會是O（N^3），因爲在每個循環內部運行N次迭代。
這些循環是而不是獨立，因爲它們是嵌套。

N * N * N = N^3