algorithm - ネストされたforループが繰り返しカウンターを2倍にするこのコードの複雑さは何ですか？

Question

『 Programming Interviews Exposed』という本では、以下のプログラムの複雑さはO（N）であると書かれていますが、これがどのように可能かわかりません。誰かがこれがなぜであるか説明できますか？

int var = 2;
for (int i = 0; i < N; i++) {
   for (int j = i+1; j < N; j *= 2) {
      var += var;
   }
}

Answer 1

それを確認するには、少し数学が必要です。内側のループは 2Θ(1 + log [N/(i+1)])回反復します ( は1 +for から必要i >= N/2で[N/(i+1)] = 1あり、対数は 0 ですが、ループは 1 回反復します)。少なくとも と同じ大きさになるまでj値を取得し、(i+1)*2^kN

(i+1)*2^k >= N <=> 2^k >= N/(i+1) <=> k >= log_2 (N/(i+1))

数学的な除算を使用します。したがって、更新j *= 2は回呼び出されceiling(log_2 (N/(i+1)))、条件は回チェックされます1 + ceiling(log_2 (N/(i+1)))。したがって、総作業量を書くことができます

N-1                                   N
 ∑ (1 + log (N/(i+1)) = N + N*log N - ∑ log j
i=0                                  j=1
                      = N + N*log N - log N!

さて、スターリングの公式が教えてくれます

log N! = N*log N - N + O(log N)

したがって、完了した作業の合計は確かにO(N)です。

Answer 2

@Daniel Fischerの答えは正しいです。

このアルゴリズムの正確な実行時間は次のとおりです。

つまり: