2.5 まとめ¶

1. 重要なレビュー¶

アルゴリズム効率評価

時間効率と空間効率は、アルゴリズムの優劣を評価する2つの主要な基準です。
実際のテストによってアルゴリズムの効率を評価できますが、テスト環境の影響を排除することは困難で、大量の計算リソースを消費します。
複雑度分析は実際のテストの欠点を克服できます。その結果はすべての動作プラットフォームに適用でき、異なるデータスケールでのアルゴリズムの効率を明らかにできます。

時間計算量

時間計算量は、データ量の増加に伴うアルゴリズムの実行時間の傾向を測定し、アルゴリズムの効率を効果的に評価します。しかし、入力データ量が少ない場合や時間計算量が同じ場合など、特定のケースでは失敗することがあり、アルゴリズムの効率を正確に比較することが困難になります。
最悪ケース時間計算量はビッグ\(O\)記法を使用して表記され、漸近上限を表し、\(n\)が無限大に近づくにつれての操作数\(T(n)\)の増加レベルを反映します。
時間計算量の計算には2つのステップが含まれます：まず操作数をカウントし、次に漸近上限を決定します。
一般的な時間計算量は、低いものから高いものへと並べると、\(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)\)などが含まれます。

2. Q & A¶

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

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

Q: 「関数」と「メソッド」という用語の違いは何ですか？

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

一般的なプログラミング言語からの例をいくつか示します：

Cは手続き型プログラミング言語で、オブジェクト指向の概念がないため、関数のみがあります。しかし、構造体（struct）を作成することでオブジェクト指向プログラミングをシミュレートでき、これらの構造体に関連付けられた関数は他のプログラミング言語のメソッドと同等です。
JavaとC#はオブジェクト指向プログラミング言語で、コードブロック（メソッド）は通常クラスの一部です。静的メソッドはクラスにバインドされ、特定のインスタンス変数にアクセスできないため、関数のように動作します。
C++とPythonは手続き型プログラミング（関数）とオブジェクト指向プログラミング（メソッド）の両方をサポートしています。

Q: 「空間計算量の一般的な種類」の図は、占有空間の絶対サイズを反映していますか？

いいえ、図は空間計算量を示しており、これは増加傾向を反映するものであり、占有空間の絶対サイズではありません。

\(n = 8\)を取ると、各曲線の値がその関数に対応していないことに気づくかもしれません。これは、各曲線に定数項が含まれているためで、値の範囲を視覚的に快適な範囲に圧縮することを意図しています。

実際には、通常は各メソッドの「定数項」複雑度を知らないため、複雑度のみに基づいて\(n = 8\)の最良ソリューションを選択することは一般的に不可能です。しかし、\(n = 8^5\)の場合、増加傾向が支配的になるため、選択がはるかに容易になります。