🎯 概要
プログラムの処理効率を評価する際に重要なのが 時間計算量（Time Complexity） と 空間計算量（Space Complexity） です。
これらは、アルゴリズムが どれくらいの時間 や メモリ を消費するかを表します。
🎯 時間計算量（Time Complexity）
時間計算量は、入力のサイズ n が大きくなるにつれて、処理時間がどのように増加するかを示します。
一般的に Big-O 記法（O 記法） を使って表し、以下のようなパターンがあります。
| 計算量 | 計算時間の増え方 | 例 | 適用シーン |
|---|---|---|---|
| O(1) | 常に一定 | 配列のインデックスアクセス | どんな場合でも最速 |
| O(log n) | ゆっくり増える | 二分探索 | データ量が大きくても高速に処理可能 |
| O(n) | 線形に増える | 配列のループ | 要素をすべてチェックする場合 |
| O(n log n) | 線形より速く増える | クイックソート、マージソート | 効率の良いソート |
| O(n²) | 急激に増える | 二重ループ | 小規模なデータセットなら許容可能 |
| O(2ⁿ) | 爆発的に増える | 再帰的なフィボナッチ |
n が大きくなると現実的に不可能 |
時間計算量の例とコード
O(1) - 定数時間
# 配列の特定のインデックスにアクセスする（O(1)）
numbers = [10, 20, 30, 40, 50]
print(numbers[2]) # 30 を取得
O(log n) - 二分探索
# 二分探索（O(log n)）
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
O(n) - 線形時間
# 配列の全要素を走査する（O(n)）
numbers = [1, 2, 3, 4, 5]
for num in numbers:
print(num)
O(n log n) - クイックソート
# クイックソート（O(n log n)）
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
O(n²) - 二重ループ（バブルソート）
# バブルソート（O(n²)）
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
O(2ⁿ) - 非効率なフィボナッチ
# フィボナッチ数列（指数時間 O(2ⁿ)）
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
🎯 空間計算量（Space Complexity）
空間計算量は、入力サイズ n に対して どれくらいメモリを使うか を示します。
これも Big-O 記法 で表現し、以下のようなパターンがあります。
| 計算量 | メモリ使用量の増え方 | 例 | 適用シーン |
|---|---|---|---|
| O(1) | 一定 | 単一の変数 | メモリを極力抑えたいとき |
| O(n) | 線形に増える | 新しいリストを作成 | 動的なデータ構造を扱う場合 |
| O(n²) | 急激に増える | 2次元配列 | 小規模なデータセットで使用 |
O(1) - 定数空間
# 変数を1つしか使わない（O(1)）
def add(a, b):
return a + b
O(n) - 線形空間
# O(n) - 配列のコピー（入力サイズに比例してメモリを消費）
original_list = [1, 2, 3, 4, 5]
# 新しいリストを作成（元のリストと同じサイズのメモリを使用）
copied_list = original_list.copy()
print(copied_list) # [1, 2, 3, 4, 5]
O(n²) - 2次元配列
# O(n²) - 2次元配列（メモリ使用量が n × n に比例）
n = 3
# 3×3 の行列（すべて 0 で初期化）
matrix = [[0] * n for _ in range(n)]
# 出力して確認
for row in matrix:
print(row)
# 出力結果:
# [0, 0, 0]
# [0, 0, 0]
# [0, 0, 0]