時間/アルゴリズムの複雑さ - 製品パターンによってインクリメントされた状態でネストされた

Question

アルゴリズムの時間複雑さを測定しようとしています。 アルゴリズムは1から始まり、しばらくしています。しかし、問題は、私は製品を増やすことです。 私は大きなOを使用していない、指示を数えるだけです。 パターンを見つけようとしています。この例では

、私は右のそれをやった：

i = 1; -> // 1 execution 
while(i<=n) { // n+1 
    j =1; // n 
while(j<=n) { // n² 
.... 
    j = j + 1; // n² * 2 
} 
i = i + 1; // 2n 
} 

[OK]をクリックします。私は合計する必要があります。

しかし、問題は、このケースである：パターン何

When n is 2 ---> The println run 1 time. 
When n is 3 ---> The println run 2 times. 
When n is 4 ---> The println run 2 times. 
When n is 5 ---> The println run 3 times. 
When n is 6 ---> The println run 3 times. 

：

i = 1; // 1 execution 
while(i<n) { // n execution? 
System.out.println("*"); // n execution?    
i = i * 2; // n execution???? 
}  

私はあまりにも多くの方法をテストしてみましたか？

私はBig O表記にしたくありません。

Answer 1

我々はそうのは、ループがm回、それらを実行されている間、我々はm<=log(n)がそう、それはO(log(n))だ意味2^m<=nを持っていることを言わせて各反復で2によりiを分割するので複雑さがO(log(n))です。