Algorithm VisionMaster Algorithms

隣接する要素を繰り返し比較し、順序が間違っている場合に交換する最も基本的なソートアルゴリズムです。泡が水面に上がるように、大きな値が徐々に配列の末尾に移動します。小規模なデータセットやソートの基礎を理解するための教育目的に最適です。

最小の要素を見つけて繰り返し前方に移動させます。各反復で残りの要素から最小値を「選択」し、ソート済み部分の後ろに配置します。メモリ使用量は最小限でシンプルに実装できますが、入力に関係なく常にO(n²)の時間がかかります。

ピボット要素を選択し、小さい値を左側、大きい値を右側に配置して配列を分割する非常に効率的なソートアルゴリズムです。平均O(n log n)で、実際に最も広く使用されているソート方法です。ほとんどのプログラミング言語の組み込みソート関数の基盤となっています。

最大ヒープを構築し、ルート要素を繰り返し抽出してソートする二分ヒープデータ構造を使用します。すべての場合でO(n log n)の時間計算量を保証し、追加メモリを必要としません。優先度付きキューの実装の基礎にもなっています。

各要素の出現回数をカウントし、算術演算を使用して位置を決定する非比較ソートアルゴリズムです。入力値の範囲をkとして、O(n+k)の時間計算量を達成します。既知の限られた範囲内の整数のソートに理想的です。基数ソートの基礎を形成します。

最下位桁から最上位桁まで桁ごとに要素を処理する非比較ソートアルゴリズムです。各桁位置にカウンティングソートをサブルーチンとして使用します。桁数をdとしてO(d(n+k))時間を達成します。整数や固定長文字列のソートに優れています。

離れた要素の交換を可能にする挿入ソートの最適化です。1まで減少するギャップシーケンスを使用し、アルゴリズムが要素を最終位置により早く移動できるようにします。1959年にこれを発明したDonald Shellにちなんで名付けられました。

要素をいくつかのバケットに分配する分布ベースのソートアルゴリズムです。各バケットは別のソートアルゴリズムを使用して個別にソートされます。入力が範囲内で均一に分布している場合に最も効果的です。平均時間計算量はO(n+k)です。

配列を半分に分割し、各半分を再帰的にソートしてから結合する分割統治アルゴリズムです。O(n log n)の時間を保証し、安定ですが、追加メモリが必要です。大規模なデータセットや連結リストのソートに特に効果的です。

手札のカードをソートするように、各要素を一度に適切な位置に挿入します。既にソート済みのデータに対してO(n)時間で実行されるため、小規模な配列やほぼソート済みのデータセットに非常に効率的です。シンプルながら適応的なアルゴリズムです。

リストの末尾近くの小さな値（亀）を排除するバブルソートの改良版です。配列長から始まる縮小ギャップシーケンスを使用し、最悪ケースの複雑さを改善します。シンプルな実装が最適なパフォーマンスよりも重視される中規模データセットに実用的です。

挿入ソートに似たシンプルなソートアルゴリズムで、庭のノームが植木鉢をソートする方法にちなんで名付けられました。要素が順序通りでない場合は後退し、再び前進します。バブルソートと同様にO(n²)ですが、そのシンプルさがソートの概念を教えたり小規模データセットを扱うのに役立ちます。

目標値を中央の要素と比較し、探索空間を繰り返し半分にする非常に効率的な探索方法です。O(log n)時間で、100万個の要素からわずか20回の比較で項目を見つけることができます。辞書で単語を調べるように機能します。

最初から最後まで各要素を順番にチェックする最も基本的な探索方法です。未ソートデータや、シンプルさが重要な小規模配列に使用されます。実装は簡単ですが、O(n)時間を必要とする大規模データセットでは遅くなります。

グラフをレベルごとに探索し、より深く進む前に現在の深さのすべての頂点を訪問します。キューを使用し、重み付けされていないグラフでの最短経路を見つけるのに理想的です。迷路の解決、ソーシャルネットワーク分析、ノード間の接続の検索などの応用があります。

