オーダー記法

オーダー記法とは、計算を早くするための記法で、計算量の大まかな把握に役立つ。

オーダー記法は以下の特徴がある。

1. 係数は無視
2. 最も計算量の大きい項を残す。

例えば

n^2 + 2n + 1をオーダー記法で表現すると

O(n^2)となる。

また、129nlognをオーダー記法で表現すると129という係数が無視されるので

nlognとなる。

ここで、仮に129n+3lognといったように、+で区切られている時はどちらの項の方が計算量が大きいかを考慮する必要があるが、今回は項が存在しないので「係数を無視する」というオーダー記法の特徴飲みに従うことになる。