【徹底解説】オーダーの大小関係

zuka

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

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

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

目次

オーダーの大小関係

計算量$T_{1}(n)$と計算量$T_{2}(n)$に対し,

\begin{align}
\lim_{n\rightarrow \infty}\frac{T_{1}(n)}{T_{2}(n)} &= 0
\end{align}

のとき,$T_{1}(n)$よりも$T_{2}(n)$の方が増加オーダーが大きくなる。

オーダーの大小関係を比較するための定義です。オーダーの大小は,差ではなく商の極限を用いて定義されます。

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

コメント

コメントする

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

目次
目次
閉じる