最良の答え
これに対する答えはありません。
この問題の説明に対する答えを見つけましょう：
Q。アルゴリズムのパフォーマンスが向上していることを見つける方法は？
A。 アルゴリズムを比較する最も一般的な方法：
1）時間の複雑さ
2）空間の複雑さ
3）ソリューションの品質（そうでない場合があります）問題を正確に解決することを提案している場合に適用できます）。近似アルゴリズムについて話している場合、これは大きな要因になる可能性があります。
4）アルゴリズムの実装/適応の容易さ。アルゴリズムによっては、正しく実装するために多くのオーバーヘッドが発生する可能性があります。より適切なアルゴリズムがある場合もあります。たとえば、並列コンピューティングでは、ベルマンフォードの動作方法により、ほとんどの場合、ダイクストラのアルゴリズムよりもベルマンフォードの方が便利です。
ただし、時間と複雑さは
1つは「数値安定性」で、線形代数と微分方程式の両方のアルゴリズムの機能です。より数値的に安定したアルゴリズムに、より多くのアルゴリズム時間とより多くのアルゴリズムの複雑さの両方を費やします。線形代数では、数値の有限表現が失われる可能性があるため、アルゴリズムがゼロまたは無限大、あるいはその両方に近すぎる数値に遭遇すると、一般に不安定性が発生します。一般に、これにより、非常にわずかに異なる数が発生し、互いにわずか数イプシロンが異なります（ここで、イプシロンは、マシン上で1つに追加でき、結果を得ることができる最小の数です！= 1）。答え。したがって、たとえば、安定したアルゴリズムを取得するために、LU分解で「ピボット」することにより、多くの時間とスペースの複雑さを費やします。 LUをピボットしないと安定しません。同様に、不安定性を回避するために「条件」行列のみを実行するアルゴリズムがあります。
2番目の例は「堅牢性」です。その技術的な統計的意味。堅牢性とは、外れ値に*影響を受けない*測定値またはアルゴリズムを意味します。したがって、たとえば、最小二乗線を点のセットに合わせると、線が1つの非常に大きな値によって大きく歪む可能性があります。完全な45度の線を形成する99ペアの数値がある場合でも、Y値が同じ線に「あるべき」ものの100倍である単一の外れ値ペアを追加すると、近似線は厳しくなります。 45度の線から外れています。アルゴリズムは、1つの外れ値ポイントをより適切に表すために、99ポイントの完全な適合を「あきらめ」ます。これは*堅牢ではありません*。
堅牢な最小二乗アプローチは、その線を使用して作成された二乗誤差の合計を最小化する線を見つける代わりに、の*中央値*を最小化する線を見つけることです。その線を使用して作成された二乗誤差。この例では、その線は45度の線であり、二乗誤差の中央値はゼロであり、外れ値ポイント（実際には最大98個のよりクレイジーな外れ値）は完全に無視されます。 45度の線が見つかります。
統計曲線のフィッティング、形状の検索などのために、同様の堅牢なアルゴリズムが存在します。ただし、時間にコストがかかり、場合によっては非常にコストがかかります。しかし、ロバスト統計は信号の「ノイズ」の影響を受けないため、時間コストは価値がありますが、最小二乗誤差アプローチはそうではありません。現実の世界はノイズと外れ値の両方でいっぱいです。それらのいくつかは、特にピクセル化された画像やサンプリングされたサウンドで、人的または機械的なエラーによって引き起こされます。このような状況では、より時間のかかる堅牢なアルゴリズムがノイズの多い環境で信号を見つけることができます。この環境では、高速のアルゴリズムがノイズによって破損した応答を生成するため、役に立たないか、受け入れられた場合は危険です。
空間の複雑さは、ノイズや信号の劣化にもかかわらず、実際の信号をモデル化する可能性が最も高い答えを見つけることほど重要ではありません。
回答
アルゴリズムは「レシピ」として数学に端を発しています。関数ベースの計算を実行するために、それは機械的に追跡することができます。関数ベースの数学的世界観では、すべての入力は計算の開始時に指定する必要があり、これはクローズドボックス方式で進行します。アルゴリズムの記述は単一の言語や形式に制限されていないため、アルゴリズムの概念は本質的に非公式です。
おそらく最も古い例は、最大公約数を見つけるためのユークリッドのアルゴリズムです。アルゴリズムは、計算が「効果的」であるとはどういう意味かを捉えています。数式と同様に、アルゴリズムは値の計算方法を教えてくれます。それらとは異なり、アルゴリズムには、現在ループまたはブランチと呼ばれているものが含まれる場合があります。
アルゴリズムの役割：有限の入力値xが与えられると、アルゴリズムはそれを出力値yに効果的に変換する手順を記述します。ここでyはいくつかの再帰関数fのf（x）。
アルゴリズムは1950年代に初期のコンピューター科学者によって採用され、アルゴリズムとチューリングマシン（TM、1936年にさかのぼる計算の正式なモデル）を結び付け、表現力を同等にしました。
Knuthの有名で影響力のある教科書「TheArtof Computer Programming、Vol。1」は、1960年代後半に、コンピュータサイエンスにおけるアルゴリズムの中心性を広めました。アルゴリズムの彼の定義において、クヌースは計算理論の数学関数ベースの基礎と一致していました。 「効果的な計算方法の概念を定式化するための本質的に同等の方法は他にもたくさんあります（たとえば、TMを使用します）。」
クヌースは、アルゴリズムが閉じていることを明示的に指定しました。計算が開始されると、新しい入力は受け入れられません。「アルゴリズムには0個以上の入力があります。つまり、アルゴリズムが開始する前に最初に与えられる量です。」彼は、I / Oを伴う可能性のある任意の計算からアルゴリズムを区別しました。アルゴリズムではない問題について彼が挙げた1つの例は、レシピからの次の指示です。「混合物がもろくなるまで軽く投げます。」コンピュータが混合する時間を知ることは不可能であるため、この問題はアルゴリズム的ではありません。これは、湿度など、事前に確実に予測できない外部の動的に変化する条件に依存する可能性があります。
アルゴリズムの正確な概念については合意がありませんが、Knuthのアルゴリズムに関する議論は依然として決定的なものです。
アルゴリズムを指定するために明示的に開発された最初の高級プログラミング言語はALGOL（ALGOrithmic Language）でした。 50年代後半に導入され、1960年代を通じて洗練され、アルゴリズムの公開の標準として機能しました。アルゴリズムの関数ベースの概念化に忠実であるため、ALGOLは、アルゴリズムの関係外のこれらの操作を考慮して、入力と出力の構成を提供しませんでした。 （当然のことながら、この不在により、業界による商用アプリケーションへのALGOLの採用が妨げられました。）
1960年代には、学部のコンピュータサイエンス（CS）プログラムが急増しました。 Association for Computing Machinery（ACM）によると、米国のCSプログラムの数は1964年の11から1968年には92に増加しました。この増加には、学者の目から見たこの新しい分野の正当性の確立に向けた激しい活動が伴いました。コミュニティ。 ACMはこの活動で中心的な役割を果たしました。 1965年に、CSの正当性と説明を学問分野として発表しました。これは、1968年の学部CSプログラムに関する推奨事項の基礎として機能しました。
ACMによるCSの説明では、情報の効果的な変換が中心的な関心事であると特定されました。コンピュータサイエンスは、物理学がエネルギーに関係しているのとほぼ同じ意味で情報に関係しています…コンピュータ科学者は、情報を変換できる実用的な手段を発見することに興味を持っています。」この説明では、アルゴリズムをコンピュータサイエンスの中心に置きます。これは、アルゴリズムが入力から出力へのこれらの効果的な変換を実行するための「レシピ」であるためです。実際、ACMは、レポートの次の文で明示的なアルゴリズムに焦点を当てています。
「この関心は、情報を表現する効果的な方法、情報を変換する効果的なアルゴリズム、表現するための効果的な言語の調査につながります。アルゴリズム…そして合理的なコストでこれらを達成するための効果的な方法。」
物理学におけるエネルギーの懸念と同様に、中心的なアルゴリズムの懸念を持つことは、CSを正当な学問分野として確立するのに役立ちました。物理。アルゴリズムは今日までコンピュータサイエンスの中心であり続けています。
解決可能な問題を定義するための非公式（アルゴリズムベース）と公式（TMベース）のアプローチの共存は今日まで続いており、アルゴリズムまたは計算可能性に関するすべての最新の教科書。これは、同等のチューリングマシンを構築できるという知識を持って、「擬似コード」を使用して非公式にアルゴリズム計算を記述できるようにすることで、コンピューター科学者にとって非常に便利であることが証明されています。
-問題は、可能であれば解決可能です。アルゴリズムによって指定されます。 −チューリングマシンがあれば問題は解決できます。
CSの中心にアルゴリズムを配置するという1960年代の理論家と教育者の決定は、初期の学部の教科書に明確に反映されていました。ただし、アルゴリズムの明示的な標準定義はなく、さまざまな教科書がこの用語を異なる方法で定義することを選択しました。 Knuthの教科書など、一部の教科書では、アルゴリズムを関数を計算するものに明示的に制限しているため、チューリングマシンと同等ですが、ほとんどの理論書では、この制限を暗示していますが、説明していません。
初期の例は1969年のHopcroftとUllmanによる教科書で、後の版が今日まで使用されています。「手順とは、コンピュータプログラムなど、機械的に実行できる命令の有限シーケンスです。常に終了する手順はアルゴリズムと呼ばれます。」
このアルゴリズムの説明は、食事の準備などの非機能的な計算を明示的に排除するものではありません。ただし、さまざまな問題の例から、関数ベースの計算のみを考慮していることがわかります。実際、彼らは例としてALGOLを使用しましたが、入力と出力の構成さえ提供していませんでした。
60年代後半以降、実際に使用され、CSプログラムで教えられた高級プログラミング言語はなくなりました。初期のALGOLのアルゴリズムの制約に縛られています。オペレーティングシステム、グラフィカルユーザーインターフェイス、自動車両やその他のロボットなど、計算全体を通じて継続的に環境と相互作用するプログラムを作成できます。
それに応じて、RiceやRice（1969）は、アルゴリズムの概念を明示的に拡張して、機能しない問題を含めました。このアプローチは、関数の計算に制限されることなくアルゴリズムの中心性を反映しており、非理論的な教科書の典型的なものになりました。これらの教科書の主題は、計算理論ではなくプログラミング方法論であり、計算モデルを支える数学的原理は、実用性のために捨てられました。
表面的には、アルゴリズムの定義ライスとライスや他のそのような教科書では、ホプクロフトとウルマンと同じです。「アルゴリズムは、何かをするためのレシピ、一連の指示、またはプロセスの仕様です。その何かは通常、ある種の問題を解決しています。」しかし、彼らの計算可能な問題の例はもはや関数ベースではなく、クヌースが拒否した種類の計算だけを認めています。おそらくアルゴリズムによって解決できる2つのそのような例は、ジャガイモのウォッカを作ることと、溝を砂で埋めることです。クヌースはそれらの両方を拒否したでしょう。
これらの教科書は、それらの「アルゴリズム」についてTMと同等であるとは主張していませんでした。ただし、このアルゴリズムの概念がKnuthの概念とは異なり、計算可能と見なされる一連の問題が拡大されていることを生徒は認識していませんでした。アルゴリズム（したがって計算可能な問題）のより広く、より実用的な概念化を、非常に計算可能な問題はTMによって計算できると主張する理論と組み合わせることにより、アルゴリズムに焦点を当てたCSカリキュラムは、この幅広い問題のセットが可能であるという誤った印象を学生に残しましたまた、TMによって解決されます。
実用的なコンピュータ科学者は、ライスとライスの先導に従い、関数の計算を超えてアルゴリズムの概念を広げてきましたが、理論計算機科学は、フレーム化する数学的な世界観を保持しています。関数ベースとしての計算、それに応じて計算問題の概念を区切ります。これは、少なくとも学部レベルでは当てはまります。その結果、二分法が生まれます。コンピュータサイエンスのコミュニティでは、アルゴリズムを一般的な計算の概念（「コンピュータの機能」）と同義であると同時に、チューリングマシンと同等であると考えています。
人々にこの二分法を認識させるために、私はこの長い答えを書かなければなりませんでした。最初に言ったように、アルゴリズムの概念は非公式です。関数の計算（またはチューリングマシン）と同等であると考えることも、オペレーティングシステムや自動自動車などのリアルタイムのインタラクティブプログラムを含む、プログラムを作成できるものと考えることもできます。しかし、反対の一般的な混乱にもかかわらず、2つの定義は同等ではありません。