2.1 アルゴリズム効率の評価¶
アルゴリズム設計では、次の 2 つのレベルの目標を順に追求します。
- 問題の解法を見つける：アルゴリズムは、定められた入力範囲内で問題の正しい解を確実に求められる必要があります。
- 最適な解法を追求する：同じ問題に対して複数の解法が存在する場合があり、私たちはできるだけ効率的なアルゴリズムを見つけたいと考えます。
つまり、問題を解けることを前提として、アルゴリズム効率はその良し悪しを測る主要な評価指標となっており、次の 2 つの観点を含みます。
- 時間効率：アルゴリズムの実行時間の長さ。
- 空間効率：アルゴリズムが使用するメモリ空間の大きさ。
簡単に言えば、**私たちの目標は「高速で省メモリ」なデータ構造とアルゴリズムを設計すること**です。そして、アルゴリズム効率を効果的に評価することは非常に重要です。そうすることで初めて、さまざまなアルゴリズムを比較し、さらにアルゴリズム設計と最適化の過程を導けるからです。
効率の評価方法は主に 2 種類に分けられます。実測と理論的な見積もりです。
2.1.1 実測¶
いまアルゴリズム A とアルゴリズム B があり、どちらも同じ問題を解けるとします。この 2 つのアルゴリズムの効率を比較する必要がある場合、最も直接的な方法は 1 台のコンピュータで両者を実行し、その実行時間とメモリ使用量を監視して記録することです。この評価方法は実際の状況を反映できますが、大きな制約もあります。
一方では、**テスト環境による干渉要因を排除しにくい**という問題があります。ハードウェア構成はアルゴリズムの性能に影響します。たとえば、並列度の高いアルゴリズムはマルチコア CPU での実行により適しており、メモリアクセスが集中的なアルゴリズムは高性能メモリ上でより良い性能を示します。つまり、異なるマシンでのテスト結果は一致しない可能性があります。これは、さまざまなマシンでテストして平均効率を統計的に求める必要があることを意味しますが、それは現実的ではありません。
他方では、**完全なテストを実施するには非常に多くの資源が必要**です。入力データ量が変化すると、アルゴリズムは異なる効率を示します。たとえば、入力データ量が小さいときはアルゴリズム A の実行時間がアルゴリズム B より短くても、入力データ量が大きいときには結果がちょうど逆になるかもしれません。そのため、説得力のある結論を得るには、さまざまな規模の入力データでテストする必要があり、それには大量の計算資源を要します。
2.1.2 理論的な見積もり¶
実測には大きな制約があるため、いくつかの計算だけによってアルゴリズムの効率を評価することを考えられます。この見積もり方法は漸近計算量解析（asymptotic complexity analysis）と呼ばれ、略して計算量解析といいます。
計算量解析は、アルゴリズムの実行に必要な時間資源と空間資源が入力データ規模とどのような関係にあるかを表します。これは、入力データ規模が増加するにつれて、アルゴリズムの実行に必要な時間と空間がどのように増加するかという傾向を記述するものです。この定義はややわかりにくいので、次の 3 つのポイントに分けて理解できます。
- 「時間資源と空間資源」は、それぞれ時間計算量（time complexity）と空間計算量（space complexity）に対応します。
- 「入力データ規模が増加するにつれて」とは、計算量がアルゴリズムの実行効率と入力データ規模との関係を反映していることを意味します。
- 「時間と空間の増加傾向」とは、計算量解析が注目するのは実行時間や使用空間の具体的な値ではなく、時間や空間の増加の「速さ」であることを示します。
計算量解析は実測という方法の欠点を克服しています。その点は次のように表れます。
- 実際にコードを動かす必要がなく、より環境にやさしく省エネルギーです。
- テスト環境から独立しており、解析結果はすべての実行プラットフォームに適用できます。
- 異なるデータ量におけるアルゴリズム効率を表せ、とくに大規模データ量での性能を反映できます。
Tip
それでも計算量の概念がまだわかりにくくても、心配はいりません。後続の章で詳しく説明します。
計算量解析は、アルゴリズム効率を評価するための「物差し」を私たちに与えてくれます。これにより、あるアルゴリズムの実行に必要な時間資源と空間資源を測り、異なるアルゴリズム同士の効率を比較できます。
計算量は数学的な概念であり、初学者にとってはやや抽象的で、学習の難度も比較的高いかもしれません。この観点から見ると、計算量解析は最初に紹介する内容としてはあまり適していない可能性があります。しかし、あるデータ構造やアルゴリズムの特徴を議論する際には、その実行速度や空間使用状況の分析を避けることはできません。
以上を踏まえると、データ構造とアルゴリズムを深く学ぶ前に、**まず計算量解析について初歩的な理解を持ち、簡単なアルゴリズムの計算量解析ができるようにしておくこと**を勧めます。