今日は、遠隔授業形式で初めての情報構造論を行った。

ペン書きを交えながらの説明はそれなりにうまくいったかな。

今日は、2重forループの処理時間の分析の説明を行ったけど、最後の説明は次回の授業への橋渡しで(To be continued…)的に終わらせたんだけど、積極的な学生さんからチャットで質問があったので、解説しちゃえ。

2重forループの処理時間の見積もり

内容は、以下のようなプログラムが、foo(100)で1msecかかったとして、foo(1000)は何秒かかる？

int foo( int n ) {
   int c = 0 ;
   for( int i = 0 ; i < n ; i++ )
      for( int j = 0 ; j < i ; j++ )
         c++ ;
   return c ;
}

勘がいい人なら、2重forループだし処理時間は に比例するから、が10倍なら処理時間は100倍なので 100msec と速攻で答えるかもしれない。でもここはもう少し複雑な見積もりの基礎を説明するのが目標ということで、もう少し厳密な説明を示す。

授業でも解説したが、このプログラムの処理時間は、以下の式で表せる。

よって、の条件で解けばいい…。

ただ、未知変数がと3つある癖に、与えられた式は１つだけ。本来なら、この方程式は解けない。

こういった処理速度を予測するといったニーズでは、通常Nの値は、ある程度大きな値。しかも、正確な時間を求めるのではなく、大まかな見積もりがしたいだけ。だとすると、 の項目は、 に比べて小さな値のはずなので、最初の方程式も以下の式で考えればいい。

そうなると、なので、となる。

よって、となる。

授業が終わってのアンケート、初めての遠隔授業だったけど、おべんちゃらも入ってるだろうけど「わかりやすかった」との言葉をもらえました。学生さんの感想の中には「先生の操作を近くの画面で見れるので、説明も理解しやすかった。トイレにいても授業に参加できます！」との楽しい💩感想ももらえました。👍