TL;DR
関数の増え方の上界を表す数学の記法。計算機科学では、入力が大きくなるにつれてアルゴリズムの実行時間や使うメモリがどう増えるかで、計算量を分類するのに使う。
仕組み
英語版 Wikipedia の「Big O notation」によると、ある正の定数 M があり、十分大きな x で |f(x)| ≤ M·g(x) が成り立つとき、f(x) = O(g(x)) と書く。この等号は値が等しいことではなく、f と g の間の不等式を表している。
大きな入力での増え方だけを見るので、和では最も速く増える項だけを残し、積では定数倍を取り除く。たとえば 6x⁴ − 2x³ + 5 は O(x⁴) である。一方で、6x⁴ は x³ より速く増えるので、O(x³) ではない。
例
よく出てくる計算量と、その例を挙げる。
- O(1)（定数時間）: 固定サイズの表の参照
- O(log n)（対数時間）: ソート済みの配列の二分探索
- O(n)（線形時間）: ソートされていないリストからの探索
- O(n log n): マージソート、ヒープソート
- O(n²)（2 乗時間）: バブルソート、挿入ソート、選択ソート
注意点
O が表すのは上界だけである。下界は Ω、上下の両方から定数倍で抑えられることは Θ で表す。計算機科学では、Θ の方が正確な場面でも O を使うことが多い。たとえば 73n³ + 22n² + 58 は O(n³) であり、Θ(n³) でもあるが、Θ(n³) と書く方が多くを伝えられる。