このアルゴリズムの実行時間が大きい

Question

アルゴリズムの複雑さを分析するのは難しいです。このアルゴリズムの例を取ると、実行時をO表記でどのように見つけることができますか？

loop(n) 
i = 1 
while i ≤ n 
    j = 1 
    while j ≤ i 
     j = 2 ∗ j 
    i = i + 1 

Answer 1

あなたの投稿からは、O表記の意味を知っていますが、それを適用する上でいくつかの問題があります。ここでは、この単純な例では、ループが実行された回数（入力サイズに依存する）を決定するだけで十分です。最終的な価値を得るには、それを結合する必要があります。

最初の手順：ループごとの実行時間を分析します。 （非ループまたは再帰文O（1）。き）

while(i<=n) 
... 
i=i+1 

こうしてO（N）

内側ループ 一方（J < = I） J = J、n回実行されます。 * 2

はi/2回実行されますが、外側ループからnだけ制限されます。これはO（n）です。

内側ループは、外側ループでO（N）であるとして、あなたが増殖する必要がasymptitics、即ち、N * N => O（N^2）

このようなコードを与え

Answer 2

、それはしばしば内側から作業するのに役立ちます。

このループは、jがiより大きくなるまで繰り返し倍増することによって機能します。あなたがiを超える前に倍にすることができる回数はΘ（log i）なので、内側ループが実行されるたびにΘ（log i）の仕事があります。

仕事がログ1 + 2 +ログ

なるようにアウターループは、1からnまでカウントアップ... + N

=ログ* 2（1 *ログ.. 。* n）（対数の性質を使って）。

=ログ（N！）

= Θ（N Nを記録）。

最後のステップはStirling's approximationです。

全体として、時間の複雑さはΘ（n log n）です。