Amortized timeとは、あるアルゴリズムが、通常起こる時間複雑性のほかにたまにしか起こらない非常に悪い時間複雑性を持つ場合の時間複雑性を表す表現方法です。 例えば、配列を含むデータ構造で、拡張可能なArrayListが良い例です。 Stack Overflow からの他の定義は、多くの操作を行う場合、操作ごとにかかる平均時間です。
ArrayList がその中の配列容量に達すると、古い配列の倍のサイズで新しい配列を作成し、古い配列のすべてのアイテムを新しい配列にコピーします。
配列が容量に達しておらず、まだアイテムを挿入する十分なスペースがある場合
この場合、配列にアイテムを挿入するには、最後のアイテムの後にアイテムを置くだけでよいのです。 6795>
配列が定員に達し、サイズを倍にして再作成する場合
配列が定員に達したため、空きスロットがなくなりました。 そこで、2 倍のサイズでまったく新しいアレイを作成する必要があります。 そして、古い配列のアイテムを新しい配列にコピーする必要がありますが、これには O(n) がかかります。ここで n は古い配列の容量で、最悪の場合です。
この二つの時間の複雑さを表現するのに、ここでは償却時間 (amortized time) が使用されています。 これは何をするかというと、内部配列が容量に達するたびに最悪のケースがたまに起こることを記述させることです。
しかし、それが起こると、コストが “償却” されるほど長い間再び起こることはないでしょう。 (Cracking the Coding Interview 6th edition 43)
では、2つの複雑さをどう表現するかですが、
ArrayListの場合、
挿入は、容量に達したときにO（n）かかり、挿入ごとの償却時間はO（1）です
しかし今回は単純化せず最悪時間の複雑さを正確に表現してみましょう。 内部配列の容量が 1 から始まる場合、容量に達して 2 倍になったときに 1、2、4、8、16… X となります。 新しい配列にコピーするためには，到達した容量に応じて 1, 2, 4, 8, 16… X 個のアイテムが必要です． Xから考えると、X + X/2 + X/4 + X/8… + 1 = 2Xになります。 つまり正確に言うと、
挿入はXの容量に達したときにO(2X)かかり、各挿入の償却時間はO(1).です
。
