与えられたスニペットの時間の複雑さは何ですか？

Question

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

時間の複雑さは「n」で何ですか？

Answer 1

最も内側のループは明らかにj回実行されます。それは1時間単位の価値の操作が含まれていると仮定すると、これは以下のようになります。

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

注：これは、最も内側のブロックの演算のみをカウントします。ループを実行するのに必要な操作は無視されます。しかし、それらを含めると、時間の複雑さは同じであることがわかります。