0

フラグメントは次のとおりです。

sum1=0;
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        sum1++
sum2=0
    for(k=1;k<=n;k*=2)
      for(j=1;j<=k;j++)
        sum2++

以下が答えです。

2 つの割り当てステートメント – O(1) 各 1 番目のネストされたループ – O(n2) 2 番目のネストされたループ – O(n) コード フラグメントの実行時間の複雑さ = O(1) + O(n^2) + O(1) + O (n) = O(n2)

しかし、これが私がそれをどのように解決したかです：

2 つの割り当て:- O(1)。最初のネストされたループ: O(n*n)=O(n^2) 2 番目のネストされたループ:

外側のループは n 回実行されます。これで、内側のループが (1+2+3+.....+(n-1)+n) 回実行され、n(n+1)/2 =O(n ^2)

総実行時間 = O(n^2)+O(n^2)+O(1)=O(n^2)

そして、はい、いくつかの調査を行ったところ、次のことがわかりました。

ループでは、反復ごとにインデックスが増加する量だけジャンプする場合、シーケンスの複雑さはログ n になります。

その場合、2 番目のループの複雑さは (n-1)/2*logn になると思います...これは O(n*log n) に等しくなります。

O(n)..O(n^2) または O(nlogn)..

助けてください

4

1 に答える 1

0

あなた k が毎回 2 倍になったので。あなたの計算は正しくありません。(1+2+4+....n/2+n) である必要があります。

     for(k=1;k<=n;k*=2)

したがって、O(nlogn) は正しいです。

于 2012-05-08T11:38:16.677 に答える