プログラマーが知っておくべき10の基本的な実用的なアルゴリズムとその説明

[[128752]]

アルゴリズム1: クイックソートアルゴリズム

クイックソートは、Tony Hall によって開発されたソートアルゴリズムです。平均すると、n 個の項目をソートするには O(n log n) 回の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、これは一般的ではありません。実際、クイック ソートは、その内部ループがほとんどのアーキテクチャで効率的に実装できるため、他の O(n log n) アルゴリズムよりも大幅に高速になることがよくあります。

クイックソートでは、分割統治戦略を使用してリストを 2 つのサブリストに分割します。

アルゴリズムの手順:

1 シーケンスから「ピボット」と呼ばれる要素を選択します。

2 シーケンスを並べ替えて、基本値より小さいすべての要素をベースの前に置き、基本値より大きいすべての要素をベースの後ろに置きます (同じ数字がどちらの側にあってもかまいません)。このパーティションを抜けると、ベンチマークはシリーズの途中になります。これをパーティション操作と呼びます。

3 基本値より小さい要素の部分シーケンスと基本値より大きい要素の部分シーケンスを再帰的にソートします。

再帰の最後のケースは、シーケンスのサイズが 0 または 1 の場合であり、これは常にソートされていることを意味します。再帰は継続されますが、各反復で少なくとも 1 つの要素を最適な位置に移動するため、アルゴリズムは常に終了します。

#p#

アルゴリズム2: ヒープソートアルゴリズム

ヒープソートとは、ヒープ データ構造を使用して設計されたソート アルゴリズムを指します。スタックは、完全な二分木を近似し、スタックの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。

ヒープソートの平均時間計算量はΟ(nlogn)です。

アルゴリズムの手順:

1.ヒープH[0..n-1]を作成します。

2. ヒープ先頭 (最高値) とヒープ末尾を交換します。

3. ヒープのサイズを1減らし、shift_down(0)を呼び出して、新しい配列の先頭データを対応する位置に調整します。

4. ヒープ サイズが 1 になるまで手順 2 を繰り返します。

#p#

アルゴリズム3: マージソート

マージソート（Merge sort、台湾ではmerge sortと訳される）は、マージ操作に基づく効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。

アルゴリズムの手順:

1. ソートされた 2 つのシーケンスの合計サイズを持つスペースを申請します。このスペースは、マージされたシーケンスを格納するために使用されます。

2. 2 つのソートされたシーケンスの開始位置を初期位置とする 2 つのポインタを設定します。

3. 2 つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインタを次の位置に移動します。

4. ポインタがシーケンスの末尾に到達するまで手順 3 を繰り返します。

5. 他のシーケンスの残りの要素をすべて、結合されたシーケンスの末尾に直接コピーします。

#p#

アルゴリズム4: 二分探索アルゴリズム

バイナリ検索アルゴリズムは、順序付けられた配列内の特定の要素を見つけるための検索アルゴリズムです。検索プロセスは、配列の中央の要素から始まります。中央の要素がまさに検索対象の要素である場合、検索プロセスは終了します。特定の要素が中央の要素より大きいか小さい場合は、中央の要素より大きいか小さい配列の半分で検索され、最初と同様に中央の要素から比較が開始されます。特定のステップで配列が空の場合、配列が見つからないことを意味します。この検索アルゴリズムは、比較ごとに検索範囲を半分に減らします。バイナリ検索では、検索領域が毎回半分に削減され、その時間計算量は O(logn) です。

アルゴリズム 5: BFPRT (線形探索アルゴリズム)

BFPRT アルゴリズムによって解決される問題は非常に古典的なもので、n 個の要素のシーケンスから k 番目に大きい (k 番目に小さい) 要素を選択するというものです。巧妙な分析により、BFPRT は最悪の場合でも時間の複雑さが線形であることを保証できます。このアルゴリズムの考え方はクイックソートの考え方に似ています。もちろん、最悪の場合でもアルゴリズムが o(n) の時間計算量を達成できるようにするために、5 人のアルゴリズム作成者は微妙な調整を行いました。

アルゴリズムの手順:

1. n 個の要素を 5 個ずつ n/5 (上限) のグループに分割します。

2. 各グループの中央値を取得し、挿入ソートなどの任意の方法を使用して並べ替えます。

3. 選択アルゴリズムを再帰的に呼び出して、前のステップですべての中央値の中央値を見つけ、それを x に設定し、中央値が偶数の場合は、中央の小さい方を選択するように設定します。

4. x を使用して配列を分割します。x 以下の要素の数を k、x より大きい要素の数を nk とします。

