time - この疑似コードの実行時間

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

次のように考えることができます。

ループの途中で

 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

2番目のものも実行されます

n/2 times(n-n/2)

そして3番目のものも実行されます

n/2 times (1 to n/2)

したがって、この場合、n/2*n/2*n/2これは与え(n^3)/8ています。

O(n^3)

Answer 2

最初の考え: n*n*logN だと思いますか?

編集: 最も内側の k は 1 にヒットし、次に 1 と 2 にヒットし、次に 1 と 2 と 3 にヒットします...これは線形です...特定の間隔で停止します。線形なので、当然 N... と言うでしょう。

で、考えてみたらO(n^3)？