償却コスト

Posted by

純粋関数型データ構造を読んでる。

計算量の解析において１回の計算に要するコストだけに注目するのではなく、アルゴリズム中で繰り返しなされる計算の平均について好ましい性能をもつかどうかを解析することをならし計算量（mortized analysis）という。つまり、単純に各ステップの計算量を積み上げるのではなく、コストの高い計算の実行される頻度を考えてアルゴリズムを決定すれば、アルゴリズムの選択肢が十分に広がってシアワセということ。

例えば最初に10の領域を確保しn 個の値をベクトルに格納するときを考える時、n \leq 10であれば計算量はO(1)である。しかし、n > 10の時は、新たに10の領域を追加確保しそれまで格納した n個の値を新しい領域にコピーしなければならない。この時全体のコピー数は

    \begin{eqnarray*} \frac{9}{10}\times n+\sum_{i=1}^{\frac{n}{10}}10i&=&\frac{9n}{10}+\frac{\frac{n}{10}(\frac{n}{10}-1)}{2} \\ &=&\frac{n^2}{200}+\frac{17n}{20} \end{eqnarray*}

となる。これを nで割ると平均で計算量は O(n)となる。ところで、新たに領域を10追加確保するのではなく「最初は1の大きさで、領域が一杯になる毎に領域の大きさを倍にする」方法では、

    \begin{eqnarray*} n - log_{2}n + \sum_{i=1}^{log_{2}n-1}2^{i} = 2n - 1 - log_{2}n \end{eqnarray*}

となり、これをnで割れば平均の計算量はO(1)となる。つまり、アルゴリズムの選択肢が広がるということである。

上記例はhttp://www.ieice-hbkb.org/files/06/06gun_03hen_01.pdfを参照しました。