5

マージソートやクイックソートなどのアルゴリズムが分割統治パラダイムを使用していることは知っていますが、時間の複雑さを下げるのになぜそれが機能するのか疑問に思っています...

通常、「分割統治」アルゴリズムが非分割統治アルゴリズムよりもうまく機能するのはなぜですか?

4

3 に答える 3

4

分割統治アルゴリズムは、作業が少なくて済むため、高速に動作します。

二分探索の古典的な分割統治アルゴリズムを考えてみましょう。N二分探索は、答えを見つけるために項目を調べるのではなくLog2N、それらだけをチェックすることになります。当然のことながら、仕事が減れば、より早く終わらせることができます。それがまさに、分割統治アルゴリズムで起こっていることです。

もちろん、結果は、戦略が作業をどの程度うまく分割できるかに大きく依存します。分割がすべてのステップで多かれ少なかれ公平である場合 (つまり、作業を半分に分割する場合)、完璧なLog2N速度が得られます。ただし、分割が完全でない場合 (たとえば、O(n^2)反復ごとに 1 つの要素のみを削除するために配列の並べ替えに費やすクイックソートの最悪のケース)、分割統治戦略は役に立ちません。仕事量を減らす。

于 2013-03-27T15:30:58.973 に答える
2

分割統治アルゴリズムは、「通常はうまく機能する」わけではありません。他の非分割統治アルゴリズムと同様に、それらは機能します。それらはソートの複雑さを低下させませんが、他のアルゴリズムと同じように機能します。

于 2013-03-27T15:29:34.423 に答える
2

数学がそれをサポートしているので、分割統治はうまくいきます!

いくつかの分割統治アルゴリズムを検討してください。

1) 二分探索:このアルゴリズムは、入力スペースを毎回半分に減らします。多くの要素を調べることを避けるため、これが線形検索よりも優れていることは直感的に明らかです。

しかし、どれくらい良いですか？再発を取得します (注: これは最悪の場合の分析の再発です)。

T(n) = T(n/2) + O(1)

数学はそれを意味しT(n) = Theta(log n)ます。したがって、これは線形検索よりも指数関数的に優れています。

2) マージソート:ここでは、2 つの (ほぼ) 等しい半分に分割し、半分をソートしてからマージします。なぜこれは二次よりも優れているのでしょうか? これは再発です：

T(n) = 2T(n/2) + O(n)

数学的に示すことができます (たとえば、マスター定理を使用して) T(n) = Theta(n log n). したがって、T(n) は 2 次よりも漸近的に優れています。

素朴なクイックソートが最悪の場合の再発を与えることになることを観察してください

T(n) = T(n-1) + O(n)

これは数学的には 2 次であり、最悪の場合、(漸近的に言えば) バブル ソートよりも優れているとは言えません。しかし、平均的なケースでは、クイックソートは O(n log n) であることを示すことができます。

3 選択アルゴリズム: これは、k^ 番目に大きい要素を見つけるための分割統治アルゴリズムです。このアルゴリズムがソートよりも優れているかどうか (または、2 次でないことさえ) はまったく明らかではありません。

しかし、数学的には、その再発 (これも最悪のケース) は次のようになります。

T(n) = T(n/5) + T(7n/10 + 6) + O(n)

これは数学的に示すことができるT(n) = O(n)ため、ソートよりも優れています。

おそらく、それらを見る一般的な方法は次のとおりです。

各サブ問題が現在のサブツリーになるツリーとしてアルゴリズムを見ることができ、ノードに完了した作業量のタグを付けることができ、ノードごとに合計作業を追加できます。

二分探索の場合、作業は O(1) (単なる比較) であり、サブツリーの 1 つである作業は 0 であるため、作業の総量は O(log n) (基本的にはパスであり、二分探索木で行う）。

マージソートの場合、k 個の子を持つノードの場合、作業は O(k) (マージ ステップ) です。各レベルで行われる作業は O(n) (n、n/2 + n/2、n/4 + n/4 + n/4 + n/4 など) であり、O(log n) レベルがあり、したがって、マージソートは O(n log n) です。

クイックソートの場合、最悪の場合、バイナリ ツリーは実際には連結リストであるため、実行される作業は n+n-1 + ... + 1 = Omega(n^2) になります。

選択ソートについては、視覚化する方法がわかりませんが、3 つの子 (n/5、7n/10、および残り) を持つツリーとして見ると、まだ役立つと思います。

于 2013-03-27T16:41:58.840 に答える