アルゴリズムの時間複雑度解の説明が必要

Question

ソフトウェアエンジニアリングクラスの紹介は、時間の複雑さに打ち勝ち、特定のアルゴリズムを分析する方法を学習しています。私は彼らが彼らの解決方法を見ているのが見苦しくて誰かがそれを説明できることを望んでいました。

void foo(int N) { 
    int k = 1; 
    while (k < N * N) { 
     k = k * 2; 
    } 
} 

彼らのソリューションは、この機能のビッグ-Oは、O（logN個）であるということである[私はここでログイン理解ベース2である]

私は何回それが希望考えてこれを解決しようとしましたNにランダムな値を代入して反復し、パターンを見つけることができませんでした。

Answer 1

kが毎回2のファクタで増加しているという事実は、アルゴリズムをlogNとするものです。実際には、それはlog(N^2)ですが、対数のプロパティを使用して2log(N)に簡略化してから、Nが無限に近づくので、になるように制限を取って2を削除してください。

したがって、時間の複雑さはO(logN)です。

EDIT：さらに、kが1で始まり、kがより大きいかN * Nに等しい場合、プログラムが終了することがわかります。 log(N^2)を利用すると、プログラムが実行される回数を知ることができます。その際、log(N^2)の上限をとって、終了値kを決定することもできます。

編集例：N = 10があります。Nの正方形は100です。したがって、kは、100以上の2の累乗（128）まで増加します。

Answer 2

高校代数を使用してください。 pの反復の後にkの値は2^pです。 （これは簡単にチェックできます）k >= N^2のとき、ループは実行を停止します。代入すると、ループは

2^p >= N^2 

今すぐ解決したときに停止します。

log_2(2^p) >= log(N^2) 
p >= 2 log(N) 

だからループが 2 log(N)の反復に非常に近くで停止します。これはO（log（N））です。

オペランドのサイズに一定の制限がある場合にのみ、乗算が一定時間であることを指摘することによって、先生に任せてもよいでしょう。このような制限がない場合、問題は乗算の漸近的挙動にも依存する。

なお、O（log N）は対数のすべての基底で同じです。ベースは定数の係数だけでログの値を変更し、big-Oは定数を無視します。