Design-and-analysis-of-algorithms-analysis-of-algorithms
DAA-アルゴリズムの分析
アルゴリズムの理論的分析では、漸近的な意味での複雑さを推定する、つまり、任意の大きな入力の複雑さ関数を推定することが一般的です。 「アルゴリズムの分析」*という用語は、ドナルドクヌースによって作られました。
アルゴリズム分析は、計算の複雑さの理論の重要な部分であり、特定の計算の問題を解決するためにアルゴリズムに必要なリソースの理論的な推定を提供します。 ほとんどのアルゴリズムは、任意の長さの入力で動作するように設計されています。 アルゴリズムの分析とは、アルゴリズムの実行に必要な時間とスペースのリソースの量を決定することです。
通常、アルゴリズムの効率または実行時間は、入力の長さを*時間の複雑さ*として知られるステップの数、または*空間の複雑さ*として知られるメモリの量に関連付ける関数として表されます。
分析の必要性
この章では、アルゴリズムの分析の必要性と、特定の問題に対してより良いアルゴリズムを選択する方法について説明します。1つの計算問題は異なるアルゴリズムで解決できるためです。
特定の問題のアルゴリズムを検討することにより、パターン認識の開発を開始できるため、このアルゴリズムを使用して同様のタイプの問題を解決できます。
これらのアルゴリズムの目的は同じですが、多くの場合、アルゴリズムは互いにかなり異なります。 たとえば、異なるアルゴリズムを使用して一連の数値をソートできることがわかっています。 1つのアルゴリズムによって実行される比較の数は、同じ入力に対して他のアルゴリズムと異なる場合があります。 したがって、これらのアルゴリズムの時間の複雑さは異なる場合があります。 同時に、各アルゴリズムに必要なメモリ空間を計算する必要があります。
アルゴリズムの分析は、アルゴリズムの問題解決能力を、必要な時間とサイズ（実装中のストレージのメモリサイズ）の観点から分析するプロセスです。 ただし、アルゴリズムの分析の主な関心事は、必要な時間またはパフォーマンスです。 一般的に、次のタイプの分析を実行します-
- ワーストケース-サイズ a のインスタンスで実行されるステップの最大数。
- ベストケース-サイズ a のインスタンスで実行される最小ステップ数。
- 平均ケース-サイズ a のインスタンスで実行される平均ステップ数。
- Amortized -時間の経過とともに平均化されたサイズ a の入力に適用される一連の操作。
問題を解決するには、メモリは限られているが十分なスペースが利用可能であるか、またはその逆のシステムでプログラムが実行される可能性があるため、時間とスペースの複雑さを考慮する必要があります。 このコンテキストで、*バブルソート*と*マージソート*を比較すると。 バブルソートには追加のメモリは必要ありませんが、マージソートには追加のスペースが必要です。 バブルソートの時間の複雑さはマージソートに比べて高くなりますが、メモリが非常に限られている環境でプログラムを実行する必要がある場合は、バブルソートを適用する必要があります。
