計算量（Computational Complexity）

アルゴリズムがどれだけ効率的に動作するかを表す指標。
ある問題を解くのにどれくらい手間を要したかを数値で表したもの。
計算量を意識することで、より効率的でスケーラブルなプログラムを設計することができる。
計算量は、主に「時間計算量」と「空間計算量」の2つに分けられる。

1. 時間計算量（Time Complexity）

時間計算量は、アルゴリズムが実行されるのにかかる時間を表す。
コンピュータが特定の手順に従って与えられた問題を解く際に必要とする手順の回数のこと。
具体的には、入力サイズが大きくなるにつれて、アルゴリズムの実行時間がどのように増加するかを示す。

代表的な時間計算量

O(1)　定数時間：入力サイズに関係なく、常に一定時間で実行される。

（例）配列の特定の要素にアクセスする。

O(log n)　対数時間：入力サイズが大きくなっても、実行時間はゆっくりと増加する。

（例）二分探索。

O(n)　線形時間：入力サイズに比例して実行時間が増加する。

（例）配列の全要素を走査する。

O(n log n)　線形対数時間：入力サイズが大きくなると、実行時間は線形よりも速く増加する。

（例）クイックソートやマージソート。

O(n^2)　二乗時間：入力サイズの二乗に比例して実行時間が増加する。

（例）バブルソートや選択ソート。

O(2^n)　 指数時間：入力サイズが大きくなると、実行時間が急激に増加する。

（例）ナップサック問題の総当たり解法。

2. 空間計算量（Space Complexity）

アルゴリズムが実行されるのに必要なメモリの量を表す。これも入力サイズに依存する。
コンピュータが特定の手順に従って与えられた問題を解く際に必要とする記憶領域の容量のこと。

代表的な空間計算量

O(1)　定数空間：入力サイズに関係なく、常に一定のメモリを使用する。

（例）単純な変数の使用。

O(n)　線形空間：入力サイズに比例してメモリ使用量が増加する。

（例）配列やリストの格納。

O(n^2)　二乗空間：入力サイズの二乗に比例してメモリ使用量が増加する。

例: 二次元配列の格納。

計算量の重要性
計算量を理解することで、アルゴリズムの効率を評価し、適切なアルゴリズムを選択することができる。特に大規模なデータを扱う場合、計算量が小さいアルゴリズムを選ぶことが重要。
（例）
ソートアルゴリズムを選ぶ場合、データ量が少ない場合はバブルソート（O(n^2)）でも問題ありませんが、データ量が大きい場合はクイックソート（O(n log n)）やマージソート（O(n log n)）を選ぶべき。

O 記法（Bachmann-Landau O-notation）

アルゴリズムの計算量を表すための数学的な記法。
特に、アルゴリズムの最悪の場合の振る舞いを記述するために使われる。
O記法を使うことで、アルゴリズムを実際に計算しなくとも大まかに計算時間を測ることができる。
アルゴリズムの効率を簡単に比較・評価することができる。

例1：線形探索
線形探索の時間計算量は O(n)
最悪の場合、配列の全要素を走査する必要があるため

例2：二分探索
二分探索の時間計算量は O(log n)
最悪の場合でも、探索範囲が半分ずつ減少していくため

その他： O(n^2) , O(2 ^ n) , O(n log n) などがある。

O記法の重要性
O記法を使うことで、アルゴリズムの効率を簡単に比較・評価することができる。
特に大規模なデータを扱う場合、計算量が小さいアルゴリズムを選ぶことが重要。

※通常入力サイズ n に対して、計算量が n のように綺麗に収まることはなく、n^2 + 8n + 9 のように複雑になることがほとんど。このような場合に、最高次数の項以外を無視して考えることによって、大まかに計算を行うことができる。

◎コンピュータに物理制限があるため、アルゴリズムを実装する際は、時間計算量、空間計算量を意識しながら最適化されたコードを書くことが非常に重要

スタックオーバーフロー（stack overflow）

スタックオーバーフローのよくある発生原因として、ベースケースが機能しておらず、再帰関数が無限に呼び出されたり、空間計算量が大きいこと（O(2^n)等）が挙げられる。