今回は、情報処理センターの機種更新に伴うパスワード再発行やら、 授業アンケートの作業に前半の時間をとられ、そのまま演習室にて授業。

2分探索法の処理時間分析

最初に、先週説明の単純サーチ と、２重ループの最大選択法 との比較をしながら、 以前のBLOG資料を使って、 2分探索法の処理時間が であることを説明する。

オーダ記法

次に、定番の説明であるけれど、 「単純サーチで、100件で1msecかかった。 データ10000件なら何秒かかる？」 同様に、「最大選択法のプログラムで、100件で10msecかかったら、10000件なら何秒？」 という質問から、オーダ記法の導入を説明する。

最後に、 , , といった、Nが大きな値になった時に、式で大きな値となる主要な部分を抜き出したもの がオーダといった説明を行う。

次回の授業での予習ネタとして、以下の式のオーダについて考えておくように…