49

別の既知のアルゴリズムよりも時間の複雑さが悪いが、すべての実際の状況でより良い選択である広く使用されているアルゴリズムはありますか (複雑さは劣りますが、それ以外の場合は優れています)?

受け入れられる答えは、次のような形式です。

それに応じてと時間の複雑さを持つアルゴリズムがありますがA、定数が非常に大きいため、宇宙内の原子の数よりも少ない入力に対しては 利点がありません。BO(N**2)O(N)BA

回答のハイライトの例:

  • シンプレックス アルゴリズム -- 最悪の場合は指数時間 --対凸最適化問題の既知の多項式時間アルゴリズム。

  • 中央値アルゴリズムの単純な中央値 -- 最悪の場合の O(N**2)対既知の O(N) アルゴリズム。

  • バックトラッキング正規表現エンジン -- 最悪の場合の指数対O(N) Thompson NFA ベースのエンジン。

これらの例はすべて、最悪のシナリオと平均的なシナリオを比較したものです。

最悪のケースと平均的なケースのシナリオの違いに依存しない例はありますか?

関連している：

  • 「悪いほうがいい」の台頭。(この質問の目的のために、「Worse is Better」というフレーズは、記事よりも狭い(つまり、アルゴリズムの時間の複雑さ) 意味で使用されています)

  • Python の設計哲学:

    ABC グループは完璧を目指して努力しました。たとえば、漸近的に大きなコレクションに最適であることが証明されたツリーベースのデータ構造アルゴリズムを使用しました (ただし、小さなコレクションにはあまり適していませんでした)。

    この例は、これらの大規模なコレクションを格納できるコンピューターがない場合の答えです (つまり、この場合、大規模では十分な大きさではありません)。

  • 正方行列乗算のCoppersmith–Winograd アルゴリズムは良い例です (これは最速 (2008 年) ですが、悪いアルゴリズムより劣っています)。他のもの？ ウィキペディアの記事から: 「現在のハードウェアでは処理できないほど大きな行列に対してのみ利点があるため (Robinson 2005)、実際には使用されていません。」

4

24 に答える 24

35

クイックソートは、最悪の場合のO（N ^ 2）の時間計算量を持ちますが、通常、最悪の場合のO（N log n）の時間計算量を持つ他のソートアルゴリズムよりも優れていると見なされます。

于 2009-01-23T01:45:21.883 に答える
29

シンプレックスは、最悪の場合は指数関数的な時間計算量を持つアルゴリズムですが、実際の場合は多項式です。おそらく線形計画法の多項式アルゴリズムが存在しますが、それらは非常に複雑で、通常は大きな定数を持っています。

于 2009-01-23T01:49:20.083 に答える
15

モンテカルロ積分は、正解を返す保証のない定積分を計算する確率的手法です。それでも、実際の状況では、証明可能な正しい方法よりもはるかに速く正確な答えを返します。

于 2009-01-23T18:14:35.787 に答える
14

「WorseisBetter」は、Perl、Python、Ruby、Php、C＃やJavaの背後にあるアイデア、またはアセンブラーやCではない言語（C ++がここに収まるかどうかはわかりません）などの言語でも見られます。

基本的には常に「完璧な」解決策がありますが、多くの場合、「より悪い」ツール/アルゴリズム/言語を使用して、より速く、より少ない苦痛で結果を得る方が良いでしょう。そのため、人々はこれらの高級言語を使用しますが、理想的なコンピューター言語の観点からは「より悪い」ものであり、代わりに人間志向です。

于 2009-01-23T02:09:36.237 に答える
13

正方行列乗算のためのCoppersmith–Winograd アルゴリズム。その時間計算量は、単純な乗算アルゴリズムのO(n 2.376 )対O(n 3 )、またはStrassenアルゴリズムのO(n 2.807 )です。

ウィキペディアの記事から：

ただし、Strassen アルゴリズムとは異なり、現在のハードウェアでは処理できないほど大きな行列に対してのみ利点があるため、実際には使用されません (Robinson 2005)。

