2番目のループの複雑さはどのように計算されますか？

Question

は、このためのPythonでループのために：

for(int a = 1 ; a < N ; a*=2) 
     for(int b =1 ; b <N ; b++) 

私はコードがO(n*log(n))で完了知っているが、ループがある場合：

For(int a = 1 ; a <N ; a*=2) 
    for(int b = 1 ; b < a ; b++) 

することは、それはまだO(n*log(n))で完了でしょうか？

Answer 1

はい（いいえ）です。 Big Oの定義に厳密に従えば、2番目のアルゴリズムはO(n*log(n))ですが、より良い結び付きを持っていることがわかります。

最初に、最初のループのアイデアを見てみましょう。各ループ反復を計算単位と呼びますと、合計計算量はsum(sum(1 from 0 to N) from 0 to log2(N))であり、ちょうどN log2(N)（たぶん1つ外れている）と言えるでしょう。この結果は、ループの最初のセットがO(N log(N))であることを示しています。

今度は2番目のセットです。上記の手順を繰り返すと、sum(sum(1 from 0 to *a*) from 0 to log2(N)) = (log2(2 N) log2(4 N)) <= k [log(N)]^2となるので、2番目のアルゴリズムはO(log^2(N))（ポリログと呼ばれます）です。

k N log(N)（いくつかのkの場合）は依然として第2のアルゴリズムの上限ですので、厳密にはまだO(N log(N)です。ここ

ランタイムの期待成長のイメージである：

赤、ループの最初のセットであり、緑色は、ループの第二のセットであり、青色は2N log(N)あります。