2.1 アルゴリズムの効率評価¶

アルゴリズム設計において、私たちは順序に従って以下の2つの目標を追求します。

問題の解決策を見つける: アルゴリズムは、指定された入力範囲内で確実に正しい解を見つけることができるべきです。
最適解を求める: 同じ問題に対して複数の解決策が存在する場合があり、私たちは可能な限り最も効率的なアルゴリズムを見つけることを目指します。

つまり、問題を解決できることを前提として、アルゴリズムの効率がアルゴリズムを評価する主要な基準となっており、これには以下の2つの次元が含まれます。

時間効率: アルゴリズムが実行される速度。
空間効率: アルゴリズムが占有するメモリ空間のサイズ。

要するに、私たちの目標は、高速でメモリ効率の良いデータ構造とアルゴリズムを設計することです。アルゴリズムの効率を効果的に評価することは重要です。なぜなら、そうすることで初めて様々なアルゴリズムを比較し、アルゴリズムの設計と最適化プロセスを導くことができるからです。

効率評価には主に2つの方法があります：実際のテストと理論的推定です。

2.1.1 実際のテスト¶

アルゴリズムAとBがあり、どちらも同じ問題を解決でき、それらの効率を比較する必要があるとします。最も直接的な方法は、コンピュータを使用してこれら2つのアルゴリズムを実行し、実行時間とメモリ使用量を監視・記録することです。この評価方法は実際の状況を反映しますが、大きな制限があります。

一方で、テスト環境からの干渉を排除することは困難です。ハードウェア構成はアルゴリズムの性能に影響を与える可能性があります。例えば、並列度の高いアルゴリズムはマルチコアCPUでの実行により適していますし、集約的なメモリ操作を含むアルゴリズムは高性能メモリでより良い性能を発揮します。アルゴリズムのテスト結果は、異なるマシン間で変わる可能性があります。これは、平均効率を計算するために複数のマシンでテストすることが実用的でないことを意味します。

一方で、完全なテストを実施することは非常にリソース集約的です。アルゴリズムの効率は入力データサイズによって変わります。例えば、データ量が少ない場合はアルゴリズムAがBより速く実行される可能性がありますが、データ量が多い場合はテスト結果が逆になる可能性があります。したがって、説得力のある結論を導くためには、幅広い入力データサイズをテストする必要があり、これには過度な計算リソースが必要になります。

2.1.2 理論的推定¶

実際のテストの大きな制限により、計算のみでアルゴリズムの効率を評価することを検討できます。この推定方法は漸近的複雑度解析、または単に複雑度解析として知られています。

複雑度解析は、アルゴリズムの実行に必要な時間と空間リソースと入力データのサイズとの関係を反映します。これは、入力データのサイズが増加するにつれて、アルゴリズムに必要な時間と空間の増加傾向を記述します。この定義は複雑に聞こえるかもしれませんが、より良く理解するために3つの重要なポイントに分解できます。

「時間と空間リソース」は、それぞれ時間計算量と空間計算量に対応します。
「入力データのサイズが増加するにつれて」は、複雑度がアルゴリズムの効率と入力データ量との関係を反映することを意味します。
「時間と空間の増加傾向」は、複雑度解析が実行時間や占有空間の具体的な値ではなく、時間や空間が増加する「率」に焦点を当てることを示します。

複雑度解析は実際のテスト方法の欠点を克服します。これは以下の側面で反映されます：

実際にコードを実行する必要がないため、より環境に優しく、エネルギー効率が良いです。
テスト環境に依存せず、すべての動作プラットフォームに適用できます。
異なるデータ量でのアルゴリズムの効率を反映でき、特に大量データでのアルゴリズムの性能を示します。

Tip

複雑度の概念についてまだ混乱している場合でも、心配しないでください。以降の章で詳しく取り上げます。

複雑度解析は、アルゴリズムの効率を評価する「ものさし」を提供し、実行に必要な時間と空間リソースを測定し、異なるアルゴリズムの効率を比較することを可能にします。

複雑度は数学的概念であり、初心者には抽象的で困難かもしれません。この観点から、複雑度解析は最初に紹介するのに最も適したトピックではないかもしれません。しかし、特定のデータ構造やアルゴリズムの特性について議論するとき、その速度と空間使用量を分析することを避けるのは困難です。

要約すると、データ構造とアルゴリズムに深く入る前に複雑度解析の基本的な理解を身につけることをお勧めします。これにより、簡単なアルゴリズムで複雑度解析を実行できるようになります。