0

私がこのようなループ構造を持っている場合

for(int i=1; i<n;i++)
   for(int j=1; j<n;j++);

O（n 2）またはO（0）？

ループ内が次の場合であると想定します。

for(int i=1; i<n;i++)
   for(int j=1; j<n;j++)
      if(a==b) do();

そして、do（）がO（1）であると仮定して、最良のケースと最悪のケースを知りたいです。

最悪： O（n 2）ifステートメントは常にtrue

最良： O（0）ifステートメントは常にfalse

あれは正しいですか？

4

4 に答える 4

4

私たちの文脈では、O（0）のようなものはありません。最適化されていれば、事実上定数時間（O（1））になります。

そうかどうかについては、違います。書かれているように、それはまだO（N ^ネストされたループの数）です。オプティマイザーはコードを完全に削除する可能性がありますが、「最悪の場合」はコードを削除せず、CPUがその車輪を回転させていることです。それらのループを介して。

于 2013-02-25T21:25:22.327 に答える
3

n = 3とすると、最初のループでは次のようになります。

i = 1
i < 3 => true
  j = 1
  j < 3 => true
  j++
  j < 3 => true
  j++
  j < 3 => false
i++
i < 3 => true
  j = 1
...

ループ内に他のコードがあるかどうかに関係なく、これらすべての増分とチェックを実行する必要があります。

したがって、最良+最悪の場合O（n 2）になります。

もちろん、オプティマイザーがループ内で何も起こらないことを確認し、それを完全に削除する可能性があります。しかし、ループの最良のケースがO（1）であると言うことは、技術的には正しいとしても、おそらく間違っていると見なされます。

于 2013-02-25T21:27:51.980 に答える
1

それらはO（n ^ 2）ですが、実際には、ループ自体のコストが大きい場合にのみ関係します。

于 2013-02-25T21:27:48.933 に答える
1 
for(int i=1; i<n;i++)
    for(int j=1; j<n;j++);

O（n ^ 2）、何もしなくてもカウンターは更新されます。

したがって、2番目の質問では、最良と最悪の両方がO（n ^ 2）です。

于 2013-02-25T21:29:08.707 に答える