実行時間オーダー入門教科書

# 実行時間オーダー入門教科書

## 目次
1. [実行時間オーダーとは](#1-実行時間オーダーとは)
2. [Big O記法の基礎](#2-big-o記法の基礎)
3. [主な時間計算量のパターン](#3-主な時間計算量のパターン)
4. [コード例で学ぶ時間計算量](#4-コード例で学ぶ時間計算量)
5. [時間計算量の求め方](#5-時間計算量の求め方)
6. [実践的な最適化のヒント](#6-実践的な最適化のヒント)
7. [まとめと演習問題](#7-まとめと演習問題)

---

## 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) - 定数時間の例

```python
def get_first_element(arr):
    return arr[0]  # 常に1回のアクセス

# 配列のサイズに関係なく実行時間は一定
```

### 4.2 O(n) - 線形時間の例

```python
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²) - 二次時間の例

```python
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) - 対数時間の例

```python
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 基本的な手順

1. **ループの回数を数える**
2. **ネストしたループは掛け算**
3. **条件分岐は最悪ケースを考慮**
4. **定数倍や低次項は無視**

### 5.2 実践例

```python
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 再帰の場合

```python
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 よくある最適化パターン

#### ハッシュテーブルの活用
```python
# 悪い例：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
```

#### ソート済みデータの活用
```python
# 線形探索：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空間**：実行時間を短縮するために追加のメモリを使用する場合がある

```python
# メモ化によるフィボナッチ：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：時間計算量を求めよ
```python
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：より効率的な実装を考えよ
```python
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)に改善
```python
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)

---

### 参考資料
- アルゴリズムとデータ構造の教科書
- オンラインジャッジサイトでの実践
- 各プログラミング言語の標準ライブラリのドキュメント