必ず読むべき28の古典的なプログラミングアルゴリズム

最初の 10 個は、聖書からのトップ 10 アルゴリズムです。

発起者からの説明: Proofs from the Bible には、簡潔でエレガントな数学的証明が数十個集められており、すぐに多くの数学愛好家の支持を得ました。 「聖書からのアルゴリズム」という別の本があったら、そこにはどのようなアルゴリズムが含まれているでしょうか?

***名前: Union-find

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

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

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

3位: BFPRTアルゴリズム

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

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

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

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

大きい場合は、配列を再帰的に分割します。

小さい場合は、配列を中央のピボット ポイント要素として再帰します。

それ以外の場合は、パーティションで返される値である配列を返します。 //この s を見つけるだけです。

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

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

4. クイックソート

クイックソートアルゴリズムは、すべての古典的なアルゴリズムのほぼすべてのリストをカバーします。これは 20 世紀の 10 大アルゴリズムの 1 つに選ばれました。

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

このアルゴリズムの紹介については、私が書いたこの記事「いくつかの最短経路アルゴリズムの比較」(http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx) を参照してください。

d: 2D 配列。d は、コストが最小またはパスが最短となる隣接エッジです。

k は 1 から n までです:

i は 1 から n までです:

jは1からnまで:

d = min(d, d + d)

第6位：ジェントリーの完全準同型暗号化方式

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

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

これらは他の多くのアルゴリズムの基礎となります。

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

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

第9回: バイナリ検索

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

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

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

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

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

10位: ハフマン符号化

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

11. Cooley-Tukey FFT アルゴリズム。高速フーリエ変換アルゴリズム。

12. 線形計画法。

13. ダイクストラアルゴリズム。

上記の 5 番目と同じ、別の最短経路アルゴリズムです。

14. マージソート。

マージソート。

15. フォード・フルカーソンアルゴリズム。

ネットワーク***フローアルゴリズム。

16. ユークリッド法。

数学において、ユークリッドの互除法は、最大公約数を見つけるアルゴリズム、つまり 2 つの正の整数の最大公約数を見つけるアルゴリズムです。このアルゴリズムは TAOCP の最初のアルゴリズムとして説明されており、注目度の高さが伺えます。これは 3000 年前に遡る、最も古い既知のアルゴリズムです。ユークリッドの互除法は、ユークリッドの『原論』（第 7 巻、命題 i と ii）で初めて登場し、中国では東漢の時代に登場した『九章算術』にまで遡ることができます。拡張ユークリッド定理は、任意の整数 a と b に対して、ax + by = gcd(a, b) となる x、y のペアが存在することを構成的に証明します。

17. RSA暗号化アルゴリズム。

暗号化アルゴリズムについては後ほど詳しく説明します。

18. 遺伝的アルゴリズム。

19. 期待値（EM）アルゴリズム。

このアルゴリズムは、データマイニングの分野におけるトップ 10 の古典的なアルゴリズムの 1 つに選ばれました。統計計算において、最小期待値 (EM) アルゴリズムは、観測不可能な潜在変数に依存する確率モデル内のパラメータの最小尤度推定値を見つけるためのアルゴリズムです。 ***機械学習やコンピュータービジョンにおけるデータクラスタリングの分野で多用されることが期待されています。期待値アルゴリズムは、2 つのステップで交互に計算を実行します。最初のステップは、隠れ変数の既存の推定値を使用してそれらの尤度推定値を計算し、期待値 (E) を計算することです。2 番目のステップは最適化 (M) で、E ステップで取得した尤度値を最適化して、パラメーターの値を計算します。 M ステップで見つかったパラメータ推定値は次の E ステップの計算に使用され、このプロセスが交互に継続されます。

20. データ圧縮

データ圧縮は、コンピューターや通信に保存されるデータの冗長性を削減することでデータ密度を高め、最終的にデータの保存スペースを削減するテクノロジです。データ圧縮は、ファイル ストレージや分散システムで広く使用されています。データ圧縮は、メディア容量の増加とネットワーク帯域幅の拡張も意味します。

21. ハッシュ関数

ハッシュは、一般的に「ハッシュ」と翻訳され、「ハッシュ」と直接書き起こされることもあります。ハッシュは、ハッシュ アルゴリズムを使用して、任意の長さの入力 (プレマッピング、プレイメージとも呼ばれます) を固定長の出力に変換します。出力はハッシュ値です。

22. 動的プログラミング。

23. ヒープソートアルゴリズム。

高速かつ安定したアルゴリズムであるヒープソートアルゴリズムの平均時間計算量（最悪の場合）は O(n*lgn) です。もちろん、実際のアプリケーションでは、適切に実装されたクイック ソート アルゴリズムはヒープ ソート アルゴリズムよりも優れています。ただし、ヒープ データ構造は効率的な優先キューとしても機能します。

24. 再帰とバックトラッキングアルゴリズム。

これら 2 つのアルゴリズムについては既にご存知かと思いますので、ここでは詳細には触れません。

25. 最長共通部分列

最長共通部分列。LCS (Longest Common Subsequence) と略されます。その定義は、シーケンス S が 2 つ以上の既知のシーケンスの部分シーケンスであり、この条件を満たすすべてのシーケンスの中で最長である場合、S は既知のシーケンスの最長共通部分シーケンスと呼ばれるというものです。

最長共通部分列を計算する動的計画法は次のとおりです。

2 つのシーケンス X と Y を例に挙げます。

2 次元配列 f が X の i 番目の位置と Y の j 番目の位置の前の最長共通部分列の長さを表すとすると、次のようになります。

f = 同じ(1,1)

f = max{f+same(i,j),f,f}

このうち、same(a,b) は、X の a 番目のビットが Y の b 番目のビットと完全に同じ場合に「1」になり、そうでない場合は「0」になります。

この時点で、f の最小の数字は、X と Y の最長共通部分列の長さです。配列をバックトラックすると、最長共通部分列を見つけることができます。

このアルゴリズムの空間計算量と時間計算量はともに O(n2) です。最適化後、空間計算量は O(n)、時間計算量は O(nlogn) になります。

26. 赤黒木のアルゴリズムと実装

赤黒木に関しては、Linux カーネルに実装されています。

27. A*検索アルゴリズム。

BFS、ダイクストラ法などのアルゴリズムと比較して、A* 検索アルゴリズムは効率的な最短経路検索アルゴリズムとして、ますます広く使用されるようになっています。

28. 画像特徴抽出とマッチングのためのSIFTアルゴリズム

SIFT (スケール不変特徴変換) は、画像内のローカル特徴を検出して記述するために使用されるコンピューター ビジョン アルゴリズムです。空間スケールの極値点を検索し、その位置、スケール、回転の不変量を抽出します。このアルゴリズムは、1999 年に David Lowe によって公開され、2004 年に改良されました。