于 2009-02-02T12:03:09.950 に答える
10

このステートメントは、ほぼすべての並列アルゴリズムに適用できます。コンピューティングの初期にそれらがあまり研究されなかった理由は、単一の実行スレッド（ユニプロセッサを考えてください）の場合、漸近的な複雑さ、小さなnの定数係数の点で、よく知られているシーケンシャルな対応物よりも実際に遅いためです。または両方。ただし、現在および将来のコンピューティングプラットフォームのコンテキストでは、数（マルチコアと考える）、数百（GPUと考える）、または数千（スーパーコンピューターと考える）の処理要素を利用できるアルゴリズムは、シーケンシャルバージョンのパンツを打ち負かします実時間では、すべてのプロセッサが費やした合計時間/エネルギーが並列バージョンの方がはるかに大きい場合でも。

並べ替え、グラフアルゴリズム、線形代数の手法は、並列化するために少し余分な簿記、通信、および実行時のオーバーヘッドのコストを負担することにより、実時間の観点から高速化できます。

于 2009-01-23T02:08:55.130 に答える
9

多くの場合、これらの品質を欠く競合するアルゴリズムよりも、簡単に並列化またはランダム化できるアルゴリズム（クイックソートなど）が選択されます。さらに、巡回セールスマン問題のように、正確なアルゴリズムが指数関数的な実行時間をもたらす場合、問題の近似解が受け入れられることがよくあります。

于 2009-01-23T01:50:03.013 に答える
8

この例は、これらの大規模なコレクションを格納できるコンピューターがない場合の答えになります。

おそらくコレクションのサイズは 641K でした。

さまざまな航空機の構造および空力コードを担当していた BAE SYSTEMS のテクニカル コンピューティング グループで働いていたとき、コードベースは少なくとも 25 年前にさかのぼりました (そして、スタッフの 3 分の 1 はその期間そこにいました)。

アルゴリズムの多くは、スケーラビリティではなく、16 ビット メインフレームでのパフォーマンスに合わせて最適化されています。これらの最適化は 1970 年代のハードウェアには完全に適していましたが、それに取って代わった 32 および 64 ビット システムのより大きなデータセットではうまく機能しませんでした。現在取り組んでいるハードウェアでよりうまく機能するスケーラビリティの悪いものを選択している場合、これは最適化であり、将来的には適用されない可能性があることに注意してください。これらの 1970 年代のルーチンが作成された時点では、2000 年代にそれらに入れられたデータ サイズは実用的ではありませんでした。残念ながら、これらのコードから明確なアルゴリズムを抽出して、最新のハードウェアに合わせて実装できるようにすることは簡単ではありませんでした。

大海を沸騰させることを除いて、「すべての実際的な状況」と見なされるものは、多くの場合、時間に依存する変数です。

于 2009-01-23T13:38:49.340 に答える
5

あまり目立たないが、バックトラックベースの正規表現は、DFAベースの正規表現のO（N）に対して指数関数的な最悪のケースがありますが、DFAベースの正規表現ではなく、ほとんどの場合、バックトラックベースの正規表現が使用されます。

編集：（JFS）

正規表現のマッチングは単純で高速です（ただし、Java、Perl、PHP、Python、Rubyなどでは低速です）：

後方参照が追加する能力には多大なコストがかかります。最悪の場合、最もよく知られている実装には指数探索アルゴリズムが必要です。

正規表現エンジン：

この方法（DFA）は実際にはより効率的であり、キャプチャーや欲張りでないマッチングを可能にするように適合させることもできますが、重要な欠点もあります。

  • 見回すのは不可能です
  • 逆参照も不可能です
  • 正規表現の事前コンパイルはより長く、より多くのメモリを必要とします

明るい面として、DFAアプローチは、最悪の場合の指数関数的な実行時間を回避するだけでなく、入力データのサイズが線形である最悪の場合のスタックの使用を回避します。

[3]：

于 2009-01-29T04:37:27.640 に答える
5

