本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
オーダーの性質
関数$f(x)$と$g(x)$には，以下の関数の漸近的な増加の勢いに関する大小関係があるとする。
f(x) \prec g(x) \label{大小関係}
\end{align}
このとき，以下が成り立つ。
O(f(x)+g(x)) &= O(g(x)) \label{主題1}
\end{align}
定数$c$に対して，以下が成り立つ。
O(cf(x)) &= O(f(x)) \label{主題2}
\end{align}
$f(x)$が最高次数を$n$とする多項式関数の場合，以下が成り立つ。
O(f(x)) &= O(x^{n}) \label{主題3}
\end{align}
オーダーの性質を利用することで，ビッグオーの中身を綺麗に整理することができます。
証明
まずは式($\ref{主題1}$)から証明します。オーダーの定義と式($\ref{大小関係}$)より，オーダーが$cf(x)$となる関数$T(x)$は，ある$c_{0}>0$に対して以下を満たします。
T(x) &\leq c_{0}(f(x)+g(x)) \\[0.7em]
&\leq 2c_{0}g(x) \\[0.7em]
&= c_{1}g(x)
\end{align}
ただし，$c_{1}=2c_{0}$と置きました。したがって，オーダーの定義より，オーダー$f(x)+g(x)$である関数は必ずオーダー$g(x)$であることが示されました。すなわち，式($\ref{主題1}$)が示されました。続いて，式($\ref{主題2}$)を示します。オーダーの定義より，オーダーが$cf(x)$となる関数$T(x)$は，ある$c_{0}>0$に対して以下を満たします。
T(x) &\leq c_{0}cf(x) \\[0.7em]
&= c_{1}f(x)
\end{align}
ただし，$c_{1}=cc_{0}$と置きました。これにより，式($\ref{主題2}$)が示されました。最後に，式($\ref{主題3}$)を示します。一般に，ある$0<m<n$に対し，以下が成り立ちます。
\lim_{n\rightarrow \infty}\frac{x^{m}}{x^{n}} &= \lim_{n\rightarrow \infty}\frac{1}{x^{n-m}} \\[0.7em]
&= 0
\end{align}
このとき，オーダーの大小関係の定義より，以下が成り立ちます。
x^{m} \prec x^{n}
\end{align}
したがって，式($\ref{主題1}$)と式($\ref{主題2}$)を逐次適用していくと，以下が得られます。
O(x^{n}+x^{n-1}) &= O(x^{n}) \\[0.7em]
O((x^{n}+x^{n-1})+x^{n-2}) &= O(x^{n}+x^{n-1}) \\[0.7em]
&= O(x^{n}) \\[0.7em]
&\vdots \\[0.7em]
O(f(x)) &= O(x^{n})
\end{align}
ただし，$C$は定数を表します。これにより，式($\ref{主題3}$)が示されました。
コメント