Big O Notation

目的

アルゴリズムの効率の漸近的な増加率を抽象化し、アルゴリズムの比較と選択に役立てる。

メカニズム

f(n)=O(g(n)) は、定数 C と n0 が存在して、n>n0 のすべての n で |f(n)|≤C|g(n)| が成り立つことを意味する。代表的なオーダーは O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!) である。最悪場合の上界に注目する。

ユースケース

• アルゴリズムの計算量解析
• データ構造の選択
• パフォーマンス最適化の判断
• インタビューと教育

例

• 入力

  Binary search

  Output

  O(log n)

  Halves each time

よくあるエラー

Ignoring constant factors misjudges real-world performance

Big O is asymptotic; benchmark for real behavior