償却計算量
Amortized complexityというのがまだ理解できてない．代表的な結果である「動的配列のアクセスのコストは拡張のコストを含めてもO(1)であること」なんかの証明がぱっと出てこないのよね．いっぺん時間を取って落ち着いて考えてみたい．
そういやO記法の使い方について「『O(2^n)だから効率が悪い！』という言明は誤ってる」って話がある．O(2^n)であることは，実はO(1)定数時間であることを含むO(2^n)のアルゴリズムの中には実はO(1)であるものも含まれる*1訳で... Knuth先生は「上界」Oの類似品として「下界」Ωや「漸近」Θ*2を使い分けてらっしゃるようだけど，普段はそんなこと考えないよねぇ．つまり何となくΘと取り違えて使ってることが多いと思う．
こないだUMのメモリ管理にハッシュ表を使ってみたので，こんなことを思い出した．
