給定片段的時間複雜度是多少？

Question

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

「n」的時間複雜度是多少？

Answer 1

最內圈將明顯運行j次。假設它包含價值100個單位時間的操作，這將是：

T_inner(j) = j 

環路中間將運行i倍，即

T_middle(i) = Sum {j from 1 to i} T_inner(j) 
      = Sum {j from 1 to i} j 
      = i/2 * (1 + i) 

最後：

T_outer(n) = Sum {i from 1 to n} T_middle(i) 
      = Sum {i from 1 to n} (i/2 * (1 + i)) 
      = 1/6 * n * (1 + n) * (2 + n) 
      = 1/6 n^3 + 1/2 n^2 + 1/3 n 

這顯然是O(n^3)。

注意：這隻會計算最內側塊中的操作。它忽略了執行循環所需的操作。但是如果你包含這些，你會發現時間複雜度是一樣的。