ホーム » スタッフ » 斉藤徹 » 繰返し処理の処理速度の見積もりと、オーダ記法

2004年4月
 123
45678910
11121314151617
18192021222324
252627282930  

最新の投稿(電子情報)

アーカイブ

カテゴリー

繰返し処理の処理速度の見積もりと、オーダ記法

EI3向けに実施した、情報処理技術者試験のH15年秋の問題での補講 の中の処理速度に関する1問 FN T∝N^3のアルゴリズムがN=100で2秒ならN=1000で4倍速いマシンでは、何秒? /FN を解いてもらうのを、例題として実施。

その後、forループの処理時間、2重ループの処理時間の式を示す。 前記例題と同じような見積もりをしてもらい、次数の低い項を無視する話しをする。 次にオーダ記法を説明し、平方根やlogの混ざった処理時間のオーダを 求める話しをする。

時間が余ったので、来週の再帰方程式のための導入話しとして、 いつもの 「ハノイの塔」の処理回数の導出 を行う。

話しを進める途中で、「どうやって解く?」と聞きながら授業をすすめていると、 例年になく、 Σ i = N*(N-1) やら ロピタルの定理 やら 帰納法 などの答えがタイムリーに返ってくる。 久々に反応が良く気持ちの良い授業であった。