定数時間 O(1) — 永遠に遅くならない操作
O(1)定数時間計算量を理解します。配列、ハッシュマップ、スタックの例とともに、入力サイズに関係なく定数時間で実行される操作を学びます。
Complexity Classes
詳細な説明
O(1)定数時間とは？
操作がO(1) — 定数時間 — で実行されるとは、必要なステップ数が入力サイズに依存しないことを意味します。データセットが10要素でも1000万要素でも、操作はほぼ同じ時間で完了します。
一般的なO(1)操作
| 操作 | データ構造 | O(1)の理由 |
|---|---|---|
| インデックスによるアクセス | 配列 | メモリオフセットの直接計算 |
| 先頭への挿入/削除 | 連結リスト | ポインタの更新のみ |
| Push / Pop | スタック | トップポインタのみ変更 |
| Enqueue / Dequeue | キュー（双方向） | 先頭/末尾ポインタの更新 |
| キーによる検索 | ハッシュテーブル（平均） | ハッシュ関数 + 1バケットアクセス |
定数時間が重要な理由
O(1)はパフォーマンスのゴールドスタンダードです。重要な操作をO(1)にできれば、スケーリングの懸念を完全に排除できます。
償却O(1)
一部の操作は償却O(1)です。つまり、個々の操作が時々遅くなっても、平均するとO(1)です。動的配列のpush()が典型的な例です。
注意点
- ハッシュテーブルの検索は平均O(1)ですが、多くのキーが同じバケットにハッシュされると**最悪O(n)**になります。
- 「定数時間」は「瞬時」を意味しません — 定数係数が大きい場合もあります。
ユースケース
キャッシュ検索、設定アクセス、スタックベースの解析、パフォーマンスクリティカルなコードのホットパスなど、効率的なデータアクセスパターンの設計に不可欠です。