2

このコードの時間計算量とそれを見つけるために使用されるロジックに混乱しています。

void doit(int N) {
    for (int k = 1; k < N; k *= 2) { <----I am guessing this runs O(logN)
           for (int j = 1; j < k; j += 1) { <------I am not sure how this one works.
       }
    }
}

私はすでにそれを手書きで解決しようとしました。しかし、私はまだそれを理解していません。

お時間をいただきありがとうございます。

編集：

それに別の質問を追加します。同じコンセプト、異なるフォーマット。

void doit(int N) {
    int j, k; //I ended up getting this answer to be O(n^(n/2)) But then I was stuck after that...is that even the right answer?
    for (k = 1; k < N / 2; k += 1) {
       for (j = k; j < 2 * k; j += 1) [
             x[j] = x[j-k] + x[j];//This doesn't really matter
        }
    }
}
4

1 に答える 1

8

全体の複雑さは実際にはO(N)

主張：それぞれについて、内部ループの反復kがあります。k（なぜそれが正しいのかを確信してください）

内側のループの合計反復回数をで表しT(N)、外側のループの数を。としますh。
これは、次のことを意味します。

T(N) = 1 + 2 + 4 + ... + 2^h 
     < 2 * 2^h               (1)
     = 2^(h+1)     
     = 2^(logN + 1)          (2)
     = 2^(log(2N))   
     = 2N

（1）和または等比数列 から（2）等比数列は、（あなたが言ったように）外側のループの反復があるためであることに
注意してください。2^(h+1) = 2^(logN + 1)h = logNlogN

于 2012-12-11T11:00:13.733 に答える