ループ処理の時間
先週の、単純検索の処理時間が、 、 2分探索のループ回数が、
の説明に続き、 その処理時間は、
であることを示す。
もう少し複雑になった事例ということで、2重ループを含む最大選択法による並べ替えは、 最内ループ回数が となることを示し、 最大選択法の処理時間は、
で示されることを説明する。
オーダ記法
前述の処理時間の式では、処理時間に関する定数が沢山でてくる。 また、Nが大きく変化した時の処理時間のおおよその予測の際には、 Nの次数の低い項は無視する場合が多い。
このためプログラムのアルゴリズムの効率(処理時間）を議論するときは、 Nが巨大になった時の最も値の大きい項の変化式の部分だけで、 大まかな処理時間の予測ができる。この式でアルゴリズムを表現したものを オーダ記法(ビッグオー記法)と呼ぶ。
よって、 単純検索は、、 2分探索は、
、 最大選択は、
で示されることを説明する。
処理時間の予測
2分探索法で、データ(N)が100件の時の処理時間が1msecであった場合、 データが1000件の場合どのくらいの処理時間となると予想されるか？
オーダ記法では、 は、
なので、
より、
(ただしlogの底は10とする)。 よって、
授業の最後に、複数の項のNの次数が微妙で増加速度の判断が困難な場合の オーダーを求める手法として、ロピタルの定理を用いた方法なども説明する。