償却分析 - 正しいアプローチ？

Question

この練習を勉強して偶然見つけました。私は3つの方法すべてでそれを解決するのに問題があります。

一連のn回の操作でデータ構造を維持しているとします。 k番目の 操作の実際の実行時間をf（k）とします。次の各関数fについては、結果として累積された1回の操作の償却原価を決定します。 （実際には、このノートに記載されている方法のうち を試してください）。

（a）f（k）は2^iがkを分けるような最大の整数です。

ソース：https://courses.engr.illinois.edu/cs473/fa2013/notes/14-amortize.pdf

私は操作がちょうどより高価な取得として潜在的な方法はここに助けることができる場所を私は見ていない概要

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 
f(k) 0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 ... 

を取得しようとする小さなテーブルを作りました時間とともに。バンカーの方法も同じ理由でここには適用されないようです。だから私は集計方法が最も適していると思った。

私は、n個の一連の操作のために思い付いたものです、しかし、私は私はそれが正しいアプローチだかどうかを疑問視せた、それを変換するために見えることはできません。

EDIT：

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 
f(k) 0 1 0 2 0 1 0 3 0 1 0 1 0 1 0 4 ... 

Answer 1

ケース誰で迅速な答えは、あなたが「保存することができバンカーのメソッドを使用して、この

をグーグル：それは私が正しい表は次のようになりと思う質問を誤解のように見えます'一定のクレジット数（この場合は2回の操作で効果があります）より高価なもののコストを簡単にカバーできます。

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 
f(k) 0 1 0 2 0 1 0 3 0 1 0 1 0 1 0 4 ... 
cr 2 3 5 5 7 8 10 9 11 12 14 15 17 18 20 18 ...