【徹底解説】オーダーの性質

zuka

こんにちは。
zuka(@beginaid)です。

本記事は数学の徹底解説シリーズに含まれます。記事一覧はこちらの目次ページからご覧ください。

初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

目次

オーダーの性質

関数$f(x)$と$g(x)$には,以下の関数の漸近的な増加の勢いに関する大小関係があるとする。

\begin{align}
f(x) \prec g(x) \label{大小関係}
\end{align}

このとき,以下が成り立つ。

\begin{align}
O(f(x)+g(x)) &= O(g(x)) \label{主題1}
\end{align}

定数$c$に対して,以下が成り立つ。

\begin{align}
O(cf(x)) &= O(f(x)) \label{主題2}
\end{align}

$f(x)$が最高次数を$n$とする多項式関数の場合,以下が成り立つ。

\begin{align}
O(f(x)) &= O(x^{n}) \label{主題3}
\end{align}

オーダーの性質を利用することで,ビッグオーの中身を綺麗に整理することができます。

証明

まずは式($\ref{主題1}$)から証明します。オーダーの定義と式($\ref{大小関係}$)より,オーダーが$cf(x)$となる関数$T(x)$は,ある$c_{0}>0$に対して以下を満たします。

\begin{align}
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$に対して以下を満たします。

\begin{align}
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$に対し,以下が成り立ちます。

\begin{align}
\lim_{n\rightarrow \infty}\frac{x^{m}}{x^{n}} &= \lim_{n\rightarrow \infty}\frac{1}{x^{n-m}} \\[0.7em]
&= 0
\end{align}

このとき,オーダーの大小関係の定義より,以下が成り立ちます。

\begin{align}
x^{m} \prec x^{n}
\end{align}

したがって,式($\ref{主題1}$)と式($\ref{主題2}$)を逐次適用していくと,以下が得られます。

\begin{align}
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}$)が示されました。

シェアはこちらからお願いします!
URLをコピーする
URLをコピーしました!

コメント

コメントする

※スパム対策のためコメントは日本語で入力してください。

目次
目次
閉じる