1

たとえば、試験の準備を簡単に行うことができます。

f(x) = 5x<sup>2</sup> + 4x * log(x) + 2

大きなOはO(x<sup>2</sup> + x * log(x))、5や4などの非対数係数を考慮に入れる必要がありますか？

同様に、このコードを検討してください

for (int i = 0; i < block.length; i++)
    for (int j = 0; j < block.length;  j++)
        for (int k = 0; k < 5; k++)
             g(); //assume worst case time performance of g() is O(1)

では、大きなOはO（5n 2）またはO（n 2）でしょうか？

4

2 に答える 2

3

の複雑さf(x) = 5x^2 + 4xlogx + 2はO(x^2)

O(g(x) + k(x)) = max(O(g(x), k(x))
// and O(X^2) > O(xlogx)

//additionally coeffs are disregarded
O(c*g(x)) = O(g(x))

したがって、合計がある場合は、1日の終わりに最大の複雑さを選択するだけで、nが無限大になると、最大のコンポーネントが最大の計算負荷を与えます。また、何が起こるかを大まかに見積もろうとするので、係数があるかどうかは関係ありません。

他のサンプルについては、以下の理由を参照してください

for (int i = 0; i < block.length; i++)
    for (int j = 0; j < block.length;  j++)
        for (int k = 0; k < 5; k++)
             g(); //assume worst case time performance of g() is O(1)

最初にループを合計に変換し、右から左に合計を計算します

Sum (i=0,n)
    Sum(j=0, n)
        Sum(k=0, k=5)
            1

1から5までのO（1）のカウンターはまだO（1）です。係数を無視することを忘れないでください

Sum(k=0, k=5) 1 = O(5k) = O(1)

したがって、O（1）の関数をn回カウントする中間の合計になります。これにより、O（n）の複雑さが得られます。

Sum(j=0, n) 1 = O(n)

最後に、左端の合計に到達し、 nn回カウントすることに注意してください。つまり、またはn+n+n...に等しいn*nn^2

Sum (i=0,n) n = O(n^2)

したがって、最終的な答えはO（n ^ 2）です。

于 2012-06-21T12:10:43.850 に答える
0

O(x**2)なぜなら：

lim n^2 if (x->8) = 8

lim 5n^2 if (x->8) = 8

8 is infinity

しかし、いくつかの式の合計がある場合は、最も急速に成長する関数を理解する必要があります。それはあなたの質問に対する答えになります。

式の前にある他の定数でも同じ答えが得られます。その場合、漸近解析 を使用する必要があります。アドバイスを提供する場合があります。必要ないくつかの機能の合計に直面した場合：

  • コンポーネントの式を分解します
  • 各要素のプロットを想像してください
  • 無限を超えない最も急速に成長している要素を理解しました

この要素はあなたに答えを与えるでしょう

于 2012-06-21T12:11:11.727 に答える