現在世界で最も重要な古典的アルゴリズムトップ10

今日の世界では、数え切れないほどの古典的なアルゴリズムが発見または作成されてきました。最も価値あるアルゴリズムのトップ 10 に投票するとしたら、何を選びますか?

最近、誰かが StackExchange で、ネットユーザーに現在世界で最も古典的なアルゴリズムのトップ 10 を集めるよう求める質問をしました。観客は多数の候補アルゴリズムの中から投票し、最終的に最も多くの支持を得た次の 10 個のアルゴリズムを決定しました。

聖書に出てくるアルゴリズムトップ10:

発起者からの説明: Proofs from the Bible には、簡潔でエレガントな数学的証明が数十個集められており、すぐに多くの数学愛好家の支持を得ました。「聖書からのアルゴリズム」という別の本があったら、そこにはどのようなアルゴリズムが含まれているでしょうか?さて、皆さん、ここに候補となるアルゴリズムが何十個もあります。これが今日の世界で最も古典的なアルゴリズムだと思うなら、ぜひ投票してください.....

最終的に、最も多くの票を獲得した次の 10 個の古典的なアルゴリズムが生成されました。

10位: ハフマン符号化

ハフマン符号化は、ロスレスデータ圧縮に使用される符号化方式およびエントロピー符号化（重み符号化）アルゴリズムです。これは、1952 年に MIT で博士号取得を目指していた David A. Huffman によって発明され、「最小冗長コードの構築方法」という論文で発表されました。

第9回: バイナリ検索

順序付けられたコレクション内の要素を見つけるには、バイナリ検索アルゴリズム (バイナリサーチとも呼ばれます) を使用できます。バイナリ検索アルゴリズムは、まずセットの中央にある要素をキーのサイズと比較します。次の 3 つのケースがあります (セットが小さいものから大きいものの順に並べられていると仮定)。

1. キーが中央の位置にある要素より小さい場合、一致する要素は左側にあるはずなので（ある場合）、左側の領域にバイナリ検索が適用されます。

2. キーは中央の位置にある要素と等しいので、要素が見つかります。

3. キーが中央の位置にある要素より大きい場合、一致する要素は右側にあるはずなので（存在する場合）、右側の領域にバイナリ検索が適用されます。

また、コレクションが空の場合は、見つからないことを意味します。

8. ミラー・ラビン類似実験テスト

アイデアは、素数の特性 (フェルマーの最終定理の使用など) を使用して、証人が素数を数えない小さな確率を見つけることです。十分なランダムテストを行っても証拠が見つからない場合、その数は素数です。

No. 7: 深さ優先探索、幅優先探索

これらは他の多くのアルゴリズムの基礎となります。深さ優先探索アルゴリズムと幅優先探索アルゴリズムの詳細な紹介については、この記事を参照してください: BFS および DFS 優先探索アルゴリズムの徹底的な理解を教えます。

No. 6: Gentry の完全準同型暗号化方式アルゴリズム。

このアルゴリズムは非常に優れており、第三者が秘密鍵を取得せずに暗号化されたデータに対して任意の操作を実行できるようになります（よく理解されていません）。

5. フロイド・ワーシャル全ペア最短経路アルゴリズム

このアルゴリズムの紹介については、私が書いたこの記事を参照してください: いくつかの最短経路アルゴリズムの比較

d[]: 2D配列。d[i,j]は最小コストまたは最短パスを持つ隣接エッジです。

 kは1 から n までです:
 iは1 から n までです:
 jは1からnまで:
 d[i,j] = min(d[i,j], d[i,k] + d[k,j])

4. クイックソート

クイックソートアルゴリズムは、すべての古典的なアルゴリズムのほぼすべてのリストをカバーします。これは、20 世紀の 10 大アルゴリズムの 1 つに選ばれました (こちらを参照: 20 世紀の 10 大アルゴリズムを数える)。クイックソートアルゴリズムの詳細な紹介については、私が書いたこの記事を参照してください: パート I の続き: クイックソートアルゴリズムの詳細な分析。

3位: BFPRTアルゴリズム

1973 年、Blum、Floyd、Pratt、Rivest、および Tarjan は共同で「選択の時間境界」というタイトルの論文を執筆しました。この論文では、配列内の k 番目に大きい要素を選択するアルゴリズムが提示され、一般に「中央値のアルゴリズム」として知られています。慎重に設計されたピボット選択方法に依存するこのアルゴリズムは、理論的には最悪の場合でも線形時間計算量を保証し、平均線形計算量と最悪の O(n^2) 計算量を持つ従来のアルゴリズムを上回ります。専門家のグループが再帰アルゴリズムの複雑性分析を習得し、まさにバイブルアルゴリズムと呼ぶにふさわしいアルゴリズムを構築しました。

ここでは、配列内の k 番目に大きい要素を選択するための時間計算量が O(N) のアルゴリズムを簡単に紹介します。

クイックソートのセグメンテーションアルゴリズムに似ています:

各分割後、配列内のピボットポイントの位置 s を返すことができ、次に s のサイズが k と比較されます。

大きい場合は、配列[s..n]を再度再帰的に分割します。

小さい場合は、再帰的にarray[left...s-1] //sは中央のピボットポイント要素です。

それ以外の場合は、partition で返される値である配列[s]を返します。 //この s を見つけるだけです。

要件を満たす s 値を見つけたら、 s より小さい側の要素を走査して出力します。

参照先：アルゴリズム入門、第9章、第10節、期待線形時間での選択、

配列内の k 番目に小さい要素を見つけるには、平均で O(N) の時間計算量が必要であるという証明を見つけました。要素が別個であると仮定すると、上記のプログラムの予想実行時間は O(n) であることが証明されています。

2位: Knuth-Morris-Pratt 文字列マッチングアルゴリズム

このアルゴリズムの紹介については、こちらの記事を参照してください: 6. KMP アルゴリズムを最初から最後まで徹底的に理解する方法を教えます。 KMP アルゴリズムは 20 世紀の 10 大アルゴリズムの 1 つには選ばれませんでしたが、このように美しく効率的な KMP アルゴリズムが選ばれないことを人々が受け入れることは明らかにできませんでした。そのため、最終投票では、KMP アルゴリズムが 2 位になりました。

***名前: Union-find

厳密に言えば、union-find セットは、セットのマージとクエリ操作を処理するために特別に使用されるデータ構造です。ユニオン検索アルゴリズムは、ツリー構造を巧みに使用してプログラミングの複雑さを信じられないほどのレベルまで低減します。いくつかの再帰テクニックを使用すると、ほぼすべての操作を 2 行のコードで実行できます。パス圧縮の優れたアイデアは、データ構造全体の最後の仕上げです。 union-find の効率は非常に高く、単一の操作の時間計算量はほぼ一定レベルとみなすことができますが、データ構造の実際の動作を予測することは難しいため、正確な時間計算量分析には多くの高度な技術が必要です。最終的に、並列検索がこのリストのトップの座を獲得しました。

補足：上位 3 位の得票数はわずか 4 票と 8 票の差でした。そのため、このランキングは今後も変化し続けるでしょう。しかし、最終結果がどうであろうと、トップ 10 のアルゴリズムは基本的に確定しています。

いかがですか、上記のアルゴリズムについてご存知ですか? 今、私があなたに投票権を与えるとしたら、どのアルゴリズムに投票しますか? では、投票してみましょう。この記事の下のコメント欄に、あなたの意見や決定を書き込んでください。

オリジナルリンク: http://www.itrenjia.org/chengxuyuan/home-space-uid-5-do-blog-id-3761.html

【編集者のおすすめ】