トップ 10 のプログラミング アルゴリズムは、プログラマーがマスターへの道を歩むのに役立ちます

アルゴリズム 1: クイックソートアルゴリズムクイックソートは、Tony Hall によって開発されたソートアルゴリズムです。平均して、n 個の項目を並べ替えるには、O(n log n) 個の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、この状況は一般的ではありません。実際、クイックソートは、ほとんどのアーキテクチャで内部ループを効率的に実装できるため、他の Ο(n log n) アルゴリズムよりも大幅に高速であることがよくあります。 クイックソートは、分割統治戦略を使用してシーケンス (リスト) を 2 つのサブシリーズ (サブリスト) に分割します。 アルゴリズムの手順: 1 シーケンスから「ピボット」と呼ばれる要素を選択します。 2 シーケンスを並べ替えます。ピボット値より小さいすべての要素がピボットの前に配置され、ピボット値より小さいすべての要素が配置されます。はピボットの前に配置されます。大きい方がベースの後ろに配置されます (同じ番号をどちらの側にも配置できます)。このパーティションが終了すると、塩基はシーケンスの途中になります。これをパーティション操作と呼びます。 3 基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。 再帰の最も低いケースは、配列のサイズが 0 または 1 の場合、つまり、配列が常にソートされている場合です。再帰を続けますが、各反復で少なくとも 1 つの要素が最終位置に移動するため、このアルゴリズムは常に終了します。 アルゴリズム 2: ヒープソートアルゴリズムヒープソートとは、ヒープのデータ構造を使用して設計されたソートアルゴリズムを指します。スタッキングは、完全なバイナリ ツリーに近似し、スタッキングの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードより小さい (または大きい) ものです。 ヒープソートの平均時間計算量はΟ(nlogn)です。 アルゴリズムの手順: ヒープH[0..n-1]を作成しますヒープの先頭(最大値)と末尾を交換します3. ヒープのサイズを1つ減らし、shift_down( 0)、目的は、新しい配列の先頭データを対応する位置に調整することです4. ヒープのサイズが 1 になるまでステップ 2 を繰り返しますアルゴリズム 3: マージソートマージソート（マージソート、台湾語訳：マージソート）は、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法を使用する非常に典型的なアプリケーションです。 アルゴリズムの手順: 1. そのサイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します 2 つのポインターを設定し、初期位置はすでに 2 つです。並べ替えられたシーケンスの開始位置3. 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージ スペースに置き、ポインターを次の位置に移動します4.ステップ 3 特定のポインタがシーケンスの末尾に到達するまで5. 他のシーケンスの残りのすべての要素をマージされたシーケンスの末尾に直接コピーしますアルゴリズム 4: 二分探索アルゴリズム順序付けされた配列内の特定の項目を検索する方法 要素検索アルゴリズム。検索プロセスは、配列の中央の要素から開始され、中央の要素が検索対象の要素である場合、特定の要素が中央の要素より大きいか小さい場合、検索プロセスは終了します。中央の要素より大きいか小さい配列を指定し、最初と同様に中央の要素から比較を開始します。特定のステップで配列が空の場合、それは見つからないことを意味します。この検索アルゴリズムでは、比較するたびに検索範囲が半分に減ります。半探索では探索範囲が毎回半分に減り、計算量はΟ(logn)となります。 アルゴリズム 5: BFPRT (線形探索アルゴリズム) BFPRT アルゴリズムによって解決される問題は非常に古典的です。つまり、n 個の要素のシーケンスから k 番目に大きい (k 番目に小さい) 要素を選択します。賢い分析により、BFPRT は最悪の場合でも線形時間計算量を保証できます。もちろん、このアルゴリズムの考え方はクイックソートと似ていますが、最悪の場合でも時間計算量が o(n) になるように、5 人のアルゴリズム作者が絶妙な処理を行っています。 アルゴリズムの手順: 1. n 個の要素を 5 個のグループに分割し、それらを n/5 (上限) のグループに分割します。 2. 各グループの中央値を取得し、挿入並べ替えなどの並べ替え方法を使用します。 3. 選択アルゴリズムを再帰的に呼び出して、前のステップですべての中央値の中央値を見つけ、それを x に設定し、中央値が偶数の場合は、中央の小さい方を選択するように設定します。 4. x を使用して配列を分割します。x 以下の数を k とし、x より大きい数を n-k とします。 5. i==k の場合は x を返し、i終了条件: n=1のとき、小要素iを返す。 アルゴリズム 6: DFS (深さ優先検索) 深さ優先検索は、検索アルゴリズムの一種です。ツリーの深さに沿ってツリーのノードを横断し、ツリーの枝をできるだけ深く検索します。ノード v のすべてのエッジが探索されると、検索はノード v が見つかったエッジの開始ノードに戻ります。このプロセスは、ソース ノードから到達可能なすべてのノードが検出されるまで続行されます。まだ検出されていないノードがある場合は、それらの 1 つをソース ノードとして選択し、すべてのノードが訪問されるまで上記のプロセス全体を繰り返します。 DFS はブラインド検索です。 深さ優先検索は、グラフ理論の古典的なアルゴリズムです。深さ優先検索アルゴリズムを使用すると、ターゲット グラフに対応するトポロジカル ソート テーブルを生成できます。トポロジカル ソート テーブルを使用すると、関連する多くのグラフ理論の問題を簡単に解決できます。 、最大パスの問題など。ヒープ データ構造は通常、DFS アルゴリズムの実装を支援するために使用されます。 深さ優先探索グラフ アルゴリズムの手順: 1. 頂点 v を訪問します。2. v の未訪問の隣接点から開始して、グラフ内に次の頂点が存在するまで、グラフの深さ優先探索を実行します。 v に接続されたパス。すべて訪問済みです 3. この時点でまだ訪問されていない頂点がグラフ内にある場合は、未訪問の頂点から開始して、グラフ内のすべての頂点が訪問されるまで深さ優先探索を再度実行します。訪問されました。 上記の説明は比較的抽象的かもしれません: DFS は、グラフ内の特定の開始頂点 v を訪問した後、v から開始してその隣接する頂点 w1 を訪問し、次に w1 から開始して隣接する頂点を訪問します。 w1 ではなく、まだ訪問されていない頂点 w2 です。次に、w2 から開始して同様の訪問を実行し、隣接するすべての頂点が訪問された頂点 u に到達するまで同様に実行します。 次に、前回訪問したばかりの頂点に一歩戻って、まだ訪問していない隣接する頂点があるかどうかを確認します。存在する場合は、この頂点にアクセスし、この頂点から上記と同様のアクセスを実行します。存在しない場合は、1 ステップ戻って検索します。接続されたグラフ内のすべての頂点を訪問するまで、上記のプロセスを繰り返します。 アルゴリズム 7: BFS (Breadth-First Search)Breadth-First-Search は、グラフ検索アルゴリズムです。簡単に言えば、BFS はルート ノードから開始し、ツリー (グラフ) の幅に沿ってツリー (グラフ) のノードを横断します。すべてのノードにアクセスすると、アルゴリズムは中止されます。 BFS もブラインド検索です。キュー データ構造は通常、BFS アルゴリズムの実装を支援するために使用されます。 アルゴリズムの手順: 1. まずルートノードをキューに入れます。 2. キューから最初のノードを取得し、それがターゲットであるかどうかを確認します。 ターゲットが見つかった場合、検索は終了し、結果が返されます。 それ以外の場合は、まだチェックされていないすべての直接の子ノードをキューに追加します。 3. キューが空の場合は、画像全体がチェックされたことを意味します。つまり、画像内に検索対象がないことを意味します。検索を終了し、「ターゲットが見つかりません」を返します。 4. ステップ 2 を繰り返します。 アルゴリズム 8: ダイクストラのアルゴリズムダイクストラのアルゴリズムは、オランダのコンピューター科学者エドガー・ダイクストラによって提案されました。ダイクストラのアルゴリズムは、幅優先探索を使用して、非負重み付き有向グラフの単一ソース最短経路問題を解決し、最終的に最短経路ツリーを取得します。このアルゴリズムは、ルーティング アルゴリズムで、または他のグラフ アルゴリズムのサブモジュールとしてよく使用されます。 このアルゴリズムの入力には、重み付き有向グラフ G と G 内のソース頂点 S が含まれています。 V を使用して、G のすべての頂点のセットを表します。グラフ内のすべてのエッジは、2 つの頂点によって形成される要素の順序付けされたペアです。 (u, v) は、頂点 u から v に接続するパスがあることを意味します。 E を使用して G 内のすべてのエッジのセットを表し、エッジの重みは重み関数 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 からの距離値が最小である頂点 W を選択します。 S ではなく、Sを追加します。3. T の残りの頂点の距離値を変更します。W を中間頂点として追加すると、V0 から Vi までの距離値が短くなり、この距離値を変更しますすべての頂点が S に含まれるまで、つまり W=Viアルゴリズム 9: 動的計画法アルゴリズム になるまで、上記の手順 2 と 3 を繰り返します。動的プログラミングは、元の問題を比較的単純な部分問題に分解することで複雑な問題を解決するために、数学、コンピューターサイエンス、経済学で使用される手法です。動的プログラミングは、多くの場合、重複する部分問題と最適な部分構造のプロパティを伴う問題に適しています。 動的プログラミングの背後にある基本的な考え方は非常にシンプルです。大まかに言えば、特定の問題を解決するには、そのさまざまな部分 (つまり、サブ問題) を解決し、サブ問題の解決策を組み合わせて、元の問題の解決策に到達する必要があります。多くの部分問題は非常に似ていることが多いため、動的プログラミングでは各部分問題を 1 回だけ解決しようとするため、計算量が削減されます。特定の部分問題の解が計算されると、次回同じ部分問題が必要になった場合に備えて、その解が記憶され、保存されます。問題を解くときは、表を直接調べてください。このアプローチは、反復される部分問題の数が入力のサイズに応じて指数関数的に増加する場合に特に役立ちます。 動的計画法に関する最も古典的な問題は、間違いなくナップザック問題です。 アルゴリズムのステップ: 1. 最適な部分構造のプロパティ。問題の最適解に、やはり最適である部分問題の解が含まれている場合、その問題は最適な部分構造特性を備えている (つまり、最適化原理を満たしている) と言います。最適な下部構造の特性は、動的プログラミング アルゴリズムが問題を解決するための重要な手がかりを提供します。 2. 副次的な問題の重複する性質。部分問題の重複する性質は、再帰的アルゴリズムを使用して問題を上から下まで解く場合、毎回生成される部分問題が必ずしも新しい問題であるとは限らず、一部の部分問題は複数回繰り返し計算されることを意味します。動的計画アルゴリズムは、この部分問題の重複する性質を利用し、各部分問題を 1 回だけ計算し、計算された部分問題を再度計算する必要がある場合にのみその計算結果をテーブルに保存します。結果を確認するだけで効率が向上します。 アルゴリズム 10: ナイーブ ベイズ分類アルゴリズム ナイーブ ベイズ分類アルゴリズムは、ベイズの定理に基づく単純な確率分類アルゴリズムです。ベイズ分類の基礎は確率論的推論です。これは、さまざまな条件の存在が不確実で、その発生確率だけがわかっている場合に、推論と意思決定のタスクを完了する方法です。確率論的推論は決定論的推論に相当します。ナイーブ ベイズ分類器は独立性の仮定に基づいています。つまり、サンプルの各特徴が他の特徴と関連していないと仮定されます。 ナイーブ ベイズ分類器は正確な自然確率モデルに依存しており、教師あり学習のサンプル セットで非常に優れた分類結果を達成できます。多くの実際のアプリケーションでは、ナイーブ ベイズ モデルのパラメーター推定には最尤推定法が使用されます。つまり、ナイーブ ベイズ モデルは、ベイズ確率やベイズ モデルを使用しなくても機能します。 ウェブサイトのブログをフォローしていただきありがとうございます!

以上、プログラマーがマスターになるためのトップ 10 プログラミング アルゴリズムを内容の側面も含めて紹介しましたが、PHP チュートリアルに興味のある友人の参考になれば幸いです。