2.5 まとめ¶

アルゴリズム効率の評価

時間計算量

時間計算量は、アルゴリズムの実行時間がデータ量の増加に伴ってどう変化するかを測るためのものであり、効率評価に有効です。ただし、入力データ量が小さい場合や時間計算量が同じ場合などには、効率の優劣を正確に比較できないことがあります。
最悪時間計算量はビッグオー記法 \(O\) で表され、関数の漸近上界に対応し、\(n\) が正の無限大に近づくときの操作回数 \(T(n)\) の増加の度合いを表します。
時間計算量の推定は二段階に分かれ、まず操作回数を数え、次に漸近上界を判断します。
一般的な時間計算量を低い順から並べると、\(O(1)\)、\(O(\log n)\)、\(O(n)\)、\(O(n \log n)\)、\(O(n^2)\)、\(O(2^n)\)、\(O(n!)\) などがあります。
一部のアルゴリズムの時間計算量は固定ではなく、入力データの分布に関係します。時間計算量には最悪、最良、平均時間計算量がありますが、最良時間計算量は入力データが厳しい条件を満たす必要があるため、ほとんど使われません。
平均時間計算量は、ランダムな入力データに対するアルゴリズムの実行効率を表し、実運用時の性能に最も近い指標です。平均時間計算量を求めるには、入力データの分布と、それを踏まえた数学的期待値を統計する必要があります。

空間計算量

空間計算量の役割は時間計算量に似ており、アルゴリズムが使用するメモリ空間がデータ量の増加に伴ってどう変化するかを測ります。
アルゴリズム実行中に関係するメモリ空間は、入力空間、一時空間、出力空間に分けられます。通常、入力空間は空間計算量の計算に含めません。一時空間は一時データ、スタックフレーム空間、命令空間に分けられ、このうちスタックフレーム空間は通常、再帰関数でのみ空間計算量に影響します。
私たちは通常、最悪空間計算量のみに注目し、最悪の入力データと最悪の実行時点における空間計算量を数えます。
一般的な空間計算量を低い順から並べると、\(O(1)\)、\(O(\log n)\)、\(O(n)\)、\(O(n^2)\)、\(O(2^n)\) などがあります。

Q：尾再帰の空間計算量は \(O(1)\) ですか？

理論上、尾再帰関数の空間計算量は \(O(1)\) まで最適化できます。ただし、ほとんどのプログラミング言語（Java、Python、C++、Go、C# など）は尾再帰の自動最適化をサポートしていないため、通常は空間計算量を \(O(n)\) と見なします。

Q：関数とメソッドという二つの用語の違いは何ですか？

関数（function）は独立して実行でき、すべての引数は明示的に渡されます。メソッド（method）はオブジェクトに関連付けられ、それを呼び出すオブジェクトが暗黙的に渡され、クラスのインスタンスに含まれるデータを操作できます。

以下では、いくつかの一般的なプログラミング言語を例に説明します。

C 言語は手続き型プログラミング言語であり、オブジェクト指向の概念がないため、関数しかありません。ただし、構造体（struct）を作成してオブジェクト指向プログラミングを模倣でき、構造体に関連付けられた関数は、他のプログラミング言語におけるメソッドに相当します。
Java と C# はオブジェクト指向のプログラミング言語であり、コードブロック（メソッド）は通常あるクラスの一部です。静的メソッドの振る舞いは関数に似ており、クラスに束縛され、特定のインスタンス変数にはアクセスできません。
C++ と Python は、手続き型プログラミング（関数）にもオブジェクト指向プログラミング（メソッド）にも対応しています。

Q：「一般的な空間計算量の種類」の図が表しているのは、使用空間の絶対量ですか？

いいえ。この図が示しているのは空間計算量であり、表しているのは増加傾向であって、使用空間の絶対量ではありません。

\(n = 8\) と仮定すると、各曲線の値が対応する関数と一致していないように見えるかもしれません。これは、各曲線に定数項が含まれており、値の範囲を視覚的に見やすい範囲へ圧縮しているためです。

実際には、各手法の「定数項」の複雑度がどれほどか通常は分からないため、一般に複雑度だけを根拠に \(n = 8\) 以下で最適解を選ぶことはできません。ただし、\(n = 8^5\) であれば選びやすく、このときは増加傾向がすでに支配的になっています。

Q 実際の利用場面に応じて、時間（または空間）を犠牲にしてアルゴリズムを設計することはありますか？

実際の応用では、多くの場合、空間を犠牲にして時間を得る選択をします。たとえばデータベースのインデックスでは、通常 B+ 木やハッシュインデックスを構築し、大量のメモリ空間を使う代わりに、\(O(\log n)\) あるいは \(O(1)\) の高速な検索を実現します。

空間資源が貴重な場面では、時間を犠牲にして空間を得ることもあります。たとえば組み込み開発では、デバイスのメモリが非常に貴重なため、エンジニアはハッシュテーブルの使用をやめ、配列による順次探索を選んでメモリ使用量を節約することがあります。その代償として探索は遅くなります。