performance - ネストされた for ループの実行時間の計算

Question

このループの最悪の場合の実行時間を計算するにはどうすればよいですか?

for(int i=1 ; i * i < n ; i*=2)

{
     //do something
}

Answer 1

それを築き上げましょう--

初め：

for (int i = 1; i < n; i *= 2) --> log(n)

それで：

for (int i = 1; i * i < n; i ++) --> sqrt(n)

したがって、あなたのループは log(sqrt(n)) の影響を受けるようです

Answer 2

なぜならi = 0、i*=2はまだ= 0であり、これは永遠に実行されるからですn > 0