速序は,トニー・ホールによって開発された並べ替えアルゴリズムである.平均的な場合,並べ替え n 個の項目は 0 (nlogn) 回の比較が必要である.最悪の場合は 0 (n2) 回の比較が必要である.しかし,このような状況は稀である.実際,速序は,他の O (nlogn) アルゴリズムよりも明らかに速く,その内部ループがほとんどのアーキテクチャで非常に効率的に実現できるため,通常,速序である.
快速排列は,分割と征服の策略を使用して,リストを2つのサブリストに分けます.
アルゴリズムのステップ:
1、数列から要素を選び,ピボットと呼ばれる.
2、再排列数列,基値より小さいすべての要素が基値の前に置かれ,基値より大きいすべての要素が基値の後ろに置かれ (同じ数値がどちらにも行ける).この区画を退去した後,基値は数列の中央に置かれます.これは区画操作と呼ばれる.
3,回帰的に (recursive) 基値要素より小さい子列と基値要素より大きい子列を順序付けする.
回帰の最も基本的なケースは,数列の大きさは0または1である,つまり常に順序が整っている. 繰り返し回帰しているにもかかわらず,このアルゴリズムは常に退出する,なぜなら,毎回の繰り返しの (i) 間に,少なくとも1つの要素をその最後の位置に置くからである.
ハープソート (Heapsort) とは,ハープのようなデータ構造を利用して設計されたソートアルゴリズムである.ハープは,ほぼ完全に二重木の構造であり,同時にハープの性質を満たす.すなわち,子ノードのキー値またはインデックスは常にその親ノードより小さい (または大きい) である.
堆列の順序の平均時間複雑性はΟ (nlogn) である.
アルゴリズムのステップ:
列を H [0...n-1] に変換します.
2 スタックヘッド (最大値) とスタック尾を入れ替える
3、スタックを1に縮小し,shift_down ((0) を呼び出し,新しい配列上のデータを適切な位置に調整する.
ステップ2を繰り返します.
Mergesortは,配列操作に基づいた有効な配列アルゴリズムである.このアルゴリズムは,分割と征服の非常に典型的な応用である.
アルゴリズムのステップ:
1, 配列を2つの配列の合計に等しくするスペースを申請し,その配列を統合した後に保存するスペースを使用する.
2、2つの指針を設定し,それぞれが2つの順序化された順序の開始位置である.
3, 2 つの指針が指している要素を比較し,比較的小さい要素を組み合わせスペースに入れ,指針を次の位置に移動します
4 ステップ3を繰り返す. 一つの指針が序列の末尾に達するまで.
5、他の列の残った要素をすべて直接結合列尾にコピーする
二次要位検索アルゴリズムとは,順序ある配列内の特定の要素を検索するアルゴリズムである. 検索プロセスは,配列の中間要素から始まり,中間要素がまさに探すべき要素である場合,検索プロセスは終了する.特定の要素が中間要素よりも大きいまたは小さい場合,配列のその半分から検索し,また,最初と同じように中間要素から比較する.
BFPRTアルゴリズムは,あるnつの要素の連続からk番目の (kの小さい) 要素を選んで,巧妙な分析によって,最悪の場合でも線形時間複雑性を維持することを保証する典型的な問題を解決する.このアルゴリズムの考え方は,速序の考え方に類似しており,もちろん,最悪の場合でもアルゴリズムは o (n) の時間複雑性を維持できるように,5人の作者が精巧な処理を行った.
アルゴリズムのステップ:
1、n要素を5つのグループに5つずつ n/5 (上限) グループに分割します.
2、各組の中位数を取り出す,任意の順序方法,例えば順序を挿入する.
3, 回帰的な呼び出し選択アルゴリズムは,前のステップのすべての中位数の中位数を見つけ,x に設定され,偶数の中位数の場合,中間の小さいものを選択するように設定される.
4, x を用いて配列を割るには,x に等しい数よりも小さい項をk とし,x より大きい項をn − k とする.
5, i==k で x を返します. i
終了条件:n=1では,i小要素が返されます.
深い優先検索アルゴリズム (Depth-First-Search) は,木に沿って木のノードを深く横切る検索アルゴリズムの一種である.ノードvのすべての辺が探検されたとき,検索は発見されたノードvの端の開始ノードに戻る.このプロセスは,ソースノードからアクセス可能なすべてのノードが発見されるまで続きます.もしまだ発見されたノードがない場合は,そのうちの1つをソースノードとして選択し,すべてのノードがアクセスされるまでこのプロセスを繰り返します.DFSは盲目検索です.
深層優先検索は,図解理論における古典的なアルゴリズムで,深層優先検索アルゴリズムを使用して,目標図の対応するトロップリストを生成することができる.トロップリストを使用して,最大経路問題などの多くの関連図解学の問題を簡単に解決することができる.一般的に,堆積データ構造を使用してDFSアルゴリズムを実装するのに役立ちます.
グラフアルゴリズムのステップを詳細に優先します.
1 頂点vにアクセスする
2,次々にvのアクセスされていない近隣接点から開始して,図の深度優先移動を行います.図の頂点とvの経路が一致するまでアクセスします.
3. このとき,図の頂点がまだアクセスされていない場合は,アクセスされていない頂点から,すべての頂点がアクセスされるまで,深度優先クローニングを再開します.
この例は,以下のような例を挙げると,上記の記述は抽象的かもしれません.
DFSは,アクセス図のいずれかの頂点vから開始して,vから出発し,その隣接する頂点w1を任意にアクセスし,その後w1から出発し,w2が隣接する,しかしまだアクセスされていない頂点w1にアクセスし,それからw2から再び出発し,同様のアクセスを行います...,そして,すべての隣接する頂点がアクセスされた頂点uに到達するまで続きます.
次に,前回訪れた頂点に戻り,他の未訪の隣接頂点があるかどうかを確認します.もしある場合は,この頂点にアクセスし,その後,この頂点から出発して,前述のような訪問を行います.もしない場合は,再びステップに戻り,検索を行います.接続図のすべての頂点が訪問されるまで上記のプロセスを繰り返します.
幅優先検索アルゴリズム (BFS) は,グラフ検索アルゴリズムの一種である.簡単に言えば,BFSはルーツノードから始まり,木の幅に沿って木のノードを横切るものである.すべてのノードがアクセスされた場合,アルゴリズムは停止する.BFSはまた盲目検索である.一般的なキューツデータ構造を使用してBFSアルゴリズムの実現を支援する.
アルゴリズムのステップ:
1、最初に,ルートノードを列に入れます.
2、列から最初のノードを取り出して,それが目標かどうかチェックします.
目標が見つかったら,検索を終了し,結果を送信します. チェックしていないすべての直接子ノードを列に追加します.
3、列が空である場合,図全体で
4 ステップ2を繰り返します.
ディクストラ算法 (英語版) は,オランダのコンピュータ科学者エッゼル・ディクストラによって提案されたものです. ディクストラ算法では,非負の力を持つ向図の単源の最短経路問題を解くために,幅優先検索を使用して,最短経路の木を得ます.このアルゴリズムは,通常ルータリングアルゴリズムまたは他のグラフアルゴリズムの子モジュールとして使用されます.
このアルゴリズムのインプットは,重みのある有向図 G と,G の源頂点 S を含む. V は G のすべての頂点の集合を表す. 各図の辺は,二つの頂点が形成した順序元素対である. u, v は,頂点 u から v までの経路が接続されていることを表す. E は G のすべての辺の集合を表す. 辺の重さは重み関数 w:E→[0,∞] によって定義される.
したがって,w (u,v) は頂点uから頂点vまでの非負の重量である.側重量は2つの頂点間の距離として考えることができる.両点間の経路の重量は,その経路上のすべての側重量の合計である. Vには頂点sとtがあることが知られており,Dijkstra アルゴリズムがsからtまでの最小重量経路を見つけることができる.このアルゴリズムはまた,図の中で,頂点sから他のどの頂点への最短経路を見つけることができる.非負の重量を持つ向向図では,Dijkstra アルゴリズムは現在知られている最も速い単源の最短経路算法である.
アルゴリズムのステップ:
1,初期時刻 S={V0},T={残った頂点},Tの中間の頂点に対応する距離値
2、Tから最小距離の値である頂点Wを選び,Sに含まれない.
3, 残りのTの頂点間の距離値を変更する: Wを中間頂点として追加すると,V0からViまでの距離値が縮小される.
上のステップ2,3を繰り返します. Sにすべての頂点が含まれているまで,つまり W=Vi
ダイナミックプログラミング (Dynamic programming) は,数学,コンピュータ科学,経済学において,基本的な問題を比較的単純な子問題に分解して複雑な問題を解く方法として用いられる.ダイナミックプログラミングは,重複子問題と最適子構造性のある問題に対してしばしば適用され,ダイナミックプログラミング方法は,単純な方法よりもはるかに時間がかかる.
ダイナミック・プランニングの基本的な考え方は非常にシンプルである. 一般的に,ある問題を解くには,その分を解く必要がある (即ち子問題),また,子問題を再結合して解決し,元の問題を解く必要がある.多くの子問題が非常に類似しているため,ダイナミック・プランニングは,各子問題を一度だけ解くことを試み,計算量を削減する.ある子問題の解が計算されたら,それをメモリ化して保存し,次回同じ子問題を解く必要があるときに直接チェックする.この方法は,重複子問題の数が入力量について指数的に増加するときに特に有用である.
ダイナミック・プランニングの最も古典的な問題はバックパックの問題です.
アルゴリズムのステップ:
1,最適子構造性. 問題の最適解に含まれる子問題の解も最適である場合,この問題は最適子構造性 (すなわち最適化原理を満たす) を有する. 最適子構造性により,動態計画アルゴリズムの問題解決に重要なヒントが得られる.
2,子問題の重複性.子問題の重複性とは,回帰アルゴリズムで問題を上から下へと解くとき,生成される子問題は常に新しい問題ではなく,いくつかの子問題は繰り返し計算されます. ダイナミックプランニングアルゴリズムは,この子問題の重複性を利用し,各子問題に対して一度だけ計算し,その計算結果を表の中に保存し,再び計算した子問題を計算する必要があるとき,表の中で結果を単純に見ると,より効率的な結果が得られます.
朴素なベイヤス分類アルゴリズムは,ベイヤス定理に基づいた単純な確率分類アルゴリズムである.ベイヤス分類の基礎は確率推論である.つまり,様々な条件の存在が不確実であり,その可能性が認識されている場合にのみ推論と意思決定の課題をどのように完了するかである.確率推論は確定性推論に対応する.朴素なベイヤス分類は,サンプル内の各特徴が他の特性とは関係がないと仮定する独立仮説に基づいている.
朴素なベイエズ分類器は,正確な自然確率モデルに依存し,監視学習のあるサンプルセットで非常に良い分類効果を得ることができる.多くの実用的な応用では,朴素なベイエズモデル参数推定は,最も似通りの推定方法を使用し,つまり朴素なベイエズモデルはベイエズ確率またはベイエズモデルを使わずに動作する.
これらの単純な考えと過度に単純化された仮説にもかかわらず,単純なベイエズ分類器は多くの複雑な現実状況でかなり良い結果をもたらします.