実行時間オーダー入門教科書
目次
1. 実行時間オーダーとは
1.1 定義
**実行時間オーダー（時間計算量）**とは、アルゴリズムの実行時間が入力データのサイズに対してどのように増加するかを表す指標です。
1.2 なぜ重要なのか
- 効率的なプログラム設計：大量のデータを扱う際の性能を予測できる
- アルゴリズム選択：問題に最適なアルゴリズムを選択できる
- スケーラビリティ：システムの拡張性を評価できる
1.3 実例での理解
例：1000件のデータから特定の値を探す場合
- 線形探索：最悪1000回の比較が必要
- 二分探索：最悪10回程度の比較で済む
データが100万件になると：
- 線形探索：最悪100万回
- 二分探索：最悪20回程度
この差が時間計算量の違いです。
2. Big O記法の基礎
2.1 Big O記法とは
アルゴリズムの実行時間の上限を表す数学的記法です。入力サイズnに対する実行時間の増加率を表現します。
2.2 記号の読み方
- O(1)：「オー・ワン」または「オーダー・ワン」
- O(n)：「オー・エヌ」または「オーダー・エヌ」
- O(n²)：「オー・エヌ・スクエア」
2.3 重要なポイント
- 最悪ケースを基準とする
- 定数倍は無視する（O(2n) = O(n)）
- 最も影響の大きい項のみを考慮する（O(n² + n) = O(n²)）
3. 主な時間計算量のパターン
3.1 効率性の順序（良い順）
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
3.2 各パターンの特徴
O(1) - 定数時間
- 特徴：入力サイズに関係なく一定の実行時間
- 例：配列の特定インデックスへのアクセス、ハッシュテーブルでの検索
O(log n) - 対数時間
- 特徴：入力サイズが倍になっても実行時間は少しずつしか増えない
- 例：二分探索、平衡二分木での検索
O(n) - 線形時間
- 特徴：入力サイズに比例して実行時間が増加
- 例：配列の全要素を一度ずつ処理
O(n log n) - 線形対数時間
- 特徴：効率的なソートアルゴリズムの典型的な時間計算量
- 例：マージソート、クイックソート（平均）
O(n²) - 二次時間
- 特徴：入力サイズが倍になると実行時間は4倍になる
- 例：二重ループ、バブルソート
O(2ⁿ) - 指数時間
- 特徴：入力サイズが1増えると実行時間は2倍になる
- 例：総当たり探索、一部の再帰アルゴリズム
4. コード例で学ぶ時間計算量
4.1 O(1) - 定数時間の例
def get_first_element(arr):
return arr[0] # 常に1回のアクセス
# 配列のサイズに関係なく実行時間は一定
4.2 O(n) - 線形時間の例
def find_max(arr):
max_val = arr[0]
for i in range(1, len(arr)): # n-1回のループ
if arr[i] > max_val:
max_val = arr[i]
return max_val
# 配列のサイズnに比例して実行時間が増加
4.3 O(n²) - 二次時間の例
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 外側ループ：n回
for j in range(n-1-i): # 内側ループ：最大n回
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 合計：約n×n = n²回の比較
4.4 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
# 毎回探索範囲が半分になる：log₂(n)回のループ
5. 時間計算量の求め方
5.1 基本的な手順
- ループの回数を数える
- ネストしたループは掛け算
- 条件分岐は最悪ケースを考慮
- 定数倍や低次項は無視
5.2 実践例
def example_function(arr):
# ステップ1: O(n)
for i in range(len(arr)):
print(arr[i])
# ステップ2: O(n²)
for i in range(len(arr)):
for j in range(len(arr)):
print(arr[i] + arr[j])
# ステップ3: O(1)
print("Done")
# 全体の時間計算量: O(n) + O(n²) + O(1) = O(n²)
5.3 再帰の場合
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
# T(n) = T(n-1) + T(n-2) + O(1)
# これは O(2ⁿ) になる
6. 実践的な最適化のヒント
6.1 よくある最適化パターン
ハッシュテーブルの活用
# 悪い例：O(n²)
def has_duplicate_bad(arr):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
return True
return False
# 良い例：O(n)
def has_duplicate_good(arr):
seen = set()
for num in arr:
if num in seen:
return True
seen.add(num)
return False
ソート済みデータの活用
# 線形探索：O(n)
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
# 二分探索：O(log n) ※ソート済み配列が前提
def binary_search(arr, target):
# 前述のコード参照
pass
6.2 トレードオフの考慮
時間vs空間：実行時間を短縮するために追加のメモリを使用する場合がある
# メモ化によるフィボナッチ：O(2ⁿ) → O(n)
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
7. まとめと演習問題
7.1 重要なポイント
- Big O記法は最悪ケースの実行時間の上限を表す
- ループの深さが時間計算量に大きく影響する
- 適切なデータ構造とアルゴリズムの選択が性能を大きく左右する
- 実際の性能は定数倍やハードウェアにも依存する
7.2 演習問題
問題1：時間計算量を求めよ
def mystery_function(arr):
result = 0
for i in range(len(arr)):
for j in range(i, len(arr)):
result += arr[i] * arr[j]
return result
問題2：より効率的な実装を考えよ
def find_pair_sum(arr, target):
"""配列内で合計がtargetになる2つの要素を見つける"""
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] + arr[j] == target:
return (i, j)
return None
問題3：以下のアルゴリズムの時間計算量は？
- クイックソート（最悪ケース）
- ヒープソート
- ハッシュテーブルでの挿入・検索・削除
7.3 解答例
問題1の解答：O(n²)
- 外側ループ：n回
- 内側ループ：平均 n/2回
- 合計：n × (n/2) = O(n²)
問題2の解答：ハッシュテーブルを使用してO(n)に改善
def find_pair_sum_optimized(arr, target):
seen = {}
for i, num in enumerate(arr):
complement = target - num
if complement in seen:
return (seen[complement], i)
seen[num] = i
return None
問題3の解答：
- クイックソート（最悪）：O(n²)
- ヒープソート：O(n log n)
- ハッシュテーブル：平均O(1)、最悪O(n)
参考資料
- アルゴリズムとデータ構造の教科書
- オンラインジャッジサイトでの実践
- 各プログラミング言語の標準ライブラリのドキュメント