同じ問題を解くにも、賢い手順 (アルゴリズム) を選べば 1000 倍速くなる。本記事では「探す」「並べる」という基本タスクを通じて、アルゴリズム的思考の基礎を扱います。
1. 計算量の感覚
| 計算量 | n=100 | n=1 万 | n=1 億 |
|---|---|---|---|
| O(1) | 1 ステップ | 1 ステップ | 1 ステップ |
| O(log n) | 7 | 13 | 27 |
| O(n) | 100 | 1 万 | 1 億 |
| O(n log n) | 664 | 13 万 | 27 億 |
| O(n²) | 1 万 | 1 億 | 1 京 (= 10^16) |
| O(2^n) | (計算不能) | — | — |
2. 探索アルゴリズム
2-1. 線形探索 (O(n))
未ソートのデータから探す
Python
def linear_search(data, target): for i, v in enumerate(data): if v == target: return i return -1
print(linear_search([3, 1, 4, 1, 5, 9, 2, 6], 5)) # 42-2. 二分探索 (O(log n))
ソート済みデータから探す
Python
def binary_search(sorted_data, target): low, high = 0, len(sorted_data) - 1 while low <= high: mid = (low + high) // 2 if sorted_data[mid] == target: return mid elif sorted_data[mid] < target: low = mid + 1 else: high = mid - 1 return -1
# Python 標準ライブラリでも同じことができるimport bisectsorted_data = [1, 1, 2, 3, 4, 5, 6, 9]print(bisect.bisect_left(sorted_data, 5)) # 5 が入る位置3. ソートアルゴリズム
3-1. バブルソート (O(n²)) — 教科書用
シンプルだが遅い
Python
def bubble_sort(data): n = len(data) for i in range(n): for j in range(0, n - i - 1): if data[j] > data[j + 1]: data[j], data[j + 1] = data[j + 1], data[j] return data3-2. クイックソート (平均 O(n log n))
実用最速級、ただし最悪 O(n²)
Python
def quicksort(data): if len(data) <= 1: return data pivot = data[len(data) // 2] left = [x for x in data if x < pivot] middle = [x for x in data if x == pivot] right = [x for x in data if x > pivot] return quicksort(left) + middle + quicksort(right)3-3. Python 標準 sorted (Timsort)
実用上はこれを使う
Python
# Python の sort は Timsort (マージソート + 挿入ソートのハイブリッド)data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]print(sorted(data)) # 標準。最悪 O(n log n) 保証data.sort() # in-place ソート
# キー指定people = [{'name': 'A', 'age': 30}, {'name': 'B', 'age': 25}]print(sorted(people, key=lambda p: p['age']))4. ソートアルゴリズム比較
| アルゴリズム | 平均 | 最悪 | メモリ | 安定性 |
|---|---|---|---|---|
| バブル | O(n²) | O(n²) | O(1) | 安定 |
| 選択 | O(n²) | O(n²) | O(1) | 不安定 |
| 挿入 | O(n²) | O(n²) | O(1) | 安定 |
| マージ | O(n log n) | O(n log n) | O(n) | 安定 |
| クイック | O(n log n) | O(n²) | O(log n) | 不安定 |
| ヒープ | O(n log n) | O(n log n) | O(1) | 不安定 |
| Timsort | O(n log n) | O(n log n) | O(n) | 安定 |
5. 次の話
EP.10 では 暗号と認証 に進みます。HTTPS の中身、共通鍵暗号と公開鍵暗号、ハッシュ関数の使われ方を見ます。
この記事の感想を教えてください
あなたの 1 クリックで、本当にこの記事は更新されます。「もっと詳しく」「続編希望」が一定数集まった記事は、 ふくふくが 実際に内容を拡充したり続編記事を公開 します。 送信したリアクションはお使いのブラウザに記録され、再カウントされません。