java - log n の複雑さの外側ループを持つ 2 つの従属 for ループの複雑さ

Question

問題

このアルゴリズムの複雑さを計算します。

 for(i=n; i>1;i=i/2)
   for(j=i;j<n;j++){
         statement;
   }

このトピックについて以前に行ったこと:

最初のループは logn 回実行されます。2 番目のループは、i が n から始まり、外側のループの反復ごとに i/2 に変化するように ni 回実行されます。したがって、内側のループは次のように実行されます。

n-n                             0 times

n - n/2                        n/2 times

n - n/4                        3n/4 times

n - n/8                        7n/8 times

n - n/16                     15n/16 times

などなど

n - 1回

したがって、一般的な用語はn * ((2^n)-1)/(2^n)

現在、このシーケンスは算術的でも幾何学的でもありません。したがって、 の式はn/2 * (a+l)適用できません。この解決策をさらに進めるにはどうすればよいですか、それが間違っている場合は、正しい方法は何ですか.

注:n/2*(a+l)が適用される場合、結果の複雑さは次のようになります。-n/(2^n) = O(2^n).

Answer 1

まずは計算

A := (n - n)  + (n - n/2) + (n - n/4)  + ... + (n - n / 2^logn) = 
     log n * (n) - n * (1 + 1/2 + 1/4 + 1/8 + .... 1 / 2 ^ logn)
A > log n * (n)  - n * (1 + 1/2 + 1/4 + 1/8 + .... + 1 / 2^infity) =
     logn * n - n = n(logn - 2)
A < log n * (n)

ご覧のとおり、評価したい式を に割り当てましたA。最後の 2 つの不等式から、アルゴリズムの複雑さは次のようになります。thetha(n logn)

ここでは、よく知られている次の等比数列を使用しました。(1 + 1/2 + 1/4 + .....) = 2

Answer 2

ステートメントが実行される正確な回数は nlogn - 2n(1-1/2^logn) です。