5. i==k の場合は x を返します。ik の場合は、x より大きい要素の中から ik 番目に小さい要素を再帰的に検索します。

終了条件: n=1 の場合、返される要素は i 番目の小さな要素です。

#p#

アルゴリズム 6: DFS (深さ優先探索)

深さ優先探索アルゴリズムは、検索アルゴリズムの一種です。ツリーの深さに沿ってツリーのノードをトラバースし、ツリーの枝を可能な限り深く検索します。ノード v のすべてのエッジが探索されると、検索はノード v を見つけたエッジの開始ノードに戻ります。このプロセスは、ソース ノードから到達可能なすべてのノードが検出されるまで続行されます。まだ検出されていないノードがある場合は、そのうちの 1 つがソース ノードとして選択され、上記のプロセスが繰り返されます。すべてのノードが訪問されるまで、プロセス全体が繰り返されます。 DFS はブラインド検索です。

深さ優先探索はグラフ理論における古典的なアルゴリズムです。深さ優先探索アルゴリズムは、対象グラフの対応する位相ソート テーブルを生成できます。位相ソート テーブルを使用すると、最適パス問題など、多くの関連するグラフ理論の問題を簡単に解決できます。ヒープ データ構造は通常、DFS アルゴリズムの実装を支援するために使用されます。

深さ優先トラバーサルグラフアルゴリズムの手順:

1. 頂点 v にアクセスします。

2. v の未訪問の隣接点から始めて、v に接続するパスを持つグラフ内のすべての頂点が訪問されるまで、グラフの深さ優先走査を実行します。

3. グラフ内にまだ訪問されていない頂点がある場合は、訪問されていない頂点から開始し、グラフ内のすべての頂点が訪問されるまで深さ優先走査を再度実行します。

上記の説明は抽象的かもしれないので、例を見てみましょう。

グラフ内の開始頂点 v を訪問した後、DFS は v から開始してその隣接する頂点 w1 のいずれかを訪問します。次に w1 から開始して、w1 に隣接しているがまだ訪問されていない頂点 w2 を訪問します。次に w2 から開始して同様の訪問を実行し、隣接する頂点が訪問済みの頂点 u に到達するまでこれを繰り返します。

次に、前回訪れた頂点に 1 ステップ戻って、まだ訪れていない他の隣接頂点があるかどうかを確認します。そうであれば、この頂点を訪問し、次にこの頂点から開始して上記と同様の訪問を実行します。そうでない場合は、1 ステップ戻って再度検索します。接続されたグラフ内のすべての頂点が訪問されるまで、上記のプロセスを繰り返します。

#p#

アルゴリズム 7: BFS (幅優先探索)

幅優先探索はグラフ検索アルゴリズムです。簡単に言うと、BFS はルート ノードから開始し、ツリー (グラフ) の幅に沿ってツリー (グラフ) のノードをトラバースします。すべてのノードが訪問された場合、アルゴリズムは終了します。 BFS もブラインド検索です。キュー データ構造は通常、BFS アルゴリズムの実装を支援するために使用されます。

アルゴリズムの手順:

1. まずルートノードをキューに入れます。

2. キューから最初のノードを取得し、それがターゲットであるかどうかを確認します。ターゲットが見つかった場合、検索は終了し、結果が返されます。それ以外の場合は、まだチェックされていないすべての直接の子ノードがキューに追加されます。

3. キューが空の場合は、グラフ全体がチェックされたことを意味します。つまり、グラフ内に検索するターゲットはありません。検索を終了し、「ターゲットが見つかりません」を返します。

4. 手順 2 を繰り返します。

#p#

アルゴリズム8: ダイクストラアルゴリズム

ダイクストラのアルゴリズムは、オランダのコンピュータ科学者エドガー・ダイクストラによって提案されました。ダイクストラ アルゴリズムは、幅優先探索を使用して、非負の重みを持つ有向グラフの単一ソース最短経路問題を解決し、最終的に最短経路ツリーを取得します。このアルゴリズムは、ルーティング アルゴリズムや他のグラフ アルゴリズムのサブモジュールとしてよく使用されます。

