アルゴリズムの計算量

§1 概要

アルゴリズムの計算量（Algorithm Complexity）は、アルゴリズムが問題を解くのに必要な計算資源（時間やメモリ）を定量的に評価する尺度である。効率的なアルゴリズムの設計、問題の本質的な難しさの理解、実用的なプログラムの性能予測において不可欠な概念である。

計算量理論により、多項式時間で解ける問題（クラスP）、検証が多項式時間の問題（クラスNP）、計算不可能な問題などが分類され、アルゴリズムの限界と可能性が明らかになっている。

§2 時間計算量

基本演算とは、比較、代入、算術演算など、定数時間で実行できる操作を指す。

最悪時間計算量

すべての入力に対する実行時間の最大値： $$T_{\text{worst}}(n) = \max_{\text{size}(I) = n} T(I)$$ 通常「計算量」といえば最悪時間計算量を指す。

平均時間計算量

入力の分布を仮定したときの期待実行時間： $$T_{\text{avg}}(n) = \mathbb{E}[T(I) \mid \text{size}(I) = n]$$

最良時間計算量

最も有利な入力に対する実行時間の最小値（通常あまり重要でない）。

§3 O記法（漸近記法）

計算量を簡潔に表現するため、O記法（Big-O notation）が用いられる。

O（ビッグオー）

Ω（ビッグオメガ）

$f(n) = \Omega(g(n))$: $f$ は漸近的に $g$ で下から抑えられる（$f(n) \geq C \cdot g(n)$ for large $n$）。

Θ（ビッグシータ）

$f(n) = \Theta(g(n))$: $f(n) = O(g(n))$ かつ $f(n) = \Omega(g(n))$（$f$ と $g$ は同じオーダー）。

§4 代表的な計算量クラス

§5 例

例1: 線形探索

def linear_search(arr, target):
    for i in range(len(arr)):  # n回のループ
        if arr[i] == target:   # 定数時間の比較
            return i
    return -1

例2: 二分探索

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

例3: バブルソート

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):         # 外側ループ: n回
        for j in range(n-i-1): # 内側ループ: 最大n回
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

例4: マージソート

§6 空間計算量

アルゴリズムが使用するメモリ容量を入力サイズ $n$ の関数として表す。

• In-placeアルゴリズム: $O(1)$ の追加メモリ（バブルソート、ヒープソート）
• 再帰アルゴリズム: スタック深さに比例（マージソートは $O(n)$、二分探索は $O(\log n)$）

§7 計算量クラスP, NP

クラスP（Polynomial time）

決定性チューリング機械で多項式時間で解ける問題のクラス。実用的に「効率的に解ける」問題。

例: ソート、最短経路（Dijkstraアルゴリズム）、線形計画問題

クラスNP（Nondeterministic Polynomial time）

解の正当性を多項式時間で検証できる問題のクラス。非決定性チューリング機械で多項式時間で解ける。

例: 充足可能性問題（SAT）、グラフの彩色、ナップサック問題

NP完全問題

NPで最も難しいクラス。あるNP完全問題が多項式時間で解ければ、すべてのNP問題が多項式時間で解ける。

例: SAT、ハミルトン閉路、巡回セールスマン問題（TSP）

P vs NP 問題

§8 応用

アルゴリズム設計

効率的なアルゴリズムの選択・設計。問題サイズが大きい場合、$O(n \log n)$ と $O(n^2)$ の差は実行時間に劇的な影響を与える。

データ構造の選択

操作の計算量により最適なデータ構造を選ぶ（配列、連結リスト、ハッシュテーブル、平衡木など）。

暗号理論

RSA暗号の安全性は、素因数分解の計算量が指数的であることに基づく（既知の多項式時間アルゴリズムなし）。

機械学習

訓練アルゴリズムの計算量評価。データサイズ $n$、特徴数 $d$、イテレーション数に依存（例: 線形回帰 $O(nd^2)$、k-meansは反復的）。

最適化問題

NP困難問題に対しては、近似アルゴリズムやヒューリスティック（遺伝的アルゴリズム、焼きなまし法）を用いる。

§9 実装例（計算量測定）

Python

import time
import matplotlib.pyplot as plt  # pip install matplotlib

def measure_time(func, arr):
    """関数の実行時間を測定"""
    arr_copy = arr.copy()
    start = time.time()
    func(arr_copy)
    return time.time() - start

# アルゴリズムの定義
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]

# 計算量の実験的検証
sizes = [100, 200, 400, 800, 1600]
times = []

for n in sizes:
    arr = list(range(n, 0, -1))  # 最悪ケース（降順）
    t = measure_time(bubble_sort, arr)
    times.append(t)
    print(f"n={n}: {t:.6f} sec")

# プロット
plt.plot(sizes, times, 'o-', label='Bubble Sort')
plt.xlabel('Array Size (n)')
plt.ylabel('Time (sec)')
plt.title('Time Complexity of Bubble Sort')
plt.legend()
plt.grid()
plt.show()

# O(n^2) の確認: t ≈ C*n^2
# t[i] / n[i]^2 がほぼ一定なら O(n^2)

§10 参考文献

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Knuth, D. E. (1997–2011). The Art of Computer Programming, Vol. 1–4A. Addison-Wesley.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
• Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
• Weisstein, E. W. "Computational Complexity." From MathWorld--A Wolfram Web Resource.