各経路に沿って可能な限り深く進んでから後戻りするグラフ探索方法です。スタックまたは再帰を使用して実装され、再帰的な問題に自然です。経路探索、サイクル検出、トポロジカルソート、迷路生成に使用されます。

重み付きグラフで単一始点から他のすべての頂点への最短経路を見つけます。GPSナビゲーションシステムやネットワークルーティングプロトコルを支えています。優先度付きキューを使用した貪欲法により、非負の辺の重みで効率的に機能します。

ヒューリスティックを使用して最短経路を見つける最良優先探索アルゴリズムです。f(n) = g(n) + h(n)を使用してダイクストラ法と貪欲最良優先探索を組み合わせます。ゲーム、ロボティクス、GPSナビゲーションで効率的な経路探索に広く使用されています。

重み付き無向グラフの最小全域木（MST）を見つけます。辺を重みでソートし、サイクルを作成しない場合に追加する貪欲アプローチを使用します。効率的なサイクル検出にUnion-Findを使用します。ネットワーク設計とクラスタリングに不可欠です。

開始頂点から木を成長させることで最小全域木（MST）を見つけます。常に木の頂点と外部の頂点を接続する最小重み辺を追加します。効率的な辺選択に優先度付きキューを使用します。密なグラフに理想的です。

有向非巡回グラフ（DAG）の頂点を、すべての辺u→vについてuがvの前に来るように順序付けます。DFSベースのアプローチを使用します。依存関係解決、ビルドシステム、コーススケジューリングに不可欠です。

リンク構造によってウェブページをランク付けするGoogleのアルゴリズムです。重要度スコアを反復的に計算します。

「亀とうさぎ」アルゴリズムとしても知られ、O(1)の空間で連結リストやシーケンス内のサイクルを検出するエレガントな技術です。異なる速度で移動する2つのポインタを使用し、サイクルがあれば最終的に出会います。無限ループの検出、グラフ構造の分析、データ整合性の検証に不可欠です。

負の重みを処理し、負のサイクルを検出する単一始点最短経路アルゴリズムです。すべての辺をV-1回緩和して、負の重みでも正しい距離を保証します。通貨アービトラージ検出、様々なコストでのネットワークルーティング、ダイクストラ法が失敗する状況に不可欠です。速度を柔軟性と交換します。

O(V³)時間ですべての頂点ペア間の距離を計算する全ペア最短経路アルゴリズムです。エレガントな3行のコアロジックで動的計画法を使用します。負の重みを処理し、推移閉包を提供します。密なグラフ、ネットワーク分析、すべてのペア間距離が必要な場合に理想的です。

重みの昇順で辺を追加し、Union-Findを使用してサイクルを避けることで最小全域木を構築する貪欲アルゴリズムです。疎なグラフに対して時間計算量O(E log E)で効率的です。ネットワーク設計、クラスタリング、近似アルゴリズム、貪欲正当性証明の理解に応用されます。

木を新しい頂点に接続する最も安い辺を繰り返し追加することで最小全域木を成長させる貪欲アルゴリズムです。O(E log V)時間で効率を実現するために優先度付きキューを使用します。密なグラフやネットワークブロードキャスト、回路設計などのリアルタイムアプリケーションに適しています。

文字列内の効率的なパターンマッチングのためのKnuth-Morris-Prattアルゴリズムです。失敗関数（LPS配列）を使用して不要な比較をスキップし、O(n+m)の時間計算量を達成します。テキスト検索、DNA配列分析、盗作検出に不可欠です。

悪い文字ヒューリスティックと良い接尾辞ヒューリスティックを使用した効率的な文字列検索アルゴリズムです。パターンを右から左に比較し、不一致時に大きなジャンプを可能にします。実際にはサブリニア時間を達成し、最速の文字列マッチングアルゴリズムの1つです。

スカラー乗算の数を最小化するために行列の連鎖を括弧でくくる最適な方法を見つけます。CLRSの第15章の古典的な動的計画法の問題です。

動的計画法を使用して冗長な計算を避けながらフィボナッチ数を効率的に計算します。メモ化の力を示し、指数時間の再帰的解を線形時間アルゴリズムに変換します。動的計画法の概念への古典的な入門です。

2つの列に同じ順序で存在する最長の部分列を見つけます。動的計画法を使用して解テーブルを構築します。DNA配列アライメント、ファイル差分ツール（diff）、盗作検出などの応用があります。

1つの文字列を別の文字列に変換するために必要な単一文字編集（挿入、削除、置換）の最小数を計算する動的計画法アルゴリズムです。スペルチェック、DNA配列アライメント、自然言語処理の基礎です。

与えられた重さと価値を持つアイテムを選択し、重量制限内で総価値を最大化する古典的な動的計画法の問題です。各アイテムは一度だけ取ることができます（0/1）。リソース配分、ポートフォリオ最適化、貨物積載に応用されます。

すべての要素が昇順である最長の部分列を見つけます。古典的な動的計画法の問題です。

O(n)時間で最大の合計を持つ連続部分配列を見つけるエレガントな動的計画法アルゴリズムです。各ステップで現在の部分配列を拡張するか新しいものを開始するかを決定することで、貪欲法とDPの原則を組み合わせます。株式利益の最適化、信号処理、DP最適化技術の理解に不可欠です。

目標金額を作るために必要な最小のコイン数を見つける古典的な動的計画法の問題です。解がより小さい金額の解に依存する最適部分構造を示します。金融システム、自動販売機、リソース配分の最適化で広く適用されています。

文字列を回文部分文字列に分割するために必要な最小カット数を見つける動的計画法の問題です。DPを使用してどの部分文字列が回文かを事前計算し、最適なカットを見つけます。テキストセグメンテーション、DNA配列分析、文字列最適化問題に応用されます。

N個のチェスのクイーンをN×Nのチェス盤に、どのクイーンも他のクイーンを脅かさないように配置します。古典的なバックトラッキングアルゴリズムです。

合成数を繰り返しマークすることでnまでのすべての素数を見つけます。キレネのエラトステネス（紀元前276-194年頃）にちなんで名付けられました。

各数がその真上の2つの数の合計である二項係数の三角配列です。ブレーズ・パスカル（1623-1662）にちなんで名付けられましたが、数世紀前から数学者に知られていました。二項展開、組合せ論、フィボナッチ数との関連を含む美しい数学的パターンを示します。

紀元前300年頃の古代アルゴリズムで、2つの整数の最大公約数を効率的に計算します。GCD(a, b) = GCD(b, a mod b)という原理に基づいています。継続的に使用されている最も古いアルゴリズムの1つで、数論、暗号学、分数の簡約化の基礎を形成しています。

ユークリッドの互除法を拡張して、ベズーの等式ax + by = GCD(a, b)を満たす整数xとyを見つけます。GCDを計算するだけでなく、線形結合の係数も見つけます。モジュラー算術、RSA暗号、線形ディオファントス方程式の解法の基礎となります。

データをk個のクラスタに分割するための基本的な教師なし機械学習アルゴリズムです。点を最も近いセントロイドに繰り返し割り当て、セントロイドの位置を更新します。顧客セグメンテーション、画像圧縮、探索的データ分析で広く使用されています。

共通のプレフィックスを共有することで文字列を効率的に格納するツリーベースのデータ構造です。ルートからリーフへの各パスは単語またはキーを表します。オートコンプリート、スペルチェック、IPルーティングテーブル、辞書実装で優れており、キーの長さmに対してO(m)の操作を実現します。

木の中で2つの与えられたノードの祖先である最も深いノードを見つけます。計算生物学（種の進化）、ネットワークルーティング、バージョン管理システムでの応用を持つ木クエリの基本操作です。様々なアルゴリズムが異なる時間-空間のトレードオフを提供します。

1962年にAdelson-VelskyとLandisによって発明された最初の自己平衡二分探索木です。回転を通じて高さのバランスを維持し、O(log n)の操作を保証します。赤黒木よりも厳格なバランシングは、データベースやファイルシステムなどの検索が多いアプリケーションに理想的です。

重複しない活動の最大数を選択します。常に最も早く終了する活動を選ぶ古典的な貪欲アルゴリズムです。