本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
オーダーの大小関係
計算量$T_{1}(n)$と計算量$T_{2}(n)$に対し，
\begin{align}
\lim_{n\rightarrow \infty}\frac{T_{1}(n)}{T_{2}(n)} &= 0
\end{align}
\lim_{n\rightarrow \infty}\frac{T_{1}(n)}{T_{2}(n)} &= 0
\end{align}
のとき，$T_{1}(n)$よりも$T_{2}(n)$の方が増加オーダーが大きくなる。
オーダーの大小関係を比較するための定義です。オーダーの大小は，差ではなく商の極限を用いて定義されます。
コメント