メモ的な日記的な

競プロの考察メモとかを残していこうかなー

Big Oってなに?

 主に競技プログラミングや大学の授業で目にする O (Big O)と言う記号ですが、これの定義が曖昧な場合が多いなと思うのでまとめます。すでに多くのwebサイトや書籍で記載されているので新規性はありません。残念。O 記法は僕がはてなブログに慣れるための犠牲になりました。

時間計算量と空間計算量

 プログラミングにおける計算量には主に2種類、時間計算量と空間計算量があります。ざっくばらんに説明すると、時間計算量はその処理に必要なループ・再帰回数、空間計算量はメモリ使用量にあたります。AtCoderにおいては多くの場合は時間計算量だけを気にしていればいいですが、ゲーム開発や組み込み開発だと結構メモリ不足に悩まされるそうなので、空間計算量も意識する必要があるとかないとか。

 O 記法はこの時間計算量や空間計算量を表現する際にしばしば用いられます。

O 記法の定義とかとか

 計算量はしばしば O(N) みたいな感じに表現されますが、O って何を表しているのか知っていますか?僕は1年くらい前まで雰囲気で読み取っていましたが、確か組合せ最適化の本*1を読んだ際に初めてその定義を理解しました。

 たまーに雑な定義として、以下のような表現が見受けられます。

  •  x \to \infty の時、 f(x) \leq g(x) なら f(x) = O(g(x))

これ、f, g が共に上に有界でない単調増加関数なら両方とも無限大に飛んでいっちゃうので、比較できませんよね。なので曖昧どころか式自体間違ったものです(ニュアンスはわかるけれど)。そこで、もうちょっとしっかりと定義しておきたいなと思います。

 いきなりですが、 f(x) = O(g(x) の定義を以下のように与えます。

  •  \exists\, \alpha, C \in \mathbb{R} \, \mathrm{s.t.}\,  \forall\, x \gt \alpha,\,  |f(x)| \leq C|g(x)|

つまり、関数の引数が \alpha 以上の時に必ず一方の定数倍がもう一方以上の値をとる場合、 O 記法で上のように表せるわけです。ここで、[tex : C] は必要なの?って思った人は以下の関数を考えてみてください。

  •  f(x)=2x

この関数は実際に O(x)と表せますが、 C による定数倍がなければ永遠に |f(\alpha)| \geq |g(\alpha)| なため、そう表せなくなります。だから  C が、必要だったわけです。

 ところで、鋭い人は上の定義をみて、上から押さえることができればなんでもいいの?って思うかもしれません。これはその通りで、別に  f(x) = x f(x) = O(x^2) と表現しても問題ありません。実際、ある程度計算量が少ないことさえわかれば十分なこともあるので、雑に評価してそれなりの結果ならOKみたいなことも競プロ中にはやりがちです。

 より厳密な表現を使いたい人は、 \Theta 記法を使いましょう。 f(x) = \Theta(g(x)) は、以下のように定義されます。

  •  f(x) = O(g(x)) \land g(x) = O(f(x))

 非常にシンプルですね。 f(x) = O(g(x)) \Leftrightarrow g(x) = O(x) は一般に成立しませんが、 f(x) = \Theta(g(x)) \Leftrightarrow g(x)=\Theta(f(x)) は常に成立します。

 定義よりわかることですが、 f(x) = f_1(x)+f_2(x)+\cdots +f_n(x) と分解される時、もっとも影響の強い項のみを使って  f(x) = O(f_a(x))と表すことができます。例えば、 f(x) = 3x^2 + 10x の場合は  f(x) = O(x^2) \neq O(x) と表せます。

 いくつかまとめると、項の影響の強さは以下のような順番に並べることができます。

  •  1 \lt \log x \lt x \lt x \log x \lt x^2 \lt x^m (m \gt 2)\ll 2^x \lt x! \lt x^x

指数関数以降はそれ以前とは比べ物にならない速度で爆発的に増加するので、基本的にプログラムを書く際には避けるべきです。

おわりに

 以上、 O 記法のメモでした。ところで、下から押さえる関数の表現については \Omega 記法なんかを使うそうですが、存在と定義は知っているものの利用例を見たことがないのでここでは紹介しませんでした。興味があれば是非調べてみてください。