[解決済み] 償却期間一定

質問

アルゴリズムの時間計算量について話すとき、quot;Constant Amortized Time"は何を意味しますか？

どのように解決するのですか？

時間償却をわかりやすく解説

ある操作を100万回行ったとして、その操作のワーストケースやベストケースはあまり気にならない。気になるのは、その操作を100万回繰り返したときに、トータルでどれだけの時間がかかるかということだ。

つまり、「たまに」動作が非常に遅くても、「たまに」動作が遅いことが希薄になる程度であれば問題ないわけです。基本的に償却時間とは、多くの操作を行った場合に、1回の操作にかかる平均時間を意味します"。償却時間は一定である必要はなく、線形や対数の償却時間などでもかまいません。

mats の例で、動的な配列に繰り返し新しい項目を追加していく場合を考えてみましょう。通常、アイテムを追加するのには一定の時間がかかります（つまり。 O(1) ). しかし、配列が一杯になるたびに、2 倍の領域を確保し、データを新しい領域にコピーし、古い領域を解放します。割り当てと解放が一定時間で行われると仮定すると、この拡大処理には O(n) ここで、nは配列の現在のサイズです。

つまり、拡大するたびに、前回の拡大時の約2倍の時間がかかるわけです。しかし、その前に2倍の時間を待っていることになります。このように、拡大するたびにかかるコストは、挿入するたびにquot;spread out"することができる。つまり、長期的に見れば、1回の拡大のために必要な時間は m の項目は O(m) となり、償却時間（1回の挿入にかかる時間）は O(1) .