DAA-アルゴリズムの分析

アルゴリズムの理論的分析では、漸近的な意味でそれらの複雑さを推定すること、つまり、任意に大きな入力の複雑さ関数を推定することが一般的です。用語"analysis of algorithms" ドナルド・クヌースによって造られました。

アルゴリズム分析は、特定の計算問題を解決するためにアルゴリズムに必要なリソースの理論的推定を提供する計算複雑性理論の重要な部分です。ほとんどのアルゴリズムは、任意の長さの入力で機能するように設計されています。アルゴリズムの分析は、アルゴリズムの実行に必要な時間とスペースのリソースの量を決定することです。

通常、アルゴリズムの効率または実行時間は、入力長をステップ数に関連付ける関数として表されます。 time complexity、またはメモリのボリューム、 space complexity。

分析の必要性

この章では、アルゴリズムの分析の必要性と、1つの計算問題をさまざまなアルゴリズムで解決できるため、特定の問題に対してより適切なアルゴリズムを選択する方法について説明します。

特定の問題のアルゴリズムを検討することで、パターン認識の開発を開始し、このアルゴリズムを使用して同様のタイプの問題を解決できるようになります。

これらのアルゴリズムの目的は同じですが、アルゴリズムは互いにまったく異なることがよくあります。たとえば、さまざまなアルゴリズムを使用して一連の数値を並べ替えることができることがわかっています。1つのアルゴリズムによって実行される比較の数は、同じ入力に対して他のアルゴリズムと異なる場合があります。したがって、これらのアルゴリズムの時間計算量は異なる場合があります。同時に、各アルゴリズムに必要なメモリスペースを計算する必要があります。

アルゴリズムの分析は、必要な時間とサイズ（実装中のストレージ用のメモリのサイズ）の観点からアルゴリズムの問​​題解決能力を分析するプロセスです。ただし、アルゴリズムの分析の主な関心事は、必要な時間またはパフォーマンスです。一般的に、以下のタイプの分析を実行します-

• Worst-case −サイズのインスタンスで実行される最大ステップ数 a。

• Best-case −サイズのインスタンスで実行される最小ステップ数 a。

• Average case −サイズの任意のインスタンスで実行された平均ステップ数 a。

• Amortized −サイズの入力に適用される一連の操作 a 時間の経過とともに平均化。

問題を解決するには、メモリが限られているが十分なスペースが利用できるシステムでプログラムを実行する場合や、その逆の場合があるため、時間とスペースの複雑さを考慮する必要があります。この文脈で、私たちが比較するとbubble sort そして merge sort。バブルソートは追加のメモリを必要としませんが、マージソートは追加のスペースを必要とします。バブルソートの時間計算量はマージソートに比べて高くなりますが、メモリが非常に限られている環境でプログラムを実行する必要がある場合は、バブルソートを適用する必要があります。