前回、単純選択法（O(n^2)）と Arrays.sort()（O(n \log n)）の圧倒的な速さの違いに触れました。
今回は、その「O」という記号が一体何を表しているのか、そして自分の書いたコードをどう評価すればいいのかを徹底解説します。
1. O（オーダー）記法とは何か？
O記法とは、**「データの量 (n) が増えたときに、処理時間がどれくらいの勢いで増えるか」**をざっくりと表した指標です。
プログラムの実行時間は、パソコンの性能によって変わります。しかし、「データが2倍になったら手間が4倍になる」という増え方の法則は、どんなマシンでも変わりません。この不変の法則を評価するのがO記法です。
2. よく見る「オーダー」と代表的アルゴリズム
効率が良い順に、代表的な処理を並べました。
| オーダー | 名前 | イメージ | 代表的なアルゴリズム |
| O(1) | 定数時間 | 1億件でも一瞬 | 配列の指定要素へのアクセス |
| O(\log n) | 対数時間 | 増えてもほぼ遅くならない | 二分探索（Binary Search） |
| O(n) | 線形時間 | データ量に比例して増える | 線形探索、1重ループの全件チェック |
| O(n \log n) | 線形対数時間 | 非常に効率が良い | Arrays.sort()（クイックソート等） |
| O(n^2) | 二乗時間 | 増えると急激に重くなる | 単純選択法、バブルソート |
| O(2^n) | 指数時間 | 爆発的に増える | 愚直なフィボナッチ数列の再帰 |
3. 探索とソートの「実力差」
データが 100万件 になった時の計算回数で比較してみましょう。
探索（データを探す）
線形探索 (O(n))：1,000,000回（全部見る必要がある）
二分探索 (O(\log n))：わずか 20回 程度
ソート（並べ替える）
単純選択法 (O(n^2))：1,000,000,000,000回（1兆回・数日かかる）
クイックソート等 (O(n \log n))：約 20,000,000回（一瞬で終わる）
4. 「最悪」「平均」…どの指標を見るべき？
アルゴリズムは、データの並び順（運）によって速さが変わります。
最悪実行時間 (Worst case)
「どれだけ運が悪くてもこれ以上はかからない」という保証。エンジニアが最も重視する指標です。ここを見積もらないと、特定のデータでシステムが止まるリスクがあります。
平均実行時間 (Average case)
何度も実行した時の平均。実務上の体感速度に近い指標です。
5. 自分のコードの計算量を判定する「3つの基本ルール」
自分の書いたメソッドをどう評価すればいいのか、簡単なルールがあります。
① ループ（for文）の入れ子を数える
1重ループ：O(n)
2重ループ：O(n^2)
処理の「深さ」がそのままオーダーに直結します。
② 「半分にする」処理を探す
範囲を毎回半分に絞り込むロジックがあれば、それは O(\log n) です。これは「非常に効率が良いコード」の証です。
③ 定数（回数が決まっている処理）は無視する
「10回だけ回るループ」などは、データ量 n がいくら増えても手間が変わらないため O(1) 扱い。計算量の計算からは除外してOKです。
6. ツールで計測する：JMH
「理論上の計算量」ではなく「実際の速度」を精密に測りたい場合は、Java標準のベンチマークツール JMH (Java Microbenchmark Harness) を使います。
Javaは実行中にコードを最適化するため、単純なストップウォッチ（currentTimeMillis）では正確に測れません。JMHを使えば、ナノ秒単位で統計的なパフォーマンスを測定できます。
7. まとめ
O記法は「データ増に対する耐性」を表すもの。
ループの入れ子を意識するだけで、自分のコードの限界が見えてくる。
実務では最悪実行時間を意識して、破綻しないコードを選ぶ。
0 件のコメント:
コメントを投稿