algorithm - While ループ 時間の複雑さ

Question

私はアルゴリズムの試験を受けています..そして、ループ時間の複雑さが少し良くありません:s私はそれの基本を理解し始めたばかりです..

私はこのwhileループを持っています

i=2
while (i<n)
{
   i=i*i
   x=x+1
}

解決策は次のようでなければならないと思います： （i） ステートメントを1回実行するたびに、k = 2 ⁱ
の場合 、2から2 ^{kまで実行されます..}

つまり 1+1+1+.. 、これは 1*2 ^{kを意味します}

そしてここから、私は続けることができません..

2番目の質問みんな..これらのいくつかをもっと練習できるサイトまたはsthをお勧めしてください..検索しましたが、見つかりませんでした:s

Answer 1

iが より小さい限り、ループが実行されnます。kつまり、 2 ^{2 k} < nを満たす必要があります。==> k = ログ₂ログ₂ n. したがって、ループは log ₂ log ₂ n 回反復し、各反復で 2 つの演算 (乗算と加算) を実行します。これらの演算にはO(1)時間がかかります。

==> ループの実行時間は log ₂ log ₂ n * O(1) ==> 総複雑度はO(loglogn).