从宏观上看（合计）： ·每个元素最多只能被pop一次 ·Pop和nultipop中的pop的次数总和，最多和push次数一样多 ·长度为n的操作序列，最多有n个元素被(push、pop)操作 尽管multipop:是On)的，理论上空栈上的n 个操作最坏情况下是O(n)的。但是，合计的 操作代价仍然是O(n)的！
从宏观上看(合计)： • 每个元素最多只能被pop一次 • Pop和multipop中的pop的次数总和，最多和push次数一样多 • 长度为n的操作序列，最多有n个元素被(push、pop)操作 尽管multipop是O(n)的，理论上空栈上的n 个操作最坏情况下是O(n2 )的。但是，合计的 操作代价仍然是O(n)的！
N个increase操作的代价 Counter Total 一次位翻转：0(1) value cost 0 00000000 0 1 00000001 00000010 3 00000011 4 INCREMENT(A) 4 0000 100 7 5 000 0 101 8 1i=0 6 0 110 10 2 while i A.length and Ai==1 7 0 0 1 8 0 000 15 3 A[]=0 9 0 01001 16 10 00001 010 18 4 i=i+l 11 0000101 5 if i A.length 12 00001100 13 00001101 23 6 A[]=1 14 00001110 2 1 000011 26 16 00010000 31 在A的基础上累加1：Θ(K) K=A.length 将计数器从0累加到16的实际位翻 转次数（代价）
N个increase操作的代价 在A的基础上累加1： Θ(k) 将计数器从0累加到16的实际位翻 转次数(代价) 一次位翻转：O(1) K=A.length
将计数器从0累加到，最坏情况翻转代价？ 从0累加到n,最坏代价： O(kn)? 什么是最坏情况？ 计数经历从(2i)-1递进到2i时
将计数器从0累加到n，最坏情况翻转代价？ 什么是最坏情况？ 计数经历从(2^i)-1递进到2^i时 O(kn)? 从0累加到n，最坏代价：
实际上，一个更紧致的上界是O(n) ·并不是每次递进1，所有的bit都会翻转的！ ·A[O]每次都翻转 ·A[1]每2次翻转一次 ·A[总共翻转了n/2i次 ·合计一下： L」<n∑克 i=0 三 2n. 从宏观上观察，位翻转最多2n次
实际上，一个更紧致的上界是O(n)! • 并不是每次递进1，所有的bit都会翻转的！ • A[0]每次都翻转 • A[1]每2次翻转一次 • A[i]总共翻转了n/2^i次 • 合计一下： 从宏观上观察，位翻转最多2n次
聚合摊还代价 The worst-case time for a sequence of n INCREMENT operations on an initially zero counter is therefore O(n). The average cost of each operation,and therefore the amortized cost per operation,is O(n)/n=O(1). 什么是 aggregate 方法？
聚合摊还代价 • The worst-case time for a sequence of n INCREMENT operations on an initially zero counter is therefore O(n). • The average cost of each operation, and therefore the amortized cost per operation, is O(n)/n=O(1). 什么是 aggregate 方法？