O（n）vs O（n^2）

Question

私は最近構造クラスのデータに対して2つのテストを終了しましたが、O（n）vs O（n^2）間違って2回。私は問題を理解するのに役立つかどうか疑問に思っていた。問題は次のとおりです。

アルゴリズムAに実行時O（n^2）があり、アルゴリズムBに実行時O（n）があるとします。 n = 17のとき、これらの2つのアルゴリズムのランタイムについては何が言えますか？

A）私たちは、ときに、特定のランタイムについては何も言うことができないのn = 17

b）のアルゴリズムAがC

アルゴリズムBよりもはるかに高速に実行されます）アルゴリズムAは、アルゴリズムB

よりもはるかに遅いが実行されます

どちらのテストでも、私はhttps://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functionsに基づいてCに答えました。私はBが提供されたリンクに基づいて意味がないことを知っていた。今、私はそのA.を考え始めています。なぜなら、nは小さいからです。それが事実なら、私は、nが十分に大きくてCが真であるときはいつ疑問に思うのですか？

Answer 1

答えはa）：大きなO表記を与えられた特定の番号に対して実際には何も言えません。

c：Bのカウンタ例は1000 * n（= O（n））の実行時間を持ち、Aはn^2の実行時間を持ちます。

Answer 2

実際には2つの問題があります。

最初に述べたものがあります。成長の秩序は漸近的である。彼らはただ機能が何らかの方法で制限され、いくつかのnは任意のnのための、> nは0_{が存在することを言います。彼らはnの特定の値については何も言わず、「十分に大きい」ものだけを言います。}

（あなたは言及しなかった）第二の問題は、Oがjust an upper bound (as opposed to Θ)あり、そのためにも十分な大きさnにすることを次の2つを比較することはできませんです。 A = √ NとB = Nのであれば、その後、明らかにBはよりも速く成長します。しかし、とBは依然として√ N = O（N ）とN = O（N）として、質問に合います。

Answer 3

アルゴリズム分析を行うとき、特にBig Ohの場合、入力サイズが無限に近づくにつれて考えるべきです。このような小さなサイズ（数千対数百万）では、両者の間に大きな違いはありません。しかし、一般にO（n）はO（n^2）よりも速く実行する必要があります。ただし、その差が数ミリ秒未満であってもです。私はその質問のキーワードがだと多くはだと思う。

Answer 4

答えはA.です。

関数f（x）の

ビッグああ順序をg（x）の場合はf（x）が< = Kの*のG（X）FORALL X>いくつかの実数3の

ビッグああ* N + 2 4 * nはすべてのx> 2の両方の関数よりも大きいので、nはO（n）です。関数のBig Oh表記はすべて同じ値なので、同じ値のときに同じ時間で実行されるとは言えません。たとえばn = 0の場合、最初の関数の値は2で、2番目の値は0です。

ある値に対して2つの関数の実行時間を正確に関連付けることはできません。

Answer 5

私の答えはあなたがどちらの話をするとビッグO.

と呼ばれるOかの基本的な理解を必要と競争力のあるプログラミング、中に私の経験に基づいていますが高速で、どちらが遅くなり、もちろん、基本的な計算が行われます。 O（n）はO（n^2）よりも速いため、ワーストケースのシナリオに基づいてbig ohが使用されます。

正確に起こったときは？さて、競争的なプログラミングでは、我々は10^8サムルールを使用しました。それは、アルゴリズムの複雑さがO（n）であり、約1秒間に制限があるn = 10^8があると、アルゴリズムは問題を解決できます。

しかし、アルゴリズムの複雑さがO（n^2）の場合はどうなりますか？いいえ、その後、約1秒以上である(10^8)^2が必要になります。 （1秒のコンピュータは約10^8の操作を処理できます）。

したがって、O（n^2）の最大範囲は10^4です。一方、O（n）は最大で10^8になります。これは、コンピュータ上の1秒間のパスにおける2つの複雑さの違いをはっきりと見ることができるところです。