Phân tích thiết kế giải thuật 4回目 - これがベトナム大学院の実態だ！

2019年9月17日、Phân tích thiết kế giải thuậtの4回目授業が実施された。
前回と違い出発前に大便をすることがなく、裏門到着が17:53であった。
時間に余裕があったので校門付近の歩道を不法占拠している豚肉屋で食事をすることにした。
このため結局は5分ぐらいの遅刻となった。
この日は肛門で時間は取られなかったが校門で時間を取られたわけだ。

入室すると、第1章の問4をやる時間のようだった。

j:= 1;
while j <= n do
begin
	call A;
	j := j*b
end

幸いここは事前に予習しておいた内容だ。
問題の量が多すぎるのでこの科目の問題用に特別にノートを1冊用意しておいたのだ。
答えを書いたページを先生に見せると、板書してよいというジェスチャーが返ってきた。
すかさず黒板前に躍り出て答えを書く。
答えは $log_{b}{n}$ 回だ。
しかし、正解はこれに1回が加算されるようで、 $log_{b}{n}+1$ 回であった。
とはいえ計算量は1が無視できるので $O(log_{b}{n})$ となる。
ということで、ぴったりの正解ではなかったが、当たらずとも遠からずだったわけだ。
これが、計算量 $n^{2}$ とかだったら箸にも棒にも引っかからないが、最終的な答えには1含まれないことと、考え方の大筋はあっていたので板書が認められたということだろう。
逆に、ぴったり正解してしまっては先生の解説する出番がなくなってしまう。
そういった意味では100%の正解ではなく、95%ぐらいまでは自力で解けたけど、最後の後1歩が詰められなかったというのは先生にとってもいい講義の場であり、さらにほかの学生にとってもいい勉強の場になったと思われる。
改めて、この日は15分以上の遅刻をしなくてよかったと思うとともに、逆に食べるのを我慢して時間通りに入っても退屈な時間を過ごしたと思うので、5分遅れで入室というのは絶妙なタイミングであった。

なお、この日は2章を終え、3章の8ページまで進んだ。