コードスニペットの実行時間は何ですか

Question

次のコードスニペットの実行時の複雑さを見つけるのに助けになる人がいますか？

上記のコードスニペットの実行時の複雑さを見つけるのを手伝ってください。

Answer 1

あなたのコードには、特に最初のwhileループに問題があると思います。 while loop文の手段の後にセミコロンを持つ

while (i <= n); 

は、ループ文の下に記載がありません。ループ変数iを更新していないため、このwhileループは無限に実行されます。

誤ってセミコロンを入力した場合は、whileループの時間の複雑さをO(n)とするn回を繰り返します。

しかし、ループ変数jを値を半分に減らすので、2番目のwhileループの時間複雑度はO(log n)です。

while (j > 0) 
    y := x/(2*j); 
    j = j /2; 
    i = 2 *i; 

ので、トータルではしばらくの間ループの両方を考慮した場合、その後、合計時間の複雑さはO(n)と同等ですO(n + log n)でなければなりません。