19

分割統治アルゴリズムがブルートフォースよりも速く実行されることが多いのはなぜですか？たとえば、最も近いポイントのペアを検索します。私はあなたが私に数学的証明を見せてくれることを知っています。しかし、直感的に、なぜこれが起こるのですか？魔法？

理論的には、「分割統治はブルートフォースよりも常に優れている」というのは本当ですか？そうでない場合、反例はありますか？

4

2 に答える 2

26

最初の質問については、分割統治の背後にある直感は、多くの問題では、実行する必要がある作業の量が、線形以上にスケーリングする入力の組み合わせプロパティに基づいているということです。

たとえば、最も近い点のペアの問題では、O(n 2 ) 個の可能な点のペアすべてを調べなければならないという事実によって、力ずくの答えの実行時間が決まります。

二次関数的に成長するものを 2 つに切り分け、それぞれが以前の半分のサイズになると、最初の 4 分の 1 の時間がそれぞれの半分の問題を解決するのにかかるため、両方の半分の問題を解決するにはおおよその時間がかかりますブルートフォースソリューションに必要な時間の半分。4 つに切るのに 4 分の 1 の時間がかかり、8 つに切るのに 8 分の 1 の時間がかかります。

この場合、再帰バージョンは最終的に高速になります。これは、各ステップで、実際にチェックする必要があるペアが多すぎないようにすることで、要素のペアを処理することで多くの作業を行うことを回避できるためです。分割統治ソリューションを持つほとんどのアルゴリズムは、同様の理由でより高速になります。

2 番目の質問については、いいえ、分割統治アルゴリズムは総当たりアルゴリズムよりも必ずしも高速ではありません。配列の最大値を見つける問題を考えてみましょう。ブルート フォース アルゴリズムは O(n) 時間かかり、O(1) スペースを使用してデータを線形スキャンします。分割統治アルゴリズムは次のとおりです。

  • 配列に要素が 1 つしかない場合は、それが最大値です。
  • さもないと：
    • アレイを半分にカットします。
    • 各半分の最大値を見つけます。
    • これら 2 つの値の最大値を計算します。

これにも O(n) の時間がかかりますが、スタック スペースに O(log n) メモリを使用します。実際には、単純な線形アルゴリズムよりも悪いです。

別の例として、最大の単一販売利益問題には分割統治法がありますが、最適化された動的計画法のソリューションは、時間とメモリの両方でより高速です。

お役に立てれば！

于 2012-06-15T00:50:14.660 に答える
5

Algorithm Designの第 5 章を読むことをお勧めします。分割統治法が非常によく説明されています。

直感的には、ある問題を元の問題と同じパターンで 2 つのサブ問題に分割でき、2 つのサブ問題の結果を最終結果にマージする時間の複雑さがある程度小さい場合、その方が高速です。力ずくで元の完全な問題を解決するよりも。

Algorithm Designで述べたように、実際には時間に関して分割統治からあまり多くを得ることができません。一般に、時間の複雑さをより高い多項式からより低い多項式に減らすことしかできません(たとえば、O(n^3) から O(n^) 2)) ですが、指数関数から多項式 (たとえば、O(2^n) から O(n^3)) にはなりません。

分割統治から得られる最大のものは、問題解決の考え方だと思います。元の大きな問題をより小さく簡単なサブ問題に分解することは、常に良い試みです。実行時間が改善されなくても、問題を解決するのに役立ちます。

于 2012-06-15T00:58:54.423 に答える