6

4n ^ 2 + 7nの移動で達成するアルゴリズムがある場合、そのOは何ですか？O（4n ^ 2）？O（n ^ 2）？

7nがカットオフされていることは知っていますが、n^2係数を維持する必要があるかどうかはわかりません。

ありがとう

4

6 に答える 6

14

質問は実際には「次数」であるため、係数を削除する必要があります。これは、線形、指数、対数などとして特徴付けようとします。つまり、nが非常に大きい場合、係数はほとんど重要ではありません。

これは、+ 7nを削除する理由も説明します。これは、nが非常に大きい場合、その項は最終的な答えにとって比較的重要ではないためです。微積分に精通している場合は、lim n-> inf（4 * n ^ 2 + 7n）〜= lim n-> inf（4 * n ^ 2）〜= lim n-> inf（n ^ 2）と言うかもしれません。

これはグラフィカルな意味で考えることもできます...つまり、nの値がどんどん大きくなるように関数4n ^ 2 + 7nをグラフ化すると、数学者は「n^2のように見える」と言うかもしれません。確かに、これは厳密なステートメントではないので、かなりリベラルな数学者でなければなりませんが、それは基本的にO（...）が伝えようとしていることです。

于 2010-01-17T17:21:15.783 に答える
11

係数はBigO表記には関係がないため、O（n 2）にすぎません。 ウィキペディアが説明しているように：

[...]項n3またはn2を含む式など、他の式の順序と比較すると、係数は無関係になります。

于 2010-01-17T17:20:18.217 に答える
9

アルゴリズムの複雑さについて読んだり書いたりする人は誰でも、ランダウの記号と漸近表記が何であるかを正確に知っている必要があります。

（多くの）単純化するために、fとgを2つの関数f : N -> Nととしg : N -> Nます。すべてのに対して、のようなf is O(g)定数がある場合にのみ、と言います。つまり、より非公式には、の大きな値から始めて、すべての値がの倍数よりも小さくなります（つまり、より速く成長します）。M > 0|f(n)| < M|g(n)|n > Mnf(n)g(n)g f

その定義は同等です

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

それでは、とを取りf(n) = 4n^2 + 7n、g(n) = n^2証明してみましょうf is O(g)（省略し{n -> +oo}ます）：

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

これはM、、、n > M ==> |f(n)| < M|g(n)|したがってf is O(g)。

したがって、技術的には、、などと言うのが正しいので、と4n^2 + 7n is O(4n^2)言うのは正しいです。しかし、意味のあるものにするために、私たちは下限に関心があります。したがって、およびの場合、これははるかに制限的であるため、私たちはそれを知ることにもっと興味があります。4n^2 + 7n is O(n^3)4n^2 + 7n is O(e^n)f is O(e^n)f is O(n^2)f is O(n^2)

非常に重要な注意

アルゴリズムを選択するときに非常に重要なことは、big-O表記が漸近的なケースを指すことを理解することです。つまり、非常に想像を絶する巨大な入力を考慮すると、既知の宇宙で利用可能な計算能力をはるかに超える可能性があります（つまり、無限）入力セット。数学的には）で表され{n -> +oo}ます。

実際の使用（つまり、それほど大きな入力ではない）の場合、アルゴリズムを選択するときは、確かに、候補アルゴリズムのbig-O表記を観察しますが、選択したアルゴリズムが（期待される）に適切に適合している（そしてパフォーマンスが優れている）ことを確認する必要があります）入力。

最後に、通常、パフォーマンスの高いアルゴリズムは、理解して適切に実装することがより困難です。アルゴリズムを選択するときは、この事実も考慮する必要があります（つまり、このアルゴリズムの実装のデバッグと修正に費やす時間は、別のアルゴリズムで待機する時間よりもかなり長く、big-O表記が悪いですか？。もしそうなら、全体的な解決策がより効率的であるため、より単純で効率の悪いアルゴリズムを検討する必要があります）。

于 2010-01-17T17:36:50.303 に答える
6

O（n ^ 2）です。一定の要因は「Oに移動」します。これが支配的な指数であるため、最大の指数のみを保持します。また、異なるアルゴリズムを比較する場合、係数が非常に大きい場合でも、指数が大きい場合（nが十分に大きい場合）よりも総数が少なくなるため、係数を省略できます。

于 2010-01-17T17:20:05.350 に答える
4

次のようなステートメント

4n² + 7n = O(n²)

ある定数乗数cの場合、式cn²は最終的にを追い越すことを意味し4n² + 7nます。係数をそこに残すことは技術的に正しくありません。前者の定数は後者の定数に置き換えることができるため、まったく同じことO(n²)を意味します。ただし、そのようなことはあまり明確ではなく、誤解を招く可能性があり、間違いなく非標準です。O(4n²)cc/4

于 2010-01-17T17:35:43.110 に答える
1

数学的に言えば、O（4n²）と書くでしょう。これは、アルゴリズムの複雑度関数が正の無限に対してn->4n²として動作することを意味します。

しかし、コンピュータサイエンス/アルゴリズムでは、アルゴリズムを分類するのに十分なO（n²）のみを記述します。

于 2010-01-17T17:26:19.547 に答える