5 
for(i=0; i<n; i++)
{
    a[i]=0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            a=3;
        }
    }
}

これは、3 重にネストされたループです。私の本には、実行時間は次のように記載されています: O(N) + O(N^2) = O(N^2)

O(N^3)じゃないの？3 つのループはすべて相互に依存しています。N*N*N 回実行されます。

4

3 に答える 3

6

これは、比較中にループ#1とループ#2が同じカウント変数を使用しているためです。i

を使用した 2 番目のループの最後でi、 の値iはnであり、外側のループからも抜け出します。そこでは 1 つのループが完全に冗長です。

#include <stdio.h>
int main(){
    int x = 0;
    int n = 20;
    int i, j;
    for(i=0; i<n; i++) //this loop runs once
    {
        for(i=0; i<n; i++) //this loop runs n times
        {
            for(j=0; j<n; j++) //this loop also runs n times
            {
                x++;
            }
        }
    }
    printf("%d", x);
}

O(N^2)全体が動いているのは時間内です。

例

于 2013-02-01T21:55:16.247 に答える
1

それらがあなたの本の間違いだとは思いません。コードをもっと深く調べる必要があります。最初の 2 つのループはループに同じ変数を使用するため、次のようになります。

最初のブラケットの後、i は 0 に等しくなり、2 番目のループに進みます。2 番目のループが終了すると、両方のループが条件 i を使用するため、最初のループが終了します。

実際には、O(N) がどこから来たのかわかりませんが、グローバルな複雑さは O(N^2) である必要があります

于 2013-02-01T21:56:53.813 に答える
1

変数 i が内側のループで再利用され、n^2 になるため、これは n^3 ではありません。ただし、本のどこでO(n)が得られるかはわかりません。

于 2013-02-01T21:57:33.773 に答える