2 つのアルゴリズムは、A と B が同じ問題を解決するために書かれていると言います。アルゴリズム A は O(n) です。アルゴリズム B は (n^2) です。アルゴリズム A がより適切に機能することを期待します。
ただし、同じマシンの特定の例を実行すると、アルゴリズム B の方が速く実行されます。そのようなことがどのように起こるかを説明する理由を教えてください。
質問する
16149 次
5 に答える
3
これまでのすべての答えは正しいように見えますが... CSクラスのコンテキストでは、どれも本当に「正しい」とは感じません。計算の複雑さのコースでは、正確で定義を使用する必要があります。この質問と一般的な計算の複雑さの多くのニュアンスについて概説します。最後に、一番上にある Itay のソリューションがおそらくあなたが書くべきものである理由を結論付けます。Itay のソリューションに関する私の主な問題は、CS クラスの適切な証明を作成するための鍵となる定義が不足していることです。私の定義はあなたのクラスとは少し異なるかもしれないので、自由に置き換えてください。
「あるアルゴリズムは」と言うとき、O(n)実際には「このアルゴリズムはセット内にある」という意味O(n)です。そして、このセットには、最悪の場合の漸近的複雑度 が、ある定数とwhereのプロパティを持つO(n)すべてのアルゴリズムが含まれています。f(n)f(n) <= c*n + c_0cc_0c, c_0 > 0
次に、あなたの主張を証明したいと思います。まず第一に、あなたが問題を述べた方法、それには些細な解決策があります。これは、漸近境界が「最悪のケース」であるためです。多くの「遅い」アルゴリズムでは、非常に高速に実行されるという入力があります。たとえば、入力が既にソートされている場合、挿入ソートは線形です! したがって、挿入ソート ( O(n)) とマージソート ( )を例にとるO(nlog(n))と、ソートされた配列を渡すと、挿入ソートがより高速に実行されることに注意してください。ブーム、証明完了。
しかし、あなたの試験は、「最悪の場合、線形アルゴリズムが二次アルゴリズムよりも速く実行される理由を示す」ようなものを意味していたと思います。アレックスが前述したように、これは自由回答形式の質問です。この問題の核心は、ランタイム分析が特定の操作O(1)であると仮定することです (たとえば、ある問題では、大きな数では乗算が 2 次関数的に遅くなるにもかかわらず、乗算が行われると仮定する場合がありO(1)ます (特定の問題の数値は制限されていると主張する人もいます)。 100ビットなので、まだ「一定時間」です））。あなたのクラスはおそらく計算の複雑さに特に焦点を当てているので、おそらくこの問題を無視することを望んでいるでしょう. したがって、次のことを仮定して主張を証明します。O(1)仮定は正しいので、「キャッシングにより、このアルゴリズムは他のアルゴリズムよりも高速になります」などの詳細はありません。
これで、 is で実行される 1 つのアルゴリズムと、f(n)isO(n)で実行される別のアルゴリズムができましg(n)たO(n^2)。n上記の定義を使用して、を持つことができるものがあることを示したいと思いますg(n) < f(n)。トリックは、私たちの仮定がc, c_0, c', c_0'. Itay が言及しているようにg(n) < f(n)、多くのn. そして、残りの証明は彼が上で書いたものです (例えばc, c_0、 を定数にしf(n)て、それらが両方とも 100 でありc', c_0'、 が定数でg(n)あり、両方とも 1 であるとします。次にg(n) < f(n) => n + 1 < 100n^2 + 100 => 100n^2 - n + 99 > 0 => (factor to get actual bounds for n))
于 2013-04-14T09:16:18.623 に答える
1
シナリオによって異なります。シナリオには、1.ベスト、2.平均、3.ワーストの 3 種類があります。並べ替えのテクニックを知っていれば、同じことが起こります。詳細については、次のリンクを参照してください。
http://en.wikipedia.org/wiki/Sorting_algorithm
間違っている場合は修正してください。
于 2013-04-14T08:29:48.150 に答える