Big-Oは、データが無限大に近づく際の傾向を表しています。問題は、実際のデータが無限大に近い状態になることはめったにないということです。
Big-Oは何を無視しているのか
この表記では、定数および低次項を意図的に省略している。あるアルゴリズム 100n と、あるアルゴリズム n はどちらもO(n)ですが、前者はどのようなデータサイズにおいても100倍も遅いのです。
典型的な例：小さな配列のソート
挿入ソートはO(n²)、シャッフルソートはO(n log n)である。それにもかかわらず、標準ライブラリはすべて、配列の要素数が数十未満の場合、挿入ソートを採用している。その理由は：
- 順序付き挿入・検索であるため、CPUキャッシュは予測が可能であり、ミス予測がほぼ発生しない
- 追加のメモリ割り当ては不要
- ループ構造は非常に単純で、分岐命令が少ない
n = 20 の場合、小さな定数が成長度を圧倒的に上回る。
記憶は計算よりも高価だ
1回の加算には1ナノ秒もかからない。キャッシュミスによりRAMからデータを読み出すには、約100ナノ秒かかる。つまり、1回のキャッシュミスは100回の演算に相当する。
そのため、連続した配列を走査する方が、連結リストを走査するよりも通常は高速です。どちらもO(n)ですが、配列はメモリ上で連続して配置されており、CPUは次の要素をあらかじめ読み込んでいます。一方、連結リストでは、各ノードが別々の場所に配置されています。
Big-Oの正しい使い方
- これを使って、最初から悪い設計を排除する――100万個の要素に対してO(n²)となることは議論の余地がない
- 同程度の2つの選択肢から選ぶためにこれを使ってはならない — 実際に測定すべきだ
- 実際のデータ規模がどれほど大きいかを常に確認してください。その答えは、たいてい想像しているよりも小さいものです
Thảo luận