数学とコンピュータサイエンスでは、アルゴリズムAL-gə-ridh-əm）は、問題のクラスをどのように解決するかの明確な仕様です。 アルゴリズムは、計算、データ処理、および自動推論タスクを実行できます。
効果的な方法として、アルゴリズムは、関数を計算するための有限量の空間および時間内で明確に定義された形式言語で表現することができる。 初期状態および初期入力（おそらく空）から開始して、命令は、実行されると有限数の明確な連続状態を経て最終的に「出力」を生成し、最終終了状態で終了する計算を記述する。 ある状態から次の状態への移行は必ずしも確定的ではありません。 ランダム化アルゴリズムと呼ばれるアルゴリズムの中には、ランダム入力を組み込んだものもあります。
アルゴリズムの概念は何世紀にもわたって存在しており、この概念の使用はギリシアの数学者、例えばエラトステネスとユークリッドのアルゴリズムの篩に帰せられる。 アルゴリズムという用語自体は、9世紀の数学者MuḥammadibnMūsāal’Khwārizmī、latinized ‘Algoritmi’に由来しています。 アルゴリズムの現代的概念となるものの部分的公式化は、1928年にDavid Hilbertによって提起されたEntscheidungsproblem（「決定問題」）を解く試みから始まった。その後の公式化は、「有効な計算可能性」または「有効な方法」を定義しようと試みられた; これらの正式化には、1930年、1934年と1935年のGödel-Herbrand-Kleene再帰関数、1936年のAlonzo教会のラムダ計算、1936年のEmil PostのFormulation 1、1936年と1939年のAlan Turingのチューリング機械が含まれていた。
語源
「アルゴリズム」という言葉は、ムハンマド・イブン・ムサ・アル・クワリツミの名前をアルゴリズムの第一歩に潜んでいる。 Al-Khwārizmī（ペルシア語：خوارزمی、780-850頁）は、バグダッドの知恵の家で、ペルシャの数学者、天文学者、地理学者、学者であり、その名前は「Khwarezm」の一部であり、イランは現在、ウズベキスタンにある。
約825人、アル・クワリツミは、ヒンズー語 – アラビア数字のシステムについてアラビア語の論文を書いた。このアラビア数字は、12世紀にラテン語にAlgoritmi de numero Indorumというタイトルで翻訳された。 このタイトルは、「アルゴルティミー」が翻訳者のアル=クワリツミの名前のラテン文字化された「インディアンの数に関するアルゴリズム」を意味します。 アル=クワリツミは、中世後期にヨーロッパで最も広く読まれた数学者であり、主に別の本である代数を使っています。 中世後期のラテン語、アルゴリズム、英語の「アルゴリズム」（彼の名前の破損）は、単に「10進数体系」を意味していました。 15世紀には、ギリシャ語の「数」（「算術」参照）の影響を受けて、ラテン語がalgorithmusに変更され、対応する英語の用語「アルゴリズム」が最初に17世紀に証明された。 現代のセンスは19世紀に導入されました。
英語は、1230年頃にはじめて使われ、1391年にはチョーサーによって使われました。英語ではフランス語が採用されましたが、19世紀後半までは「アルゴリズム」は現代英語での意味を引き継いでいました。
もう一つの早期の使用はアレクサンドル・デ・ヴィルジューによって構成されたカルメン・デ・アルゴリスモ（Carmen de Algorismo）というマニュアルの1240年からのものです。 それはこうして始まる：
タクシー/タリバス・インドール・プロイメル・ビス・クイング・フィギュアには、
これは次のように解釈されます。
アルゴリズムは、現時点では、インドの人物を2倍の5倍の数で使用する芸術です。
この詩は数百行におよぶもので、新しいスタイルのインドのサイコロ、あるいはタリバス・インドールム（Talibus Indorum）、またはヒンドゥー教の数字で計算する技術を要約しています。
非公式の定義
「アルゴリズム」の定義に関するさまざまな視点の詳細な説明については、「アルゴリズムの特徴」を参照してください。
非公式の定義は、一連の操作を正確に定義する一連の規則です。 これには、数値計算を実行しないプログラムを含むすべてのコンピュータプログラムが含まれる。 一般に、プログラムは最終的に停止する場合にのみアルゴリズムです。
アルゴリズムのプロトタイプの例は、2つの整数の最大公約数を決定するユークリッドアルゴリズムである。 （他のものがある）例は、上記フローチャートおよび後のセクションの例として説明される。
Boolos、Jeffrey＆1974、1999は、次のような引用でこの単語の非公式な意味を提供しています。
人間は、十分に速く、あるいは十分に長く、あるいは十分に小さく書くことはできません（† “小さくても小さくなくても…分子、原子、電子を書くことを試みるでしょう”）。いくつかの表記法で、その名前を次々に書き出すことによって、無限に列挙されています。 しかし、人間は、ある無限の無限集合の場合には、等しく有用な何かを行うことができます。無限有限nについて、集合のn番目のメンバーを決定する明示的な指示を与えることができます。 そのような指示は、コンピューティングマシンに従うことができる形で、またはシンボル上で非常に基本的な操作だけを行うことができる人間によって、非常に明示的に与えられるべきである。
「無限の集合」とは、その要素を整数と1対1の対応関係に置くことができるものです。 したがって、BoolosとJeffreyは、アルゴリズムは、任意の「入力」整数または理論上は任意に大きな整数からの出力整数を「作成」するプロセスのための命令を意味すると言っています。 したがって、アルゴリズムは、y = m + n – 出力yを生成する2つの任意の「入力変数」mおよびnのような代数方程式とすることができる。 しかし、概念を定義しようとするさまざまな著者の試みによれば、この言葉はこれより多くを意味している。
コンピュータ（機械または人間、必要な内部的に含まれている情報と能力を備えている）の「移動」を特定する、高速かつ効率的な「良い」プロセスのための正確な指示（「コンピュータ」によって理解される言語）任意の入力整数/記号mおよびn、記号+および= …を処理し、「効率的に」、「妥当な」時間内に、指定された場所および指定されたフォーマットで出力整数yを生成する。
アルゴリズムの概念は、決定可能性の概念を定義するためにも使用されます。 その概念は公式のシステムが少数の公理と規則のセットから始まる方法を説明するための中心的なものです。 ロジックでは、アルゴリズムが完了するのに必要な時間は、私たちの慣習的な物理的次元とは明らかに関係していないため、測定できません。 進行中の作業を特徴付けるそのような不確実性から、この用語の具体的な意味（ある意味で）と抽象的な使用の両方に適合するアルゴリズムの定義が利用できなくなる。
公式化
コンピュータがデータを処理する方法には、アルゴリズムが不可欠です。 多くのコンピュータプログラムには、従業員の給与計算の計算や生徒のレポートカードの印刷など、特定のタスクを実行するためにコンピュータが（特定の順序で）実行する具体的な手順を詳述するアルゴリズムが含まれています。 したがって、アルゴリズムは、Turing-completeシステムによってシミュレートできる操作のシーケンスであると考えることができます。 この論文を主張する著者には、Minsky（1967）、Savage（1987）、Gurevich（2000）が含まれる。
ミンスキー：しかし、「自然に」効果的と言える手技は、実際には（単純な）機械で実現することができるとTuringは考えています。その賛成は反論するのが難しい」と述べた。
Gurevich： “Turingの非公式論は、彼の論文を支持してより強力な理論を正当化する：すべてのアルゴリズムはチューリングマシンによってシミュレートできる… Savage [1987]によると、アルゴリズムはチューリングマシンによって定義される計算プロセスである” 。
典型的には、アルゴリズムが処理情報と関連する場合、データは入力ソースから読み出され、出力デバイスに書き込まれ、さらなる処理のために記憶される。 格納されたデータは、アルゴリズムを実行するエンティティの内部状態の一部とみなされます。 実際には、状態は1つまたは複数のデータ構造に格納されます。
そのような計算プロセスの中には、アルゴリズムが厳密に定義されている必要があります。 つまり、どのような条件ステップも、ケースバイケースで体系的に処理されなければならない。 それぞれの場合の基準は明確でなければならず、計算可能でなければならない。
アルゴリズムは正確なステップの正確なリストなので、計算の順序はアルゴリズムの機能にとって常に重要です。 命令は通常、明示的にリストされているものとみなされ、制御の流れによって正式に記述されるアイデアである「上から」、「下から下」に向かって説明されています。
これまで、アルゴリズムの形式化についてのこの議論は、命令プログラミングの前提を前提としていた。 これは最も一般的な概念であり、個別の「機械的」手段でタスクを記述しようとします。 形式化されたアルゴリズムのこの概念に特有のことは、変数の値を設定する代入操作です。 それはスクラッチパッドとしての “記憶”の直感から派生しています。 このような割り当ての例があります。
アルゴリズムを構成するもののいくつかの代替概念については、関数プログラミングと論理プログラミングを参照してください。
アルゴリズムの表現
アルゴリズムは、自然言語、疑似コード、フローチャート、ドラコン・チャート、プログラミング言語、または制御テーブル（通訳によって処理される）を含む多くの種類の表記法で表現することができます。 アルゴリズムの自然言語表現は、冗長で曖昧な傾向があり、複雑または技術的なアルゴリズムではほとんど使用されません。 擬似コード、フローチャート、drakon-charts、および制御テーブルは、自然言語文でよく見られるあいまいさの多くを避けるアルゴリズムを表現する構造化された方法です。 プログラミング言語は主に、コンピュータで実行できる形式でアルゴリズムを表現することを目的としていますが、アルゴリズムを定義または文書化する方法としてよく使用されます。
さまざまな表現が可能であり、与えられたチューリングマシンプログラムをマシンテーブルのシーケンスとして表現することができます（詳細は有限状態マシン、状態遷移テーブル、および制御テーブルを参照）。フローチャートとdrakon-charts状態図）、または「4組の組」と呼ばれる基本的な機械コードまたはアセンブリコードの形式（詳細はチューリングマシンを参照してください）。
アルゴリズムの表現は、チューリングマシン記述の3つの許容レベルに分類することができる。
1高水準の説明
“…実装の詳細を無視してアルゴリズムを記述することをお勧めします。このレベルでは、マシンがテープやヘッドをどのように管理するかについて言及する必要はありません。
2実装の説明
“…チューリングマシンの頭部とデータをテープに保存する方法を定義するのに使われた文章。このレベルでは、状態や遷移関数の詳細は述べていない」
3正式な説明
最も詳細な「最低レベル」は、チューリングマシンの「状態テーブル」を提供します。
3つのレベルすべてで説明されている単純なアルゴリズム「Add m + n」の例については、「アルゴリズムの例」を参照してください。
実装
ほとんどのアルゴリズムは、コンピュータプログラムとして実装されることが意図されている。 しかしながら、アルゴリズムは、生物学的ニューラルネットワーク（例えば、人間の脳が算術または食品を探している昆虫）、電気回路、または機械的装置のような他の手段によっても実施される。
コンピュータアルゴリズム
コンピュータシステムでは、アルゴリズムは、ソフトウェア開発者が所与の（おそらくヌル）入力からの出力を生成する目的の「ターゲット」コンピュータに対して効果的であるようにソフトウェアで書かれた論理のインスタンスである。 最適なアルゴリズムは、古いハードウェアで実行されていても、より効率的なハードウェアで実行され、同じ目的のために最適ではない（時間複雑度が高い）アルゴリズムよりも速い結果を生成します。 そのため、コンピュータハードウェアのようなアルゴリズムは技術と見なされます。
「エレガントな」（コンパクトな）プログラム、「良い」（速い）プログラム：「シンプルさとエレガンス」という概念はクヌスと正確にはチャイティーンで非公式に現れます。
Knuth： “…ゆるく定義された美的感覚では良いアルゴリズムがほしいと思う.1つの基準は…アルゴリズムを実行するのに要する時間です… ..他の基準はアルゴリズムのコンピュータへの適合性、その単純さと優雅さです、等 ”
Chaitin：「……エレガントなプログラムは、出力を生成するための最小限のプログラムであることを意味します」
Chaitinは彼の定義の前に次のように書いています。「プログラムが「エレガント」であることを証明できないことを示す」 – そのような証拠はHaltingの問題（ibid）を解決します。
アルゴリズムによって計算可能な関数対関数：与えられた関数に対して、複数のアルゴリズムが存在する可能性があります。 プログラマが利用可能な命令セットを拡張しなくても、これは当てはまります。 Rogersは、「アルゴリズムの概念、すなわち手続きとアルゴリズムによって計算可能な関数の概念、すなわち手続きによって得られた写像を区別することは重要であり、同じ関数にはいくつかの異なるアルゴリズムがある」と述べています。
残念ながら、優良（スピード）とエレガンス（コンパクト）との間にはトレードオフがあるかもしれません。エレガントなプログラムは、あまりエレガントでないものよりも計算を完了するためにより多くのステップを要するかもしれません。 Euclidのアルゴリズムを使用した例を以下に示します。
コンピュータ（およびコンピュータ）、計算モデル：コンピュータ（または人間の「コンピュータ」）は、制限されたタイプの機械、盲目的にその指示に従う「離散決定論的機械装置」です。 MelzakとLambekの原始的なモデルは、この概念を（i）離散的で区別可能な場所、（ii）個別の、区別不能なカウンター（iii）エージェント、（iv）エージェント。
アルゴリズムのシミュレーション：コンピュータ（コンピュータ）言語：Knuthは、「アルゴリズムを学ぶ最も良い方法は、それを試して、すぐにペンと紙をとり、例を試すことです」という読者に勧めます。 しかし、実際のもののシミュレーションや実行はどうですか？ プログラマは、アルゴリズムをシミュレータ/コンピュータ/コンピュータが効果的に実行できる言語に翻訳しなければならない。 Stoneはこれを例に挙げています。二次方程式の根を計算するとき、計算機は平方根をとる方法を知っていなければなりません。 アルゴリズムが有効でない場合、アルゴリズムは平方根を抽出するための一連の規則を提供しなければならない。
つまり、プログラマは、ターゲットコンピューティングエージェント（コンピュータ/コンピュータ）に対して有効な「言語」を知っていなければなりません。
アルゴリズム分析
特定のアルゴリズムのために理論的にどのくらいの特定のリソース（時間やストレージなど）が必要かを知ることが重要な場合があります。 そのような定量的な回答（推定）を得るためのアルゴリズムの分析のための方法が開発されている。 例えば、上記のソートアルゴリズムは、リストの長さをnとする大きなO表記を使用して、O（n）の所要時間を有する。 常に、アルゴリズムは2つの値、すなわちこれまでに見つかった最大の数と入力リストの現在の位置を覚えておく必要があります。 したがって、入力番号を格納するのに必要な領域がカウントされない場合は、O（1）の領域要件があると言われ、カウントされている場合はO（n）です。
形式的対経験的
アルゴリズムの分析と研究はコンピュータサイエンスの分野であり、特定のプログラミング言語や実装を使用せずに抽象的な方法で実施されることがよくあります。 この意味で、アルゴリズム分析は、特定の実装の詳細ではなく、アルゴリズムの基礎となる特性に焦点を当てる点で、他の数学分野に似ています。 通常、擬似コードは解析のために使用され、最も簡単で最も一般的な表現です。 しかし、最終的には、ほとんどのアルゴリズムは通常、特定のハードウェア/ソフトウェアプラットフォーム上に実装され、アルゴリズム効率は実際には実コードを使用してテストされます。 「ワン・オフ」問題の解法では、特定のアルゴリズムの効率は重要な結果をもたらさないかもしれない（nが非常に大きい場合を除く）が、高速な対話型、 小さいnから大きなnへのスケーリングは、しばしば良性ではない非効率なアルゴリズムを頻繁に暴露する。
実行効率
よく確立されたアルゴリズムでさえも可能な潜在的な改善を説明するために、FFTアルゴリズム（画像処理の分野で頻繁に使用される）に関連する最近の重要な革新は、医用画像のようなアプリケーションの処理時間を最大1,000倍に短縮する可能性があります。 一般的に、速度の改善は問題の特殊な特性に依存しますが、実際のアプリケーションでは非常に一般的です。 この規模のスピードアップにより、画像処理（デジタルカメラや医療機器など）を大量に使用するコンピューティングデバイスで消費電力を削減できます。
分類
アルゴリズムを分類するには、さまざまな方法があり、それぞれ独自のメリットがあります。
実装によって
アルゴリズムを分類する1つの方法は、実施手段によるものである。
再帰
再帰的アルゴリズムとは、ある条件（終了条件としても知られる）が一致するまで、それ自体を繰り返し呼び出す（参照する）アルゴリズムです。これは、関数型プログラミングに共通のメソッドです。 反復アルゴリズムでは、ループのような反復的な構造を使用します。また、特定の問題を解決するためにスタックのような追加のデータ構造を使用することもあります。 いくつかの問題は1つの実装または他の実装に当然適しています。 たとえば、ハノイの塔は、再帰的な実装を使用してよく理解されています。 すべての再帰バージョンには同等の（しかし多かれ少なかれ複雑な）反復バージョンがあり、その逆もあります。
論理的
アルゴリズムは、制御された論理的控除と見なすことができる。 この概念は、次のように表すことができる：アルゴリズム=論理+制御。 論理構成要素は、計算において使用され得る公理を表し、制御構成要素は、公理に控除が適用される方法を決定する。 これは論理プログラミングのパラダイムの基礎です。 純粋な論理プログラミング言語では、制御構成要素は固定され、アルゴリズムは論理構成要素のみを供給することによって特定される。 このアプローチの魅力は、エレガントなセマンティクスです。公理の変更はアルゴリズムの明確な変更を伴います。
シリアル、パラレル、または分散
アルゴリズムは通常、コンピュータが一度にアルゴリズムの1つの命令を実行するという前提で議論されます。 これらのコンピュータは、シリアルコンピュータと呼ばれることもあります。 このような環境のために設計されたアルゴリズムは、並列アルゴリズムまたは分散アルゴリズムではなく、直列アルゴリズムと呼ばれます。 並列アルゴリズムは、複数のプロセッサが同時に問題に取り組むことができる一方、分散アルゴリズムはコンピュータネットワークに接続された複数のマシンを利用するコンピュータアーキテクチャを利用する。 並列アルゴリズムまたは分散アルゴリズムは、問題をより対称または非対称のサブ問題に分割し、結果をまとめて収集します。 このようなアルゴリズムにおけるリソース消費は、各プロセッサのプロセッササイクルだけでなく、プロセッサ間の通信オーバヘッドでもあります。 いくつかのソートアルゴリズムは効率的に並列化できますが、通信オーバヘッドは高価です。 反復アルゴリズムは一般に並列化可能です。 いくつかの問題には並列アルゴリズムはなく、本質的にシリアル問題と呼ばれます。
決定論的または非決定論的
決定論的アルゴリズムはアルゴリズムのすべてのステップで正確な決定で問題を解決しますが、非決定論的アルゴリズムではヒューリスティックを使用してより正確な推測が行われますが、推測によって問題を解決します。
正確または近似
多くのアルゴリズムが正確な解に達している間、近似アルゴリズムは真の解に近い近似を求めます。 近似は、決定論的戦略またはランダム戦略のいずれかを使用して達成することができる。 このようなアルゴリズムは、多くの困難な問題に対して実用的価値があります。 近似アルゴリズムの例の1つは、ナップザック問題です。 ナップザックの問題は、与えられたアイテムのセットがある場合の問題です。 この問題の目標は、ナップザックをパックして最大の合計値を得ることです。 各項目にはある程度の重みと値があります。 私たちが運ぶことができる総重量は固定数X以下です。したがって、アイテムの重量とその値を考慮する必要があります。
量子アルゴリズム
彼らは量子計算の現実的なモデルで動作します。 この用語は、本質的に量子であるように見えるアルゴリズムに通常使用されるか、または量子重畳または量子エンタングルメントのような量子計算のいくつかの本質的な特徴を使用する。
設計パラダイム
アルゴリズムを分類する別の方法は、その設計方法論またはパラダイムによるものです。 いくつかのパラダイムがあり、それぞれが互いに異なっています。 さらに、これらのカテゴリのそれぞれは、多くの異なるタイプのアルゴリズムを含む。 いくつかの一般的なパラダイムは次のとおりです。
ブルートフォースまたは網羅的な検索
これは、可能なすべての解決方法を試して、どれが最適かを知るための素朴な方法です。
分割統治
分割および征服アルゴリズムは、問題が簡単に解決できるほど小さくなるまで、問題のインスタンスを同じ問題の1つまたは複数の小さなインスタンス（通常は再帰的）に繰り返し繰り返します。 分割と征服の1つのこのような例は、マージソートです。 セグメント化は、データをセグメントに分割した後に各セグメントのデータに対して行うことができ、セグメント全体をマージすることによって、征服段階でデータ全体のソートを行うことができます。 分割と征服のより単純な変形は、同一の部分問題を解決し、この部分問題の解決法を使用してより大きな問題を解決する、減少と征服アルゴリズムと呼ばれます。 分割と征服は、問題を複数のサブ問題に分割するため、征服の段階は、減少と征服のアルゴリズムより複雑です。 減少及び征服アルゴリズムの一例は、バイナリサーチアルゴリズムである。
検索と列挙
チェスのような多くの問題は、グラフの問題としてモデル化できます。 グラフ探索アルゴリズムは、グラフを移動するためのルールを指定し、このような問題に役立ちます。 このカテゴリには、検索アルゴリズム、分岐および連結列挙、バックトラッキングも含まれます。
ランダム化アルゴリズム
複雑さの軽減
この手法では、難しい問題を解決してよりよく知られた問題にしています。そのためには、願わくは漸近的に最適なアルゴリズムがあります。 目標は、その複雑さが結果として生じるアルゴリズムの縮小によって支配されない低減アルゴリズムを見つけることである。 例えば、ソートされていないリストの中央値を見つけるための1つの選択アルゴリズムは、まずリスト（高価な部分）をソートし、次にソートされたリスト（安価な部分）の中の要素を引き出すことを含む。 この技法は変換と征服とも呼ばれます。
最適化の問題
最適化の問題については、アルゴリズムのより具体的な分類があります。 そのような問題のアルゴリズムは、上記の一般的なカテゴリのうちの1つまたは複数に加えて、以下のうちの1つに分類され得る。
線形計画
線形等式制約と不等式制約に束縛された線形関数に対する最適解を探索する場合、問題の制約を最適解の生成に直接用いることができる。 一般的なシンプレックスアルゴリズムなど、このカテゴリの問題を解決できるアルゴリズムがあります。 線形計画法で解決できる問題には、有向グラフの最大フロー問題があります。 さらに、未知数のうちの1つ以上が整数でなければならない問題がある場合、それは整数計画に分類される。 線形計画法アルゴリズムは、整数値に対するすべての制約が表面的であることが証明できれば、この解決法はこのような問題を解決することができます。 一般的なケースでは、問題の難易度に応じて、近似解を求める特殊なアルゴリズムまたはアルゴリズムが使用されます。
動的プログラミング
問題が最適な部分構造を示している場合 – 問題の最適解を部分問題に対する最適解から構成でき、部分問題が重複している – つまり、同じ問題が多くの異なる問題を解決するために使用される場合、動的計画と呼ばれるより速いアプローチは、既に計算されている。 たとえば、Floyd-Warshallアルゴリズムは、すべての隣接する頂点からのゴールへの最短経路を使用して、重み付きグラフの頂点からのゴールへの最短経路を見つけることができます。 ダイナミックなプログラミングとメモは一緒になります。 ダイナミックプログラミングと分割と征服の主な違いは、サブプログラムは分割と征服において多かれ少なかれ独立しているのに対し、サブプログラムは動的プログラミングで重複している点です。 動的プログラミングと単純な再帰の違いは、再帰呼び出しのキャッシングまたはメモ処理にあります。 部分問題が独立していて反復がないときは、メモは役に立ちません。 ダイナミックプログラミングはすべての複雑な問題の解決策ではありません。 既に解明されたサブ問題の表をメモまたは使用することにより、動的計画法は多くの問題の指数関数的性質を多項式の複雑さに還元する。
貪欲な方法
グリーディ・アルゴリズムは、サブストラクチャを調べることによって動作する点で動的プログラミング・アルゴリズムに似ています。この場合は、問題ではなく、所定の解決策を検討します。 このようなアルゴリズムは、何らかの方法で与えられるか、または構築される可能性のある解決策から始まり、小さな修正を加えることによって改善される。 いくつかの問題については最適解を見つけることができますが、他の人は局所最適解、つまりアルゴリズムでは改善できないが最適ではない解で停止します。 貪欲アルゴリズムの最も一般的な使用法は、この方法で最適解を見つけることが可能な最小スパニングツリーを見つけることです。 Huffman Tree、Kruskal、Prim、Sollinは、この最適化問題を解決できる貪欲なアルゴリズムです。
発見的方法
最適化問題では、ヒューリスティックアルゴリズムを使用して、最適解を見つけることが実用的でない場合に、最適解に近い解を見つけることができます。 これらのアルゴリズムは、進行するにつれて最適なソリューションに近づくことによって機能します。 原則として、無限に実行すると、最適な解決策が見つかるでしょう。 彼らのメリットは、比較的短時間で最適解に非常に近い解を見つけることができることです。 このようなアルゴリズムには、ローカル検索、タブー検索、シミュレーテッドアニーリング、および遺伝的アルゴリズムが含まれる。 シミュレートされたアニーリングのような一部のものは、非決定論的なアルゴリズムですが、タブー検索のような他のものは確定的です。 最適でない解の誤差の境界が分かっているとき、アルゴリズムは近似アルゴリズムとしてさらに分類される。
研究分野別
科学のあらゆる分野には独自の問題があり、効率的なアルゴリズムが必要です。 1つの分野の関連する問題は、しばしば一緒に研究されます。 いくつかの例のクラスは、検索アルゴリズム、ソートアルゴリズム、マージアルゴリズム、数値アルゴリズム、グラフアルゴリズム、文字列アルゴリズム、計算幾何アルゴリズム、組合せアルゴリズム、医療アルゴリズム、機械学習、暗号化、データ圧縮アルゴリズムおよび解析技術である。
フィールドはお互いに重なり合う傾向があり、一方のフィールドのアルゴリズムの進歩は、他の、時には完全に無関係なフィールドのアルゴリズム進歩を改善する可能性がある。 たとえば、業界でのリソース消費の最適化のためにダイナミックプログラミングが発明されましたが、現在では多くの分野で幅広い問題を解決するために使用されています。
複雑さ
アルゴリズムは、入力サイズと比較して完了までに要する時間で分類できます。
一定時間：入力サイズに関係なく、アルゴリズムに必要な時間が同じ場合。 たとえば、配列要素へのアクセス。
線形時間：時間が入力サイズに比例する場合。 リストのトラバースなど
対数時間：時間が入力サイズの対数関数である場合。 例えばバイナリ検索アルゴリズム。
多項式時間：時間が入力サイズの累乗である場合。 例えば、バブルソートアルゴリズムは、二次的な時間の複雑さを有する。
指数関数時間：時間が入力サイズの指数関数である場合。 例：ブルートフォース検索。
いくつかの問題には複雑さの異なる複数のアルゴリズムが存在し、他の問題にはアルゴリズムがないか、または効率的なアルゴリズムが知られていない可能性があります。 いくつかの問題から他の問題へのマッピングもあります。 このため、アルゴリズムの代わりに問題自体を、可能な限り最良のアルゴリズムの複雑さに基づく等価クラスに分類する方が適切であることが判明しました。
連続アルゴリズム
単語「アルゴリズム」に適用されるときの形容詞「連続」は、
このデータが離散近似で表されているにもかかわらず、連続量を表すデータで動作するアルゴリズム。このようなアルゴリズムは数値解析で研究されています。 または
アナログコンピュータ上で実行される、データ上で連続的に動作する微分方程式の形式のアルゴリズム。