アルゴリズム設計とは、問題を解決するための数学的プロセスを開発することです。アルゴリズム分析とは、アルゴリズムのパフォーマンスを予測することです。前の 2 つの章では、古典的なデータ構造 (リスト、スタック、キュー、優先キュー、セット、マップ) を紹介し、それらを問​​題解決に適用しました。この章では、さまざまな例を使用して、効率的なアルゴリズムを開発するための一般的なアルゴリズム手法 (動的プログラミング、分割統治、バックトラッキング) を紹介します。

Big O 記法は、入力サイズに基づいてアルゴリズムの時間計算量を測定する関数を取得します。関数内の乗算定数と非支配項は無視できます。 2 つのアルゴリズムが検索などの同じタスクを実行するとします (線形検索と二分検索)。どちらがいいですか？この質問に答えるには、これらのアルゴリズムを実装し、プログラムを実行して実行時間を取得します。しかし、このアプローチには 2 つの問題があります:

• まず、コンピューター上では多くのタスクが同時に実行されます。特定のプログラムの実行時間はシステム負荷によって異なります。
• 2 番目に、実行時間は特定の入力によって異なります。たとえば、線形探索と二分探索を考えてみましょう。検索対象の要素がリストの最初にある場合、線形検索の方が二分検索よりも早く要素を見つけます。

実行時間を測定してアルゴリズムを比較することは非常に困難です。これらの問題を克服するために、コンピューターや特定の入力に依存しないアルゴリズムを分析する理論的アプローチが開発されました。このアプローチは、入力サイズに対する変更の影響を近似します。このようにして、入力サイズの増加に伴ってアルゴリズムの実行時間がどれだけ速く増加するかを確認できるため、成長率を調べることで 2 つのアルゴリズムを比較できます。

線形探索を検討します。線形検索アルゴリズムは、キーが見つかるか配列がなくなるまで、キーと配列内の要素を順番に比較します。キーが配列内にない場合は、サイズ n の配列に対して n の比較が必要です。キーが配列内にある場合は、平均して n/2 回の比較が必要です。アルゴリズムの実行時間は配列のサイズに比例します。配列のサイズを 2 倍にすると、比較の数も 2 倍になることが予想されます。アルゴリズムは直線的な速度で成長します。成長率は n と桁違いです。コンピューター科学者は、「桁数」を表すために Big O 表記を使用します。この表記を使用すると、線形探索アルゴリズムの複雑さは O(n) となり、「order of n」と発音されます。時間計算量が O(n) のアルゴリズムを線形アルゴリズムと呼び、線形の成長率を示します。

同じ入力サイズでも、アルゴリズムの実行時間は入力に応じて異なる場合があります。実行時間が最短になる入力は ベストケース入力 と呼ばれ、実行時間が最長になる入力は ワーストケース入力 と呼ばれます。ベストケース分析と
最悪の場合の分析では、最良の場合の入力と最悪の場合の入力についてアルゴリズムを分析します。最良の場合と最悪の場合の分析は代表的なものではありませんが、最悪の場合の分析は非常に役立ちます。アルゴリズムが最悪の場合よりも遅くなることは決してないので、ご安心ください。
平均ケース分析は、同じサイズの考えられるすべての入力の平均時間を決定しようとします。平均ケース分析は理想的ですが、多くの問題ではさまざまな入力インスタンスの相対確率と分布を決定するのが難しいため、実行は困難です。最悪の場合の分析は実行しやすいため、通常、分析は最悪の場合を想定して実行されます。

線形検索アルゴリズムでは、リスト内にあることがわかっているものをほぼ常に検索する場合、最悪の場合は n の比較が必要で、平均的な場合は n/2 の比較が必要です。 Big O 表記を使用すると、どちらの場合も O(n) 時間がかかります。乗算定数(1/2)は省略可能です。アルゴリズム分析は成長率に焦点を当てています。乗算定数は成長率に影響を与えません。 n/2 または 100_n_ の成長率は、以下の表 成長率 に示すように、n の場合と同じです。したがって、O(n) = O(n/2) = O(100n).

n 要素の配列内の最大数を見つけるアルゴリズムを考えてみましょう。 n が 2 の場合に最大数を見つけるには、1 回の比較が必要です。 n が 3 の場合、2 つの比較。一般に、n 個の要素のリスト内の最大数を見つけるには、n - 1 回の比較が必要です。アルゴリズム分析は、大きな入力サイズを対象としています。入力サイズが小さい場合、アルゴリズムの効率を推定することに意味がありません。 n が大きくなるにつれて、式 n - 1 の n の部分が複雑さを支配します。 Big O 表記を使用すると、支配的ではない部分 (
の -1 など) を無視できます。 式 n - 1) を強調表示し、重要な部分 (式 n - 1 の n など) を強調表示します。したがって、このアルゴリズムの複雑さは O(n).

Big O 表記法は、入力サイズに応じてアルゴリズムの実行時間を推定します。時間が入力サイズに関係しない場合、アルゴリズムは O(1) という表記で 一定時間 を取ると言われます。たとえば、配列
内の指定されたインデックスにある要素を取得するメソッド 配列のサイズが増加しても時間は増加しないため、一定の時間がかかります。

次の数学的合計は、アルゴリズム分析でよく役立ちます:

時間計算量は、Big-O 表記を使用した実行時間の尺度です。同様に、Big-O 表記を使用して 空間複雑度 を測定することもできます。 空間複雑度は、アルゴリズムによって使用されるメモリ空間の量を測定します。この本で紹介されているほとんどのアルゴリズムの空間計算量は O(n) です。つまり、入力サイズに対して線形の増加率を示します。たとえば、線形探索の空間計算量は O(n).