EI3向けに実施した、情報処理技術者試験のH15年秋の問題での補講 の中の処理速度に関する1問 FN T∝N^3のアルゴリズムがN=100で2秒ならN=1000で4倍速いマシンでは、何秒? /FN を解いてもらうのを、例題として実施。
その後、forループの処理時間、2重ループの処理時間の式を示す。 前記例題と同じような見積もりをしてもらい、次数の低い項を無視する話しをする。 次にオーダ記法を説明し、平方根やlogの混ざった処理時間のオーダを 求める話しをする。
時間が余ったので、来週の再帰方程式のための導入話しとして、 いつもの 「ハノイの塔」の処理回数の導出 を行う。
話しを進める途中で、「どうやって解く?」と聞きながら授業をすすめていると、 例年になく、 Σ i = N*(N-1) やら ロピタルの定理 やら 帰納法 などの答えがタイムリーに返ってくる。 久々に反応が良く気持ちの良い授業であった。