アルゴリズムの計算量：Time ComplexityとSpace Complexityの基礎

はじめに

アルゴリズムの効率を評価する際、主に2つの観点があります：

• Time Complexity（時間計算量）：実行時間の効率
• Space Complexity（空間計算量）：メモリ使用量の効率

Time Complexity（時間計算量）

時間計算量は、入力サイズに対してアルゴリズムが必要とする処理時間の増加率を表します。実務では、O(n) 以下の時間計算量を持つアルゴリズムが望ましいとされています。

主なTime Complexityの種類

• O(1)：定数時間
  • 入力サイズに関係なく、常に同じ時間で処理が完了
  • 例：配列の先頭要素へのアクセス

def get_first_element(arr):
    if arr:
        return arr[0]  # O(1)
    return None

• O(log n)：対数時間
  • 入力サイズが2倍になると、処理時間が1段階増加
  • 例：二分探索

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:  # O(log n)
        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)：線形時間
  • 入力サイズに比例して処理時間が増加
  • 例：配列の線形探索

def linear_search(arr, target):
    for i in range(len(arr)):  # O(n)
        if arr[i] == target:
            return i
    return -1

• O(n log n)
  • 比較的効率的な並び替えアルゴリズムの計算量
  • 例：クイックソート

def quicksort(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 quicksort(left) + middle + quicksort(right)  # O(n log n)

• O(n²)：二次時間
  • 入力サイズの2乗に比例して処理時間が増加
  • 例：バブルソート

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):  # O(n²)
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Space Complexity（空間計算量）

空間計算量は、アルゴリズムの実行に必要なメモリ量の増加率を表します。メモリ効率を重視する場合、O(1)の空間計算量（定数空間）を目指すことが理想的です。

主な特徴

1. 入力データのサイズ

   • 入力データ自体が必要とするメモリ

2. 補助スペース

   • アルゴリズムが追加で必要とするメモリ
   • 一時変数、再帰呼び出しのスタックなど

一般的なSpace Complexityの例

• O(1)：定数空間
  • 入力サイズに関係なく、固定量のメモリのみ使用
  • 例：インプレースでの配列要素の交換

def swap_first_last(arr):
    if len(arr) <= 1:
        return
    arr[0], arr[-1] = arr[-1], arr[0]  # O(1) space

• O(n)：線形空間
  • 入力サイズに比例してメモリ使用量が増加
  • 例：配列のコピー作成

def double_array(arr):
    result = []  # O(n) space
    for num in arr:
        result.append(num * 2)
    return result

実践的な指針

1. Time Complexityについて

   • O(n) 以下を目指すべき
   • O(n log n) までは許容範囲
   • O(n²) 以上は可能な限り避ける
   • 小さな入力サイズでは、定数倍の違いが重要になることもある

2. Space Complexityについて

   • O(1) が理想的
   • メモリに余裕がある場合は、時間計算量との兼ね合いで O(n) も許容
   • 再帰アルゴリズムではスタック領域の使用に注意

このグラフから分かるように、O(1)、O(log n)、O(n) は効率的な計算量で、入力サイズが大きくなっても比較的緩やかな増加を示します。一方、O(n²) は入力サイズの増加に対して急激に処理時間/空間が増加するため、大きな入力サイズに対しては非効率となります。

まとめ

• Time Complexityは処理時間の効率を評価
• Space Complexityはメモリ使用量の効率を評価
• 実用的なコードでは Time Complexity O(n) 以下、Space Complexity O(1) を目指す
• アルゴリズムの選択時は、両方の計算量を考慮することが重要
• 実際の応用では、しばしばTime ComplexityとSpace Complexityのトレードオフを検討する必要がある