オーダー記法 Part3 「計算量の導出」 - shogonir blog

概要 この記事では計算量の導出について紹介します。 オーダー記法シリーズの中でも最も面白く、知るべき内容だと思います。 この記事では特に線形探索と二分探索の計算量を導出します。 この2つの導出を見るだけでも、基本的なテクニックが詰まってますので応用がききます。 また、この記事の内容は動画にもまとまっていますので、 より理解を深めたい方はぜひご覧ください。 線形探索の計算量を導出する方法を説明した動画 youtu.be 二分探索の計算量を導出する方法を説明した動画 youtu.be 計算量の導出 計算量の導出はどのように行うかというと、 定数時間の計算を何回行う必要があるかを数えることで出来ます。 問題の入力で使われる変数を使って定数時間の計算を 何回行うのかを表していきます。 線形探索と二分探索の場合は、入力のリスト長である n を 使うことで計算量を表現できることが分かっています。 それ