big-o - 実行されていない場合の時間の複雑さ

Question

プログラムの次のセグメントの「最良のケース」の時間計算量は?

n=0
sum=0
input(x)
while x!=-999 do
  n=n+1
  sum=sum+x
  input(x)
end {while}
mean=sum/n

ユーザーが初めて「-999」と入力した場合、「最良のケース」は O(1) になる可能性があります注: ユーザーが初めて -999 と入力した場合、「平均」は 0/0 になり、関数の結果は未定義になります

score 0 · Accepted Answer

最悪のケースは無限大です。つまり、このプログラムは決して停止しません。「アルゴリズム」の定義によっては有限の入力セットが必要な場合もあれば、特定の数の計算ステップの前に終了する必要がある場合もあるため、アルゴリズムとは呼びません。

つまりO()、ここでは適用できません。

score -1 · Accepted Answer

アルゴリズムの複雑さは通常、ある種のデータに関連して定義されます。あなたの場合のように、それは入力データにすることができます。

データが手動で入力されるのではなく、アプリ内の配列で提供されることをしばらく想像してみてください。その場合、複雑さはどうなりますか？

この場合、処理される数値の量は N であり、ループは N ごとに 1 回実行されるため、複雑さは O(N) であると想定できます。

2 に答える 2