今年度最終講義

ソフトウェア構成論は試験期間前日だけど補講。アルゴリズムの平均所要時間を求める手法−ならし解析について。集計法は各操作の最大時間の和をとるもの。大抵大きく出すぎるので、それに「直感で」気付いて修正かけないといけない。出納法は、所要時間の少ない操作のときに、時間のかかる操作のための貯金をするものと考えて、貯金額が０を切らないような貯金の仕方を見つければそれが平均所要時間になっているというもの。ポテンシャル法は、・・・ちょっと言葉じゃ説明しにくい。
今回は、アルゴリズムそのものではなくアルゴリズムの解析の仕方。さて、このネタは試験に出るや出ざるや。出ない気がする。おいしい話題だけど、まともな問題にしようがないから。