素数性を判断するための多項式時間アルゴリズムが存在しますが、実際には、指数時間アルゴリズムを使用するか、十分な確実性を得るために十分な確率計算を実行する方が常に高速です。

于 2011-02-23T16:28:52.897 に答える
5

1 つの例は、計算幾何学からのものです。Polygon TriangulationはChazelleにより最悪の O(N) アルゴリズムを持っていますが、実装の難しさと巨大な定数のために実際にはほとんど実装されていません。

于 2010-11-21T20:59:05.500 に答える
4

数値グループの中央値を計算する場合、クイックソートに非常によく似たアルゴリズムを使用できます。数字を分割すると、大きいものはすべて片側に、小さいものはすべて反対側に移動します。次に、一方の辺を捨てて、大きい方の辺の中央値を再帰的に計算します。これは最悪のケースでは O(n^2) かかりますが、平均的なケースではかなり高速です (低い定数の O(n))。

約 40 の定数で、最悪の場合の O(n) パフォーマンスを保証できます。これは、中央値アルゴリズムの中央値と呼ばれます。実際には、これを使用することはありません。

于 2009-01-29T02:40:51.777 に答える
4

基数ソートは、固定長入力に対して時間複雑度 O(n) を持ちますが、基数ソートの要素ごとのオーバーヘッドは通常、はるかに高いため、漸近的なランタイムが悪いにもかかわらず、クイックソートがより頻繁に使用されます。

于 2009-01-23T19:25:08.033 に答える
4

では、巡回セールスマンの問題を解決することを考えてみましょう。唯一の完璧な解決策は、考えられるすべてのルートをテストすることです。ただし、N が増加するにつれて、ハードウェアと時間制限ではそれが不可能になります。そのため、多くのヒューリスティックを考えてきました。

これにより、質問の答えが得られます。ヒューリスティック（悪い）は、NP完全問題のブルートフォースよりも優れています。これは、「Worse is Better」が常に真である状況を表しています。

于 2009-01-28T03:07:01.910 に答える
4

私が質問を理解している場合、理論的には優れているが、すべての状況で実際には劣っているアルゴリズムを求めています。したがって、誤って使用しない限り、それらが実際に使用されることは期待できません。

考えられる例の 1 つは、普遍的なメモ化です。理論的には、すべての決定論的関数呼び出しは、すべての可能な入力に対してメモ化する必要があります。そうすれば、複雑な計算を単純なテーブル ルックアップに置き換えることができます。さまざまな問題に対して、この手法は生産的に時間とストレージ スペースを交換します。しかし、人類のすべてのコンピュータによって使用されるすべての可能な機能に対するすべての可能な入力の結果の中央リポジトリがあったとします。誰かがどこかで初めて計算を行ったのは、それが最後になるでしょう。それ以降のすべての試行では、テーブル ルックアップが発生します。

しかし、これを行わない理由はいくつか考えられます。

  1. すべての結果を格納するために必要なメモリ領域は、おそらく信じられないほど大きくなります。必要なビットの数は、宇宙の粒子の数を超える可能性が高いようです。(しかし、その数を見積もる作業さえ困難です。)

  2. その膨大な問題空間をメモ化するための効率的なアルゴリズムを構築するのは難しいでしょう。

  3. クライアントの数が増えると、中央リポジトリとの通信コストが利益を上回る可能性があります。

他の問題も考えられると思います。

実際、この種の時間/空間のトレードオフは、実際には信じられないほど一般的です。理想的には、すべてのデータが L1 キャッシュに保存されますが、サイズの制限により、ディスクまたは (恐ろしい!) テープに常にデータを配置する必要があります。テクノロジーの進歩により、これらのトレードオフの痛みはいくらか軽減されますが、上で示唆したように、限界があります。

JFセバスチャンのコメントに応えて：

普遍的なメモ化リポジトリの代わりに、階乗リポジトリを検討するとします。また、可能なすべての入力の結果が保持されるわけではありません。むしろ、それは から までの結果に限定され1ますN! 。これで、階乗を行ったコンピューターは、計算を行うよりも結果を調べることで利益を得ることが容易にわかります。(N+1)!ルックアップを計算する場合でも、その計算は に減少するため、大きな勝利になりN!(N+1)ます。

この「より良い」アルゴリズムをさらに悪化させるには、N を増やすか、リポジトリを使用するコンピューターの数を増やす必要があります。

しかし、私はおそらく質問の微妙な点を理解していません。私が考えているように、そうでない場合まで、うまくスケーリングできる例を考え続けます。

于 2009-01-29T19:47:09.687 に答える
3

マージソートとクイックソート

クイック ソートの平均時間の複雑さは O( n log n ) です。配列をその場でソートできます。つまり、空間の複雑さは O(1) です。

マージソートも O( n log n ) の平均時間複雑性を持っていますが、その空間複雑性はさらに悪いです: Θ( n )。(連結リストには特殊なケースがあります)

クイックソートの最悪の場合の時間の複雑さは Θ(n^2) (つまり、すべての要素がすべてのピボットの同じ側にある) であり、マージソートの最悪のケースは O( n log n ) であるため、ライブラリのデフォルトの選択はマージソートです。実装者。

この場合、マージソートの最悪の場合の時間の複雑さの予測可能性は、クイックソートがはるかに低いメモリ要件に勝ると思います。

クイックソートの時間の複雑さの最悪のケースの可能性を大幅に減らすことができることを考えると (たとえば、ピボットのランダムな選択を介して)、マージソートはクイックソートの病理学的ケースを除いてすべて悪いと主張できると思います。

于 2009-01-28T12:33:26.433 に答える
2

私は常に、「より悪い」という用語は、比較的理解しやすい近似（または十分に良い）ソリューションが存在する非常に複雑な正しいソリューションの問題に関連することを理解しています。

これにより、設計、製造、および保守が容易になります。

于 2009-01-23T02:19:58.430 に答える
2

O(n 2 ) の複雑さにもかかわらず、挿入ソートは小さなコレクション (n < 10) の場合、他のどのソート アルゴリズムよりも高速です。これは、ネストされたループが小さく、高速に実行されるためです。sort メソッドを実装している多くのライブラリ (STL を含む) は、実際にそれをデータの小さなサブセットに使用して高速化しています。

于 2009-01-29T02:31:01.000 に答える
1

モンテカルロ統合はすでに提案されていますが、より具体的な例として、金融におけるモンテカルロ プライシングも提案されています。ここで、メソッドはコーディングがはるかに簡単で、他のいくつかのメソッドよりも多くのことを実行できますが、有限差分よりもはるかに遅くなります。

20 次元の有限差分アルゴリズムを実行するのは実用的ではありませんが、20 次元の価格設定の実行は簡単にセットアップできます。

于 2009-01-29T05:02:39.557 に答える
1

Spaghetti ソートは、セットアップに O(n)、実行に O(1)、ソートされたデータの抽出に O(n) という点で、他のどのソート アルゴリズムよりも優れています。これらすべてを O(n) 空間の複雑さで実現します。(全体的なパフォーマンス: 時間と空間の両方で O(n)。) しかし、奇妙な (明白な) 理由で、誰もそれを何にも使用せず、はるかに劣った O(nlogn) アルゴリズムとその同類を好んでいます。

于 2010-05-31T05:03:37.397 に答える
0

反復的な深化

単純な深さ優先検索にアルファ ベータ プルーニングを追加した場合と比較すると、反復的な深化検索を貧弱な (または存在しない) 分岐順序付けヒューリスティックと組み合わせて使用​​すると、より多くのノードがスキャンされることになります。ただし、優れた分岐順序付けヒューリスティックを使用すると、アルファ ベータ枝刈りの効果が高まるため、ツリーのかなりの部分が削除されます。時間や空間の複雑さとは関係のない 2 つ目の利点は、問題領域に対する解の推測が早期に確立され、探索が進むにつれてその推測が洗練されることです。多くの問題領域で魅力的なのは、この 2 番目の利点です。

于 2010-05-31T04:16:13.313 に答える