原书出处
Introduction to Algorithms, Fourth Edition
16 第16章 摊还分析
tion pops k plates, then the actual cost is paid by the k dollars stored on the k plates.
Because each plate on the stack has $1 of credit on it, and the stack always has a nonnegative number of plates, the amount of credit is always nonnegative. Thus, for any sequence of n PUSH, POP, and MULTIPOP operations, the total amortized cost is an upper bound on the total actual cost.
Since the total amortized cost is O(n), so is the total actual cost. Incrementing a binar
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter016.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea