2

コードは次のとおりです。

int Outcome = 0;  
for (int i = 0; i < N; i++)  
    for (int j = i+2; j = 0; j--)  
        Outcome += i*j;

これが私の分析です。最初の行は割り当てステートメントであるため、これには正確に 1 つの時間単位 O(1) が必要です。2 行目の内訳は、1 + N + N = 2N + 2 です。3 行目では、ループの内容が 1 回の操作であるため、ループとそのブロックは i+1 回の操作を実行します。これもネストされた for ループです。最後に、4 行目は実行にちょうど 1 時間単位かかります。したがって、N に関するこのコードの Big-Oh 表記は O(N 2 ) です。

4

2 に答える 2

1

正確には：あなたが言うように、4行目は1つの操作です。特定の に対してi、内側のループ時間を実行しますi+3。したがって、操作の合計数は

sum(0 <= i <= N-1 : i+3) 
    = 3N + sum(0 <= i <= N-1 : i) 
    = 3N + N(N-1) / 2
    = N^2/2 + 5N/2
    = O(N^2)
于 2013-05-25T23:17:54.007 に答える