1

次のループを検討してください。

   for (i =1; i <= n; i++) {
     for (j = 1; j <= i; j++) {
        k = k + i + j; 
     } 
    }

外側のループは n 回実行されます。i= 1, 2, ... の場合、内側のループは 1 回、2 回、n 回実行されます。したがって、ループの時間計算量は

 T(n)=c+2c+3c+4c...nc
     =cn(n+1)/2
     =c/2(n^2)+c/2n
     =O(n^2)..

わかりましたので、時間の複雑さ、T（n）がc + 2c + 3cを決定する方法さえ理解していません。など..そして cn(n+1)/2? それはどこから来ましたか？

4

1 に答える 1

4

合計 1 + 2 + 3 + 4 + ... + n は n(n+1)/2 に等しく、これはガウス級数です。したがって、

c + 2c + 3c + ... + nc

= c(1 + 2 + 3 + ... + n)

= cn(n+1) / 2

この合計は、アルゴリズム分析でよく出てくるので、big-O 表記法を使用するときに知っておくと便利です。

それとも、総和がどこから来るのかという質問ですか？

お役に立てれば！

于 2013-10-07T07:08:17.397 に答える