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

• ### アルゴリズム1: 素早く並べ替える

急速排列は,トニー・ホールが開発した排列アルゴリズムである.平均的な状況では,n個の項目を排列するにはΟ[nlogn]回が必要である.最悪の状況ではΟ[n]回が必要であるが,この状況は一般的ではない.実際,急速排列は,通常,他のΟ[nlogn]アルゴリズムよりも明らかに速い,なぜなら,その内部ループ (innerloop) は,ほとんどのアーキテクチャで非常に効率的に実現できるからである.

素早く並べ替えるには,Divideandconquer (分割と征服) の策略を用いて,1つの連続したリストを2つの子連続したサブリストに分割する.

アルゴリズムのステップ:

• 1 列からピボットと呼ばれる要素を選びます.

• 1. 列を並べ替え,基数より小さい要素はすべて基数の前に配置し,基数より大きい要素はすべて基数の後ろに配置する.この区画の退出後に,この基数は列の真ん中に位置する.これは区画 (partition) 操作と呼ばれる.

• 3 ,再帰的に ((recursive) 基値要素より小さい子数列と基値要素より大きい子数列を並べます.

  累乗の最底辺は,数列の大きさが0か1である,つまり,常に順序が付けられているということである.常に累乗するにもかかわらず,このアルゴリズムは常に退出する,なぜなら,毎回のイテレーションで,少なくとも1つの要素をその最後の位置に置くからである.

• ### アルゴリズムII: スタックソートアルゴリズム

ハイプソート (Heapsort) は,このデータ構造を利用して設計された並び算法である. ハイプソートは,ほぼ完全な二叉木の構造であり,同時に,ハイプソートの性質を満たす:すなわち,子ノードのキー値またはインデックスは,常にその父ノードより小さい (または大きい) である.

堆積物の並べ替えの平均時間的複雑さはΟ ((nlogn) 。

アルゴリズムのステップ:

• H スタックを作成します.[0..n-1]

• 2 スタックヘッド (最大値) とスタック尾を交換する

• 3 スタイルのサイズを1に縮小し,shift_down (((0) を呼び出し,新しい配列の頂点のデータを適切な位置に調整する

• 4 ステップ 2 を繰り返して, スタックのサイズが 1 になるまで

• アルゴリズム3:帰帰順

合併ソート (Mergesort,台湾訳:合併ソート) は,合併操作に基づいた有効な排列アルゴリズムである.このアルゴリズムは,分割法 (DivideandConquer) を採用した非常に典型的なアプリケーションである.

アルゴリズムのステップ:

• 1. 要求空間を,その大きさを2つの既に排列された序列の和にして,その空間は合併後の序列を格納するために使用される

• 2 開始位置を2つの指針で設定し,それぞれ2つの順序の開始位置に設定する

• 3 指針が指す2つの要素を比較し,相対的に小さい要素を合体空間に入れて,指針を次の位置に移動する

• 1. ステップ3を繰り返して,指針が列の末尾に到達するまで

• 5 ほかの列の残りの要素をすべて 結合列の尾に直接コピーする

• アルゴリズム4:二分探求アルゴリズム

二分探求アルゴリズム (英: binary search algorithm) は,順序付けの配列の中で特定の要素を探す検索アルゴリズムである. 検索プロセスは配列の中間要素から始まり,中間要素が正しかったら検索プロセスは終了する. 特定の要素が中間要素より大きいまたは小さい場合,配列の中間要素より大きいまたは小さい半分から検索し,最初と同じように中間要素から比較を開始する. あるステップで数列が空である場合は,代表は見つからない. この検索アルゴリズムは,比較ごとに検索範囲を半分に絞り込む. 折り畳み検索は,検索領域を半分に減らし,複雑さは ((Οlogn) になる.

• ### アルゴリズム5:BFPRT (線形検索アルゴリズム)

BFPRTアルゴリズムは,あるn個の要素の序列からk大 (k小) の要素を選び,巧妙な分析によって,BFPRTは最悪の場合でも線形時間的複雑さを保証できる.このアルゴリズムの考え方は,急速ソートメントの考え方に似ており,もちろん,最悪の場合でも,アルゴリズムは,o (n) の時間的複雑さを達成できるようにするために,5人のアルゴリズム作者が精巧な処理を行った.

アルゴリズムのステップ:

• 1,n個の要素を5つのグループごとに,n/5 (上限) グループに分割する.

• 2 グループごとに中位数を取り出し,任意の排列方法,例えば挿入排列

• 1. 繰り返し呼び出すselectionアルゴリズムは,前のステップで求められたすべての中位数の中位数を探し,xに設定し,偶数の中位数がある場合,中位数の小さいものを選択するように設定する.

• 4 , 配列をxで分割すると,xより小さい数はkで,xより大きい数はn-kである.

• 5 ,i==kであれば,x を返し;ikであれば,x より大きい要素の i-k 番目の最小要素をリクエストする.

  終止条件:n=1時,返されるのはi小元素である。

• アルゴリズム6:DFS (深度優先検索)

深度優先検索アルゴリズム (Deepth-First-Search) は,検索アルゴリズムの一種である。それは,木の深さに沿って木のノードを巡り,できるだけ深い検索木の分岐を巡る。ノードvのすべての辺が探求されたとき,検索は,発見されたノードvの辺の開始のノードに戻される。この過程は,発見された源のノードから到達できるすべてのノードまで続けられる。もしまだ発見されていないノードが存在するならば,その中の1つを源のノードとして選択し,上記のプロセスを繰り返す.この過程は,すべてのノードがアクセスされるまで繰り返される。DFSは,盲目検索の類である.

ディーププライオリティ検索は,図解における古典的なアルゴリズムである.ディーププライオリティ検索アルゴリズムは,対象図の対応する拓並列表を生成し,拓並列表を使用すると,最大経路問題などの多くの関連する図解問題を簡単に解決することができる.DFSアルゴリズムの実装を補助するために,一般的に,堆積データ構造を使用する.

グラフのステップを優先して行きます.

• 1 頂点Vへのアクセス

• 2 図の未訪問の隣接接点から,図を深度優先して巡る.図とvの経路が一致する頂点まで巡る.

• 1. このタイムマップの頂点がまだ訪問されていない場合,訪問されていない頂点から始まり,図のすべての頂点が訪問されるまで,再び深度優先巡回を行います.

  ナイジェリアでは,女性を男性に比べると,男性が女性を男性に比べると,女性が男性に比べると,男性が女性に比べると,男性が女性に比べると,男性に比べると,女性に比べると,男性に比べると,男性に比べると,女性に比べると.

  DFSは,アクセス図のある頂点vから始め,vから発足し,その隣接頂点w1にアクセスし,次にw1から発足し,w1と隣接しているが訪問されていない頂点w2にアクセスし,次にw2から発足し,同様の訪問を行います. …こうして,すべての隣接頂点が訪問された頂点uに到達するまで続けます.

  次に,前回訪問した頂点に戻り,訪問されていない他の隣接頂点があるかどうかを確認します. ある場合は,この頂点にアクセスし,その後,この頂点から出発し,前述の同様の訪問を行います.

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

幅優先検索アルゴリズム (Breadth-First-Search) は,グラフ検索アルゴリズムである.簡潔に言えば,BFSは,ルートノードから始まり,木 (図) の幅に沿って木 (図) を横断するノードである.すべてのノードがアクセスされた場合,アルゴリズムは停止する.BFSは,盲目検索の類である.BFSアルゴリズムは,一般的に配列データ構造を使用して,BFSアルゴリズムを実装する.

アルゴリズムのステップ:

• まず,ルートノードを列に入力します.

• 2 列から最初のノードを取り出し,それがターゲットであるかどうかをチェックする

  ターゲットが見つかったら,検索を終了し,結果を返信します. 直接の子ノードをクエイトに追加します.

• 3 列が空である場合,図全体がをチェックしたことを示し,図に検索したい対象がないことを意味します. 検索を終了し,返信がターゲットを見つけることができなかったことを意味します.

• 4 ステップ2を繰り返す

• アルゴリズム8: ディジクストラ アルゴリズム

ディクストラアルゴリズムは,オランダのコンピュータ科学者イズヘル・ディクストラによって提唱された. ディコスチャーは,非負の有権図の単元最短経路問題を解くために幅優先検索を使用し,アルゴリズムは最短経路の樹を最終的に得ている. このアルゴリズムは,路由アルゴリズムまたは他の図アルゴリズムのサブモジュールとしてよく使用されます.

このアルゴリズムの入力には,重量のある方向図Gと,G内の源頂点Sが含まれている.Vは,G内のすべての頂点の集合を表す.各図の辺は,二つの頂点によって形成された順序要素の対である.u,vは,頂点uからvまでの経路がつながっているを表す.Eは,G内のすべての辺の集合を表す.辺の重量は,重量関数w:E→によって表される.[定義する.

したがって,w(u,v) は頂点uから頂点vまでの非負の重量(weight) である.辺の重さは2つの頂点の間の距離として考えることができる.任意の2点間の経路の重さは,その経路上のすべての辺の重量の合計である.Vには頂点sとtがあることが知られているが,Dijkstraアルゴリズムは,sからtまでの最小重量経路 (例えば,最短の経路) を見つけることができる.このアルゴリズムは,グラフの中で,頂点sから他のどの頂点までの最短の経路も見つけることができる.負の重量を含まない方向図に対して,Dijkstraアルゴリズムは,現在知られている最も速い単一の経路アルゴリズムである.

アルゴリズムのステップ:

• 1 初期時 S={V0},T={残りの頂点},T 中頂点の対応距離値 ,d ((V0,Vi) が存在すると,の弧上の重量となる. が存在しない場合,d (V0,Vi) は∞である.

• 1. Tから距離が最小の頂点Wを選択し,Sに属さない.

• 3 ,残りのTの頂点の距離値を修正する: 中央の頂点としてWを加え,V0からViまでの距離値を短縮すると,この距離値を修正する

  ステップ2と3をSにすべての頂点を含めるまで,つまりW=Viまで繰り返す.

• アルゴリズム9:ダイナミックプランニング

ダイナミックプログラミング (Dynamicprogramming) は,数学,コンピュータ科学,経済学において,原始問題を比較的単純な子問題に分解することによって複雑な問題を解く方法である.ダイナミックプログラミングは,重複子問題と最適子構造の性質を持つ問題によく適用され,ダイナミックプログラミング方法は,単純解法よりもはるかに時間がかかりません.

ダイナミック・プランニングの背後にある基本的考えは極めてシンプルである.一般的に,ある問題を解くには,その異なる部分を解く必要がある (即子問題),そして子問題の解き方を組み合わせて,元の問題の解き方を得ている.通常,多くの子問題は非常に似通っているため,ダイナミック・プランニング法では,それぞれの子問題を一度だけ解くことを試み,計算量を減らす:ある子問題の解き方が解き出されると,それを記憶して保存し,次回同じ子問題を解く必要のあるときに直接表記する.このやり方は,重複子問題の数が入力に関するスケールインデックスの増加に際して特に有用である.

背負った荷物の問題です.

アルゴリズムのステップ:

1. 最適子構造特性.問題の一番良い解に含まれる子問題の解も最適であるならば,その問題を最適子構造特性 (すなわち,最適化原理を満たす) と言う. 最適子構造性質は,動的計画アルゴリズムの問題解決に重要な手がかりを提供する.

2 ,子問題重複性 〔子問題重複性〕とは,リクリエーション・アルゴリズムで上から下へと問題を解くとき,毎回発生する子問題は必ずしも新しい問題ではなく,いくつかの子問題は繰り返し計算される 〔ダイナミック・プランニング・アルゴリズム〕は,この子問題の重複性を利用して,各子問題に対して1回しか計算せず,その計算結果を表に保存し,すでに計算された子問題を再び計算する必要があるときは,表で単純に結果を一目にして,高効率を得ることである.

• ### アルゴリズム10: 素朴なベーイズ分類アルゴリズム

素朴ベイエス分類アルゴリズムは,ベイエス定理に基づく単純な確率分類アルゴリズムである.ベイエス分類の基礎は,確率推論である.つまり,様々な条件が存在し,その確率のみが知られていれば,推論と意思決定のタスクをどのように遂行するかである.確率推論は,決定推論と対称である.そして,素朴ベイエス分類器は,サンプルの各特征が他の特征とは関係がないという独立仮定に基づいている.

素朴ベーイズ分類器は精密な自然確率モデルに依存し,監督学習のサンプル集中で非常に良い分類効果を得ることができる.多くの実用的なアプリケーションでは,素朴ベーイズモデルのパラメータは,最大近似推定方法を使用して推定される.つまり,素朴ベーイズモデルは,ベーイズ確率やベーイズモデルを使用せずに動作する.

これらの単純思考と単純化されすぎた仮定にもかかわらず,シンプルなベーイズ分類者は,多くの複雑な現実状況において,かなり良い効果を上げることができる.