実行時間オーダー完全攻略教科書
目次
- 実行時間オーダーとは
- 漸近記法の数学的基礎
- 主な時間計算量のパターンと特性
- アルゴリズム解析手法
- 発展的解析技法
- 実際のシステムでの考慮事項
- 競技プログラミングでの実践
- 研究レベルの話題
- 総合演習と実践問題
1. 実行時間オーダーとは
1.1 計算量理論の位置づけ
実行時間オーダーは**計算量理論（Computational Complexity Theory）**の基礎概念です。これは以下の重要な問いに答えます：
- どのくらい速く問題を解けるか？（時間計算量）
- どのくらいのメモリが必要か？（空間計算量）
- 問題の本質的な難しさは何か？
1.2 歴史的背景
- 1960年代：Hartmanis-Stearnsによる計算量理論の基礎
- 1971年：Stephen CookによるNP完全性の概念
- 1979年：Knuthによる漸近記法の体系化
1.3 実世界での重要性
スケーラビリティの法則
現実のシステムで重要なのは、データサイズの増加に対する性能の変化です：
データサイズ O(n) O(n log n) O(n²) O(2ⁿ)
1,000 1ms 10ms 1s 実質不可能
10,000 10ms 133ms 100s 実質不可能
100,000 100ms 1.7s 2.8時間 実質不可能
1,000,000 1s 20s 11.5日 実質不可能
2. 漸近記法の数学的基礎
2.1 厳密な定義
Big O記法（上界）
f(n) = O(g(n)) ⟺ ∃c > 0, n₀ > 0 such that ∀n ≥ n₀: f(n) ≤ c·g(n)
# 例：3n² + 5n + 2 = O(n²)
# c = 4, n₀ = 5 とすると
# n ≥ 5 のとき 3n² + 5n + 2 ≤ 4n² が成り立つ
Big Ω記法（下界）
f(n) = Ω(g(n)) ⟺ ∃c > 0, n₀ > 0 such that ∀n ≥ n₀: f(n) ≥ c·g(n)
Big Θ記法（厳密な階数）
f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) and f(n) = Ω(g(n))
Little o記法（厳密に小さい）
f(n) = o(g(n)) ⟺ lim[n→∞] f(n)/g(n) = 0
Little ω記法（厳密に大きい）
f(n) = ω(g(n)) ⟺ lim[n→∞] f(n)/g(n) = ∞
2.2 漸近記法の性質
推移律
- f = O(g), g = O(h) ⟹ f = O(h)
加法性
- f₁ = O(g), f₂ = O(g) ⟹ f₁ + f₂ = O(g)
乗法性
- f₁ = O(g₁), f₂ = O(g₂) ⟹ f₁ · f₂ = O(g₁ · g₂)
2.3 よくある間違いと注意点
# 間違い：O(n) + O(n) = O(2n) = O(n)は常に正しいが...
def misleading_example(arr):
# 第1部：O(n) - 配列の合計
total = sum(arr) # 実際は高度に最適化されている
# 第2部：O(n) - 線形探索
for i, val in enumerate(arr): # Python処理系に依存
if val == target:
return i
# 実際の実行時間は定数倍の違いが大きい場合がある
3. 主な時間計算量のパターンと特性
3.1 詳細な分類と実例
O(1) - 定数時間
# ハッシュテーブル操作（期待値）
def hash_operations():
d = {}
d['key'] = 'value' # O(1)
val = d.get('key') # O(1)
del d['key'] # O(1)
# 配列のランダムアクセス
def array_access(arr, index):
return arr[index] # O(1)
# ビット演算
def bit_operations(x, y):
return x & y, x | y, x ^ y # 全てO(1)
O(log n) - 対数時間の詳細分析
# 二分探索の変種
def binary_search_leftmost(arr, target):
"""最初に現れる位置を探す"""
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
# 平衡二分探索木（AVL、赤黒木）
class AVLNode:
def search(self, key): # O(log n)
# 高さがO(log n)に保たれているため
pass
def insert(self, key): # O(log n)
# 挿入後の再平衡化込み
pass
# ヒープ操作
import heapq
def heap_operations(arr):
heapq.heapify(arr) # O(n)
heapq.heappush(arr, val) # O(log n)
min_val = heapq.heappop(arr) # O(log n)
O(n) - 線形時間の最適化
# キャッシュ効率を考慮した線形処理
def cache_friendly_sum(matrix):
"""行優先アクセスでキャッシュミスを削減"""
total = 0
rows, cols = len(matrix), len(matrix[0])
for i in range(rows): # 外側：行
for j in range(cols): # 内側：列
total += matrix[i][j]
return total # O(n×m)だがキャッシュ効率良好
def cache_unfriendly_sum(matrix):
"""列優先アクセス - キャッシュミスが多い"""
total = 0
rows, cols = len(matrix), len(matrix[0])
for j in range(cols): # 外側：列
for i in range(rows): # 内側：行
total += matrix[i][j]
return total # 同じO(n×m)だが実行時間は遅い
O(n log n) - 分割統治法のマスターピース
# マージソートの詳細実装
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # T(n/2)
right = merge_sort(arr[mid:]) # T(n/2)
return merge(left, right) # O(n)
# 全体：T(n) = 2T(n/2) + O(n) = O(n log n)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# FFT（高速フーリエ変換）- 信号処理で重要
def fft_multiply(a, b):
"""多項式の掛け算をO(n log n)で実行"""
# 通常のO(n²)から大幅な改善
pass
O(n²) - 二次時間とその改善
# 動的プログラミングでの典型例
def longest_common_subsequence(s1, s2):
"""2つの文字列の最長共通部分列"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1): # O(m)
for j in range(1, n + 1): # O(n)
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n] # O(m×n)
# 最適化可能な例
def three_sum_naive(nums, target):
"""3つの数の和がtargetになる組み合わせを探す - O(n³)"""
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == target:
return [i, j, k]
return None
def three_sum_optimized(nums, target):
"""ソート + 二分探索でO(n²)に改善"""
nums.sort()
n = len(nums)
for i in range(n - 2):
j, k = i + 1, n - 1
while j < k:
current_sum = nums[i] + nums[j] + nums[k]
if current_sum == target:
return [i, j, k]
elif current_sum < target:
j += 1
else:
k -= 1
return None
3.2 より複雑な時間計算量
O(n^k) - 多項式時間
# k-重ループの一般形
def k_nested_loops(arr, k):
"""k重ネストループの一般的なパターン"""
def recurse(depth, current_indices):
if depth == k:
# 実際の処理 - O(1)
process(current_indices)
return
for i in range(len(arr)):
current_indices.append(i)
recurse(depth + 1, current_indices)
current_indices.pop()
recurse(0, [])
# 時間計算量：O(n^k)
O(2^n) - 指数時間
# 部分集合の生成
def generate_subsets(arr):
"""全ての部分集合を生成 - O(2^n)"""
def backtrack(start, current):
result.append(current[:]) # 現在の部分集合を追加
for i in range(start, len(arr)):
current.append(arr[i])
backtrack(i + 1, current) # 2^(n-i-1)回の再帰
current.pop()
result = []
backtrack(0, [])
return result
# 最適化：ビット演算を使った実装
def generate_subsets_bit(arr):
"""ビット演算で部分集合生成 - 同じO(2^n)だが定数倍が小さい"""
n = len(arr)
result = []
for mask in range(1 << n): # 0から2^n-1まで
subset = []
for i in range(n):
if mask & (1 << i):
subset.append(arr[i])
result.append(subset)
return result
O(n!) - 階乗時間
# 全順列の生成
def generate_permutations(arr):
"""全順列を生成 - O(n!)"""
if len(arr) <= 1:
return [arr]
result = []
for i in range(len(arr)):
rest = arr[:i] + arr[i+1:]
for perm in generate_permutations(rest):
result.append([arr[i]] + perm)
return result
# 巡回セールスマン問題（動的プログラミング版）
def tsp_dp(graph):
"""O(n² × 2^n) - 全探索O(n!)より大幅改善"""
n = len(graph)
# dp[mask][i] = マスクで表される都市集合を訪問し、都市iで終わる最小コスト
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 開始都市
for mask in range(1 << n):
for u in range(n):
if dp[mask][u] == float('inf'):
continue
for v in range(n):
if mask & (1 << v):
continue
next_mask = mask | (1 << v)
dp[next_mask][v] = min(dp[next_mask][v],
dp[mask][u] + graph[u][v])
# 全都市を訪問して開始都市に戻る最小コスト
return min(dp[(1 << n) - 1][i] + graph[i][0] for i in range(1, n))
4. アルゴリズム解析手法
4.1 マスター定理（Master Theorem）
分割統治法のアルゴリズムの時間計算量を求める強力な道具：
T(n) = aT(n/b) + f(n) の形の漸化式に対して：
- f(n) = O(n^(log_b(a) - ε)) for some ε > 0 ⟹ T(n) = Θ(n^log_b(a))
- f(n) = Θ(n^log_b(a)) ⟹ T(n) = Θ(n^log_b(a) × log n)
- f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0, and af(n/b) ≤ cf(n) for some c < 1 ⟹ T(n) = Θ(f(n))
# 具体例での適用
def master_theorem_examples():
# 例1：マージソート
# T(n) = 2T(n/2) + O(n)
# a=2, b=2, f(n)=n, log_b(a)=log_2(2)=1
# f(n) = n = Θ(n^1) → ケース2 → T(n) = Θ(n log n)
# 例2：二分探索
# T(n) = T(n/2) + O(1)
# a=1, b=2, f(n)=1, log_b(a)=log_2(1)=0
# f(n) = 1 = Θ(n^0) → ケース2 → T(n) = Θ(log n)
# 例3：Karatsuba乗算
# T(n) = 3T(n/2) + O(n)
# a=3, b=2, f(n)=n, log_b(a)=log_2(3)≈1.58
# f(n) = n = O(n^(1.58-ε)) → ケース1 → T(n) = Θ(n^1.58)
pass
4.2 アモータイズド解析（Amortized Analysis）
一連の操作の平均コストを分析する手法：
例：動的配列（Dynamic Array）
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.data = [None] * self.capacity
def append(self, value):
if self.size == self.capacity:
# 容量を2倍に拡張 - O(n)
old_data = self.data
self.capacity *= 2
self.data = [None] * self.capacity
for i in range(self.size):
self.data[i] = old_data[i]
self.data[self.size] = value
self.size += 1
# 個々の操作は最悪O(n)だが、アモータイズドコストはO(1)
# 解析：n回のappend操作のコスト
# - 通常の挿入：n回 × O(1) = O(n)
# - リサイズ：1 + 2 + 4 + ... + n ≤ 2n = O(n)
# - 合計：O(n) + O(n) = O(n)
# - アモータイズドコスト：O(n)/n = O(1)
ポテンシャル法による厳密な解析
def potential_analysis():
"""
ポテンシャル関数 Φ(D) = 2×size - capacity
各append操作のアモータイズドコスト：
- リサイズなし：actual_cost + ΔΦ = 1 + 2 = 3 = O(1)
- リサイズあり：actual_cost + ΔΦ = size + (0 - size) = 0 = O(1)
"""
pass
4.3 確率的解析
期待値による解析
import random
def randomized_quicksort(arr):
"""ランダム化クイックソート"""
if len(arr) <= 1:
return arr
# ランダムにピボットを選択
pivot_idx = random.randint(0, len(arr) - 1)
pivot = arr[pivot_idx]
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 (randomized_quicksort(left) +
middle +
randomized_quicksort(right))
# 期待実行時間の解析：
# E[T(n)] = E[分割コスト] + E[左部分の時間] + E[右部分の時間]
# = O(n) + (1/n)Σ[E[T(k)] + E[T(n-1-k)]] for k=0 to n-1
# 解くと：E[T(n)] = O(n log n)
ラスベガス vs モンテカルロアルゴリズム
def miller_rabin_primality(n, k=10):
"""Miller-Rabin素数判定 - モンテカルロアルゴリズム"""
if n < 2:
return False
# n-1 = 2^r × d の形に分解
r = 0
d = n - 1
while d % 2 == 0:
r += 1
d //= 2
# k回のテストを実行
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False # 合成数
return True # おそらく素数（誤り確率 ≤ 4^(-k)）
# 期待実行時間：O(k log³ n)
# 誤り確率：≤ (1/4)^k
5. 発展的解析技法
5.1 並列アルゴリズムの解析
PRAM（Parallel Random Access Machine）モデル
import threading
import time
def parallel_sum_example(arr, num_threads=4):
"""並列合計計算の例"""
n = len(arr)
chunk_size = n // num_threads
results = [0] * num_threads
def worker(thread_id, start, end):
results[thread_id] = sum(arr[start:end])
threads = []
for i in range(num_threads):
start = i * chunk_size
end = (i + 1) * chunk_size if i < num_threads - 1 else n
thread = threading.Thread(target=worker, args=(i, start, end))
threads.append(thread)
thread.start()
for thread in threads:
thread.join()
return sum(results)
# 並列計算量の指標：
# - Work: W(n) = 総計算量 = O(n)
# - Span: S(n) = 最長依存チェーン = O(log n)（リダクション木の高さ）
# - 並列度: P(n) = W(n)/S(n) = O(n/log n)
MapReduceパラダイム
def map_reduce_word_count(documents):
"""MapReduceによる単語カウント"""
# Map phase - O(n) with m machines: O(n/m)
def map_phase(doc):
word_counts = {}
for word in doc.split():
word_counts[word] = word_counts.get(word, 0) + 1
return [(word, count) for word, count in word_counts.items()]
# Shuffle phase - O(n log n) (sorting)
def shuffle_phase(mapped_data):
from collections import defaultdict
shuffled = defaultdict(list)
for word, count in mapped_data:
shuffled[word].append(count)
return shuffled
# Reduce phase - O(n/m) per machine
def reduce_phase(word, counts):
return (word, sum(counts))
# 全体の並列実行時間：O(n/m + log n)
pass
5.2 キャッシュ効率の解析
Cache-Oblivious Algorithm
def cache_oblivious_matrix_multiply(A, B, C, n):
"""キャッシュ効率を意識した行列乗算"""
if n <= THRESHOLD: # 基底ケース
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
return
# 再帰的に分割
m = n // 2
# A = [A11 A12], B = [B11 B12], C = [C11 C12]
# [A21 A22] [B21 B22] [C21 C22]
# C11 += A11*B11 + A12*B21
cache_oblivious_matrix_multiply(A11, B11, C11, m)
cache_oblivious_matrix_multiply(A12, B21, C11, m)
# 他の部分も同様...
# キャッシュミス数：O(n³/B + n²/√M)
# B: ブロックサイズ, M: キャッシュサイズ
5.3 オンラインアルゴリズムと競合比
def online_paging_lru(cache_size, page_requests):
"""LRUページング - オンラインアルゴリズム"""
cache = []
page_faults = 0
for page in page_requests:
if page not in cache:
page_faults += 1
if len(cache) < cache_size:
cache.append(page)
else:
# 最も古いページを削除
cache.pop(0)
cache.append(page)
else:
# ページを最新に移動
cache.remove(page)
cache.append(page)
return page_faults
# 競合比の解析：
# LRUの競合比は k（kはキャッシュサイズ）
# つまり、OPT（最適解）のk倍以下のページフォルトに抑えられる
6. 実際のシステムでの考慮事項
6.1 現代のハードウェア特性
メモリ階層とその影響
import numpy as np
import time
def cache_awareness_demo():
"""キャッシュ効率の実測"""
n = 1000
# ケース1：行優先アクセス（キャッシュフレンドリー）
matrix = np.random.rand(n, n)
start = time.time()
total = 0
for i in range(n):
for j in range(n):
total += matrix[i, j]
row_major_time = time.time() - start
# ケース2：列優先アクセス（キャッシュアンフレンドリー）
start = time.time()
total = 0
for j in range(n):
for i in range(n):
total += matrix[i, j]
col_major_time = time.time() - start
print(f"行優先: {row_major_time:.4f}s")
print(f"列優先: {col_major_time:.4f}s")
print(f"比率: {col_major_time/row_major_time:.2f}x")
# 理論上は同じO(n²)だが、実行時間は大きく異なる
SIMD（Single Instruction, Multiple Data）の活用
import numpy as np
def simd_vectorization_example():
"""ベクトル化による高速化"""
n = 1000000
a = np.random.rand(n)
b = np.random.rand(n)
# スカラー実装
start = time.time()
result_scalar = np.zeros(n)
for i in range(n):
result_scalar[i] = a[i] * b[i] + np.sin(a[i])
scalar_time = time.time() - start
# ベクトル化実装
start = time.time()
result_vector = a * b + np.sin(a)
vector_time = time.time() - start
print(f"スカラー版: {scalar_time:.4f}s")
print(f"ベクトル版: {vector_time:.4f}s")
print(f"高速化: {scalar_time/vector_time:.1f}x")
# 同じO(n)だが、SIMD命令により大幅高速化
6.2 分散システムでの計算量
CAP定理との関係
class DistributedHashTable:
"""分散ハッシュテーブルの例"""
def __init__(self, num_nodes, replication_factor):
self.num_nodes = num_nodes
self.replication_factor = replication_factor
def put(self, key, value):
"""書き込み操作の計算量分析"""
# 1. ハッシュ計算: O(1)
node = hash(key) % self.num_nodes
# 2. レプリケーション: O(r) where r = replication_factor
# ネットワーク遅延: O(1) per node
# 一貫性保証: O(r) のコンセンサス
# 強一貫性の場合：O(r) + network_delay
# 結果整合性の場合：O(1) + background_sync
pass
def get(self, key):
"""読み込み操作"""
# 最寄りのレプリカから読み込み: O(1) + network_delay
# 読み取り修復: background O(r)
pass
# 分散システムの計算量特性：
# - ローカル計算 vs ネットワーク通信のトレードオフ
# - 一貫性レベルと性能のトレードオフ
# - パーティション耐性の影響
7. 競技プログラミングでの実践
7.1 制約から計算量を逆算
def constraint_to_complexity():
"""制約条件から必要な計算量を判断"""
constraints = {
"n ≤ 10": "O(n!) でも可能（全順列）",
"n ≤ 20": "O(2^n) でも可能（ビット演算）",
"n ≤ 100": "O(n³) まで（3重ループ）",
"n ≤ 1,000": "O(n²) まで（2重ループ）",
"n ≤ 100,000": "O(n log n) まで（ソート系）",
"n ≤ 1,000,000": "O(n) または O(log n)（線形・二分探索）",
"n ≤ 10^9": "O(log n) または O(1)（数学的解法）"
}
# 実際の問題での判断例
def solve_based_on_constraints(n, time_limit_sec=2):
operations_per_sec = 10**8 # 概算
max_operations = operations_per_sec * time_limit_sec
if n <= 20 and 2**n <= max_operations:
return "bit_manipulation_or_backtracking"
elif n <= 1000 and n**2 <= max_operations:
return "dynamic_programming"
elif n <= 100000 and n * math.log2(n) <= max_operations:
return "sort_or_divide_conquer"
else:
return "linear_or_mathematical"
7.2 実装テクニックと定数倍最適化
# 高速入出力
import sys
input = sys.stdin.readline
def fast_io_techniques():
"""競技プログラミングでの高速化テクニック"""
# 1. 入力の高速化
n = int(input())
arr = list(map(int, input().split()))
# 2. 出力のバッファリング
result = []
for i in range(n):
result.append(str(process(arr[i])))
print('\n'.join(result))
# 3. リスト内包表記の活用
squares = [x*x for x in range(n) if x % 2 == 0]
# 4. ビット演算の活用
def is_power_of_two(x):
return x > 0 and (x & (x - 1)) == 0
def count_set_bits(x):
return bin(x).count('1') # または x.bit_count() in Python 3.10+
# セグメント木での実践例
class SegmentTree:
"""区間最小値クエリ - O(log n)"""
def __init__(self, arr):
self.n = len(arr)
self.tree = [float('inf')] * (4 * self.n)
self.build(arr, 1, 0, self.n - 1)
def build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self.build(arr, 2*node, start, mid)
self.build(arr, 2*node+1, mid+1, end)
self.tree[node] = min(self.tree[2*node], self.tree[2*node+1])
def query(self, node, start, end, l, r):
if r < start or end < l:
return float('inf')
if l <= start and end <= r:
return self.tree[node]
mid = (start + end) // 2
left_min = self.query(2*node, start, mid, l, r)
right_min = self.query(2*node+1, mid+1, end, l, r)
return min(left_min, right_min)
def range_min_query(self, l, r):
return self.query(1, 0, self.n-1, l, r)
8. 研究レベルの話題
8.1 近似アルゴリズムと近似比
def vertex_cover_approximation(graph):
"""頂点被覆の2-近似アルゴリズム"""
# グラフの各辺について、両端点の少なくとも一方を選ぶ
cover = set()
edges = graph.get_edges()
while edges:
# 任意の辺(u,v)を選択
u, v = edges.pop()
cover.add(u)
cover.add(v)
# u,vに接続する全ての辺を削除
edges = [(x, y) for x, y in edges if x != u and x != v and y != u and y != v]
return cover
# 近似比：2（最適解の2倍以下を保証）
# 実行時間：O(|E|)
def tsp_christofides(graph):
"""巡回セールスマン問題のChristofidesアルゴリズム"""
# 1. 最小全域木を構築: O(E log V)
mst = minimum_spanning_tree(graph)
# 2. 奇数次数頂点を見つける: O(V)
odd_vertices = find_odd_degree_vertices(mst)
# 3. 奇数次数頂点間の最小重み完全マッチング: O(V³)
matching = min_weight_perfect_matching(odd_vertices, graph)
# 4. MST + マッチングでオイラーグラフを構成: O(V + E)
eulerian_graph = combine(mst, matching)
# 5. オイラー回路を見つける: O(V + E)
euler_circuit = find_euler_circuit(eulerian_graph)
# 6. ショートカットでハミルトン回路に変換: O(V)
hamilton_circuit = shortcut(euler_circuit)
return hamilton_circuit
# 近似比：1.5（最適解の1.5倍以下）
# 実行時間：O(V³)
8.2 パラメータ化計算量理論
def vertex_cover_fpt(graph, k):
"""パラメータ化アルゴリズム - O(2^k + |V| + |E|)"""
# k: 解のサイズパラメータ
def solve(graph, k, cover):
if k < 0:
return None # 解なし
if not graph.has_edges():
return cover # 解を発見
# 分岐：任意の辺(u,v)について
u, v = graph.get_any_edge()
# u を選ぶ場合
graph1 = graph.copy()
graph1.remove_vertex(u)
result1 = solve(graph1, k-1, cover | {u})
if result1:
return result1
# v を選ぶ場合
graph2 = graph.copy()
graph2.remove_vertex(v)
result2 = solve(graph2, k-1, cover | {v})
return result2
return solve(graph, k, set())
# 計算量：O(2^k × poly(n))
# k が小さい場合は実用的（Fixed-Parameter Tractable）
8.3 量子アルゴリズム
def grover_search_classical_simulation():
"""Groverのアルゴリズムの古典シミュレーション"""
# 実際の量子計算では O(√n) だが、古典シミュレーションは O(n)
def oracle(x, target):
"""オラクル関数：目的の要素でのみ -1 を返す"""
return -1 if x == target else 1
def diffusion_operator(amplitudes):
"""拡散演算子（平均値反転）"""
mean = sum(amplitudes) / len(amplitudes)
return [2 * mean - amp for amp in amplitudes]
n = 1000 # 探索空間のサイズ
target = 42
# 初期化：均等な重ね合わせ
amplitudes = [1.0 / math.sqrt(n)] * n
# 最適な反復回数：π√n/4
iterations = int(math.pi * math.sqrt(n) / 4)
for _ in range(iterations):
# オラクル適用
for i in range(n):
amplitudes[i] *= oracle(i, target)
# 拡散演算子適用
amplitudes = diffusion_operator(amplitudes)
# 測定（最大振幅の要素を返す）
max_idx = max(range(n), key=lambda i: abs(amplitudes[i]))
return max_idx
# 量子版：O(√n)
# 古典版：O(n)（線形探索が最適）
8.4 機械学習での計算量
import numpy as np
def gradient_descent_complexity_analysis():
"""勾配降下法の計算量分析"""
class LinearRegression:
def __init__(self, learning_rate=0.01):
self.lr = learning_rate
self.weights = None
def fit(self, X, y, max_iterations=1000, tolerance=1e-6):
n_samples, n_features = X.shape
self.weights = np.zeros(n_features)
for iteration in range(max_iterations):
# 予測: O(n × d)
predictions = X @ self.weights
# 損失計算: O(n)
loss = np.mean((predictions - y) ** 2)
# 勾配計算: O(n × d)
gradient = (2/n_samples) * X.T @ (predictions - y)
# 重み更新: O(d)
self.weights -= self.lr * gradient
# 収束判定: O(d)
if np.linalg.norm(gradient) < tolerance:
break
# 1回のイテレーション: O(n × d)
# 総計算量: O(iterations × n × d)
# n: サンプル数, d: 特徴量数
def neural_network_complexity():
"""ニューラルネットワークの計算量"""
# 順伝播: O(Σ(l_i × l_{i+1})) for each layer
# 逆伝播: 順伝播と同じオーダー
# バッチサイズ b を考慮すると: O(b × network_size)
# 例：3層NN (784 → 128 → 64 → 10)
# 順伝播: 784×128 + 128×64 + 64×10 = 109,312 operations
# バッチサイズ32: 32 × 109,312 = 3,497,984 operations
pass
9. 総合演習と実践問題
9.1 基礎レベル
問題1：複雑なループ構造の解析
def complex_loop_analysis(n):
"""この関数の時間計算量を求めよ"""
count = 0
# ループ1
for i in range(n):
for j in range(i, n):
for k in range(j):
count += 1
# ループ2
i = 1
while i < n:
for j in range(n):
count += 1
i *= 2
# ループ3
for i in range(n):
j = n
while j > 1:
count += 1
j //= 2
return count
# 解答：
# ループ1: Σ[i=0 to n-1]Σ[j=i to n-1](j) = O(n³)
# ループ2: log n × n = O(n log n)
# ループ3: n × log n = O(n log n)
# 全体: O(n³)
問題2：再帰関数の解析
def mysterious_recursion(n):
"""この再帰関数の時間計算量を求めよ"""
if n <= 1:
return 1
result = 0
for i in range(n):
result += mysterious_recursion(n // 2)
return result
# 漸化式：T(n) = n × T(n/2) + O(n)
# マスター定理では解けない（第3ケースの条件を満たさない）
# 展開すると：T(n) = O(n^log₂n)
9.2 応用レベル
問題3：動的プログラミング最適化
def longest_increasing_subsequence_optimized(arr):
"""最長増加部分列をO(n log n)で求める"""
if not arr:
return 0
# tails[i] = 長さi+1のLISの末尾要素の最小値
tails = []
for num in arr:
# 二分探索でnum以上の最小要素の位置を見つける
left, right = 0, len(tails)
while left < right:
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid
# 位置leftに挿入または更新
if left == len(tails):
tails.append(num)
else:
tails[left] = num
return len(tails)
# 素朴なDP：O(n²)
# 最適化版：O(n log n)
問題4：高度なデータ構造
class FenwickTree:
"""Binary Indexed Tree（Fenwick Tree）"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, idx, delta):
"""1つの要素を更新 - O(log n)"""
while idx <= self.n:
self.tree[idx] += delta
idx += idx & (-idx) # 最下位ビットを加算
def query(self, idx):
"""前綴和を計算 - O(log n)"""
result = 0
while idx > 0:
result += self.tree[idx]
idx -= idx & (-idx) # 最下位ビットを減算
return result
def range_query(self, left, right):
"""区間和を計算 - O(log n)"""
return self.query(right) - self.query(left - 1)
# 応用：逆転数（inversion count）の計算
def count_inversions_with_fenwick(arr):
"""配列の逆転数をO(n log n)で計算"""
# 座標圧縮
sorted_unique = sorted(set(arr))
coord_map = {v: i+1 for i, v in enumerate(sorted_unique)}
ft = FenwickTree(len(sorted_unique))
inversions = 0
for i, val in enumerate(arr):
compressed_val = coord_map[val]
# val より大きい値の個数 = 現在までの要素数 - val以下の個数
inversions += i - ft.query(compressed_val)
# val を追加
ft.update(compressed_val, 1)
return inversions
9.3 研究レベル
問題5：高度な近似アルゴリズム
def maximum_cut_approximation(graph):
"""最大カット問題の0.878-近似アルゴリズム（SDP緩和 + ランダム丸め）"""
import numpy as np
from scipy.optimize import minimize
n = graph.num_vertices()
# SDP緩和を解く（簡略化された実装）
def sdp_relaxation():
# 変数：x_i ∈ R^n (||x_i|| = 1)
# 最大化：Σ_{(i,j)∈E} w_{ij} * (1 - x_i·x_j) / 2
# 実際のSDP解法は複雑なので、ここでは疑似コード
X = np.random.randn(n, n) # n×n の解行列
return X
def random_rounding(X):
"""Goemans-Williamsonのランダム丸め"""
# ランダムなベクトル r を生成
r = np.random.randn(X.shape[1])
# sign(X @ r) でカットを決定
cut = np.sign(X @ r)
return cut > 0
# アルゴリズム実行
X = sdp_relaxation()
cut = random_rounding(X)
# 期待近似比：0.878...（数学的に証明済み）
return cut
問題6：並列アルゴリズムの実装
import concurrent.futures
import threading
def parallel_merge_sort(arr, num_threads=4):
"""並列マージソート"""
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def sort_sequential(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = sort_sequential(arr[:mid])
right = sort_sequential(arr[mid:])
return merge(left, right)
def sort_parallel(arr, depth=0):
if len(arr) <= 1:
return arr
if depth >= math.log2(num_threads):
# 十分に分割したので逐次処理
return sort_sequential(arr)
mid = len(arr) // 2
with concurrent.futures.ThreadPoolExecutor(max_workers=2) as executor:
future_left = executor.submit(sort_parallel, arr[:mid], depth + 1)
future_right = executor.submit(sort_parallel, arr[mid:], depth + 1)
left = future_left.result()
right = future_right.result()
return merge(left, right)
return sort_parallel(arr)
# 理論的並列計算量：
# Work: W(n) = O(n log n)
# Span: S(n) = O(log² n)
# 並列度: P(n) = O(n log n / log² n) = O(n / log n)
9.4 実装チャレンジ
以下の問題を実装し、計算量を分析せよ：
- 平衡二分探索木（AVL木または赤黒木）の完全実装
- 永続データ構造を使った効率的なUndo/Redo機能
- ローリングハッシュを用いた文字列マッチング
- ネットワークフローの最大流アルゴリズム（Push-Relabel法）
- FFTを用いた高速畳み込み演算
9.5 解答例とポイント
# 例：ローリングハッシュの実装
class RollingHash:
def __init__(self, text, pattern_length):
self.MOD = 10**9 + 7
self.BASE = 31
self.text = text
self.pattern_length = pattern_length
# BASE^(pattern_length-1) を事前計算
self.base_power = pow(self.BASE, pattern_length - 1, self.MOD)
# 最初のウィンドウのハッシュを計算
self.current_hash = 0
for i in range(pattern_length):
self.current_hash = (self.current_hash * self.BASE + ord(text[i])) % self.MOD
def roll(self, old_char, new_char):
"""O(1)でハッシュを更新"""
# 古い文字を除去
self.current_hash = (self.current_hash - ord(old_char) * self.base_power) % self.MOD
# 新しい文字を追加
self.current_hash = (self.current_hash * self.BASE + ord(new_char)) % self.MOD
return self.current_hash
def search_pattern(self, pattern):
"""パターンマッチング - O(n + m)"""
if len(pattern) != self.pattern_length:
raise ValueError("Pattern length mismatch")
# パターンのハッシュを計算
pattern_hash = 0
for char in pattern:
pattern_hash = (pattern_hash * self.BASE + ord(char)) % self.MOD
matches = []
# 最初のウィンドウをチェック
if self.current_hash == pattern_hash:
if self.text[:self.pattern_length] == pattern: # 衝突チェック
matches.append(0)
# ウィンドウをスライド
for i in range(1, len(self.text) - self.pattern_length + 1):
old_char = self.text[i - 1]
new_char = self.text[i + self.pattern_length - 1]
hash_value = self.roll(old_char, new_char)
if hash_value == pattern_hash:
if self.text[i:i + self.pattern_length] == pattern:
matches.append(i)
return matches
# 使用例と計算量分析
def demonstrate_rolling_hash():
text = "abcdefabcdefg"
pattern = "cdef"
rh = RollingHash(text, len(pattern))
matches = rh.search_pattern(pattern)
print(f"Pattern '{pattern}' found at positions: {matches}")
# 計算量：O(n + m)
# n: テキスト長, m: パターン長
# 素朴な文字列マッチング O(nm) から大幅改善
参考文献と発展学習
必読書籍
- Thomas H. Cormen et al. - "Introduction to Algorithms" (CLRS)
- Jon Kleinberg, Éva Tardos - "Algorithm Design"
- Sanjoy Dasgupta et al. - "Algorithms"
- Donald E. Knuth - "The Art of Computer Programming"
オンラインリソース
- Coursera: Algorithms Specialization (Stanford University)
- edX: MITx Introduction to Algorithms
- 競技プログラミング: AtCoder, Codeforces, TopCoder
- 可視化ツール: VisuAlgo, Algorithm Visualizer
研究論文への入門
- ACM Transactions on Algorithms
- SIAM Journal on Computing
- Conference Proceedings: STOC, FOCS, SODA
計算量理論は理論と実践の両面から学ぶことで真の理解が得られます。基礎をしっかりと固めつつ、実際のコードを書いて体感することが重要です。