このdo-whileループの時間複雑度はどのくらいですか？

Question

int count=0; 
do 
{ 
count++; 
n=n/2; 
} while (n>1); 

nの番号を差し込み、それぞれの基本操作をプロットしても、パターンが表示されない場合があります。前もって感謝します！

編集：私はここで最悪の場合があります。

Answer 1

最初のステップはnを2で除算することです。だからn/2が得られます。今度は、2で再度割ります。n/2 > 1なら、n/4になります。 n/4 > 1をもう一度やり直してn/8とすれば、それはn/(2^3) ...と書いてください。n/(2^3) > 1あなたはもう一度やり直してください。n/(2^4) ...だから、k回するとn/(2^k)となります。 kを計算する方法n/(2^k) ≤ 1を得るには？簡単：

n/(2^k) ≤ 1 
n ≤ 2^k 
ln(n) ≤ k 

だから、あなたのアルゴリズムは、ループを終了するO(ln(n))反復を必要とします。

コードでは、kはcountです。