-1

次のプログラムの効率はどうなるでしょうか。これは、有限の番号に対して実行される for ループです。の回。

for(int i = 0; i < 10; i++ )
{
   //do something here, no more loops though.
}

それで、効率はどうあるべきですか。O(1) または O(n) ?

4

4 に答える 4

9

forそれは、ループの内容に完全に依存します。また、計算の複雑さは通常、入力のサイズで測定されますn。入力のサイズを直接的または間接的にモデル化、表現、またはエンコードする例は何も見られません。定数だけがあり10ます。

また、計算の複雑さを分析すると、予想外の驚くべき結果が得られることもありますが、正しい用語は「Big Oh」ではなくBig -Oです。

于 2013-05-17T10:25:39.773 に答える
4

計算への特定の入力に関する複雑さについてのみ話すことができます。作業を行う必要がある「何か」が 10 個あるために 10 回ループしている場合、複雑さはそれらの何かに関して O(N) になります。何かの数に関係なく10回ループする必要があるだけで、ループ内の処理時間は何かの数によって変化しない場合、それらに関する複雑さはO(1)です。次数が 1 より大きい「何か」がない場合は、ループを O(1) と記述しても問題ありません。

さらにとりとめのない議論のビット...

O(N) は、N の値が大きい場合、一定の時間に N の関数 (入力内の何かの数) を加えたものによって、作業が完了するまでにかかる時間を合理的に概算できることを示します。

  • O(N) は、時間が c + xN であることを示します。ここで、c は固定オーバーヘッドであり、x は何かごとの処理時間です。
  • O(log 2 N) は時間が c + x(log 2 N) であることを示します。
  • O(N 2 ) は時間が c + x(N 2 ) であることを示します。
  • O(N!) は時間が c + x(N!) であることを示します
  • O(N N ) は時間が c + x(N N )であることを示します
  • 等..

繰り返しますが、あなたの例では入力の数について言及されておらず、ループの反復は修正されています。10 個の入力「何か」があってもO(1) だと言いたくなる気持ちはわかりますが、次のことを考慮してください。任意の数の入力を処理できる関数がある場合は、それを自分の正確に 10 個の入力とそれをハードコードしたアプリケーションで、関数のパフォーマンス特性を明らかに変更していない - N 入力曲線の時間曲線上の 1 点にロックしただけであり、大きな複雑さはありません。ハードコーディング前に有効だったものは、その後も有効である必要があります。ただし、N of 10 は少量であり、O(N N) 定数 c と x は、全体的なパフォーマンスを記述する上で、N の巨大な値の場合よりもはるかに重要です (一般に、big-O 表記の変更は、c や x の変更よりもパフォーマンスにはるかに大きな影響を与えます。つまり、もちろん、Big-O 分析を行うことの要点です)。

于 2013-05-17T10:32:20.697 に答える
2

確かに O(1) です。ここでは、n に直線的に依存するものは何もないためです。

編集: ループ本体に、Big O 用語で複雑な O(P(n)) を持つ複雑なアクションを含めるようにします。

反復回数が定数 C の場合、ループの複雑さは O(C * P(n)) = O(P(n)) になります。

そうでなければ、今度は反復回数を Q(n) とし、n に依存します。ループの複雑さを O(Q(n) * P(n)) にします。

反復回数が一定の場合、ループ全体の複雑さは変わらないと言いたいだけです。

于 2013-05-17T10:26:21.197 に答える
1

nBig O 表記の は、入力サイズを示します。forループ内で何が起こっているのかわからないため、何が複雑なのかわかりません。たとえば、入力サイズによっては、再帰呼び出しがあるのではないでしょうか? この例では、全体はO(n)次のとおりです。

void f(int n) // input size = n
{
    for (int i = 0; i < 10; i++ )
    {
        //do something here, no more loops though.
        g(n); // O(n)
    }
}

void g(int n)
{
    if (n > 0)
    {
        g(n - 1);
    }
}
于 2013-05-17T10:28:08.603 に答える