Online Computation Compet Analysis

Online Computation Compet Analysis

半分くらいまで読んだので簡単な感想を。
基本的にこの本は、アルゴリズムの手続きについて詳しく説明している本ではないという点は注意しておいた方がよいとおもう。手続きそのものは比較的シンプルでかつ抽象的に定義されているのに対して、その最悪計算量コストがどのくらいになるかという点に焦点がしぼられていて、計算量コストの証明が本文の大半を占める。
本文のほとんどが証明に取られていて、次から次へと数学的な証明が続くので、証明を追うことに注意を取られて頭を整理していないと、今何の証明をしているのかが分からなくなること請け合い。
テーマとしては、机の上に置かれた書類をどういう順序で並べておくのが効率がよいか、とか、スキー板をレンタルするべきか買うべきかとか、そんな感じの内容。最初は比較的イメージの付きやすいところから入って、9-11章が抽象度のピークで、それを越えるとまた少し具体的な話に戻るという感じ（今ここ）
先に進むことを重視しているので、証明は完全に追いきれていないところもいくらか。とりあえず概略だけ頭に入れておいて、何か必要になったときに再度読み直して理解すればよいかと思う。しかし、一般的に、この本を入門に独習しようとするのはやや苦しいかも。

• • • -

つい筆が滑って計算量と書いてしまった。計算量じゃなくてコストです。