アルゴリズムの入力は、重み付き有向グラフ G と G 内のソース頂点 S で構成されます。 G 内のすべての頂点の集合を V で表します。グラフ内の各エッジは、2 つの頂点によって形成される要素の順序付きペアです。 (u, v) は頂点 u から v へのパスがあることを意味します。 G 内のすべての辺の集合を E で表し、辺の重みは重み関数 w: E → [0, ∞] によって定義されます。したがって、w(u, v)は頂点uから頂点vへの非負の重みです。エッジの重みは、2 つの頂点間の距離と考えることができます。任意の 2 点間のパスの重みは、そのパス上のすべてのエッジの重みの合計です。 V に頂点 s と t がある場合、ダイクストラのアルゴリズムは s から t への最も重みの高いパス (たとえば、最短パス) を見つけることができます。このアルゴリズムは、グラフ内の頂点 s から他の任意の頂点までの最短経路を見つけるためにも使用できます。負の重みのない有向グラフの場合、ダイクストラのアルゴリズムは、知られている中で最も高速な単一ソース最短経路アルゴリズムです。

アルゴリズムの手順:

1. 最初に、S={V0}、T={その他の頂点}とします。T 内の頂点に対応する距離値が存在する場合、d(V0,Vi) は弧の重みになります。存在しない場合は、d(V0,Vi) は∞です。

2. T から距離値が最小で S に含まれない頂点 W を選択し、それを S に追加します。

3. T内の残りの頂点の距離値を変更します。中間頂点としてWを追加すると、V0からViまでの距離値が短くなるので、この距離値を変更します。

4. すべての頂点が S に含まれるまで、つまり W = Vi になるまで、上記の手順 2 と 3 を繰り返します。

#p#

アルゴリズム9: 動的計画法アルゴリズム

動的計画法は、元の問題を比較的単純なサブ問題に分割することで複雑な問題を解決するために数学、コンピューターサイエンス、経済学で使用される手法です。 動的計画法は、重複するサブ問題や極端なサブ構造特性を持つ問題に適用できることが多く、動的計画法によって消費される時間は、単純なソリューションに比べて大幅に短くなることがよくあります。

動的プログラミングの基本的な考え方は非常にシンプルです。一般的に言えば、与えられた問題を解決するには、その問題のさまざまな部分（つまりサブ問題）を解決し、次にサブ問題の解決策を組み合わせて元の問題の解決策を得る必要があります。 多くの場合、多くのサブ問題は非常に類似しているため、動的プログラミングでは各サブ問題を 1 回だけ解決しようとして、計算量を削減します。特定のサブ問題の解決策が計算されると、その解決策はメモ化されて保存され、次回同じサブ問題の解決策が必要になったときに直接参照できるようになります。 このアプローチは、繰り返されるサブ問題の数が入力のサイズに応じて指数関数的に増加する場合に特に役立ちます。

動的計画法に関する最も古典的な問題はナップサック問題です。

アルゴリズムの手順:

1. ***サブ構造プロパティ。問題の最適解に含まれるサブ問題の解も最適である場合、その問題は最適なサブ構造特性を持っている（つまり、最適化原理を満たしている）と言います。 ***サブ構造プロパティは、動的プログラミング アルゴリズムが問題を解決するための重要な手がかりを提供します。

2. サブ問題の重複性。サブ問題の重複性は、再帰アルゴリズムを使用して問題を上から下まで解決する場合、毎回生成されるサブ問題が必ずしも新しい問題ではなく、一部のサブ問題は複数回繰り返し計算されることを意味します。動的プログラミング アルゴリズムは、サブ問題の重複特性を利用します。各サブ問題を 1 回だけ計算し、結果をテーブルに保存します。計算済みのサブ問題を再度計算する必要がある場合は、テーブル内の結果を確認するだけで済むため、効率が向上します。

アルゴリズム 10: ナイーブベイズ分類アルゴリズム

単純ベイズ分類アルゴリズムは、ベイズの定理に基づいた単純な確率分類アルゴリズムです。ベイズ分類の基礎は確率的推論であり、これはさまざまな条件の存在が不確実で、その発生確率のみがわかっている場合に推論と意思決定のタスクを完了する方法です。確率的推論は決定論的推論の反対です。単純ベイズ分類器は、サンプルの各特徴が他の特徴と無関係であると仮定する独立性の仮定に基づいています。

ナイーブベイズ分類器は正確な自然確率モデルに依存しており、教師あり学習のサンプル セットで非常に優れた分類結果を達成できます。多くの実際のアプリケーションでは、ナイーブ ベイズ モデルのパラメータ推定に *** 尤度推定法が使用されます。つまり、ナイーブ ベイズ モデルは、ベイズ確率やベイズ モデルを使用せずに機能します。

これらの素朴な考え方と単純化しすぎた仮定にもかかわらず、ナイーブベイズ分類器は、多くの複雑な現実世界の状況において依然として非常に優れた結果を達成できます。