Analysis a dynamic table from i ifi- I is an exact powerof 2 zero size with only insertion otherwise operation The total cost of n TABLE-INSERT operations therefore A sequence of n insert operations o The initial capacity of the table is 1 Analysis the cost of these n insertion Amortized feeling 势函数 nser实际成本 Potential function【 capacity=size】 没有扩张 d(T)=2num[]-capacitylT] 有扩张:n+1,不计算分配空间的成本 nse均摊成本:把未来的扩张成本预付 插入:1 为消费掉一个空间付帐:1【为扩张安排自己 的位置做准备】 新空间付帐:1【为扩张安排同样 If the i th operation does not trigger an a If the i th operation does trigger an expansion, then we have =c1+①1-Φ1 → then we have 1+(2mum,-capacity, )-(2.num capacity F2 capacity i and +(2 num -capacity )-(2(num-1)-capacity -) Y capacity i - =num.=num-1, which implies that 注意: capacity= capacity-,没有变化 w capacity =2 (num-1). Thus, the amortized cost of the operation is6 清华大学 宋斌恒 31 Analysis a dynamic table from Analysis a dynamic table from zero size with only insertion zero size with only insertion operation operation A sequence of n insert operations The initial capacity of the table is 1 Analysis the cost of these n insertion: 清华大学 宋斌恒 32 The total cost of n TABLE-INSERT operations is therefore ⎩ ⎨ ⎧ − = 1 . 1 2, otherwise i if i is an exact power of ci < n + 2n = 3n, [ ] ∑ ∑ = = ≤ + n j j n i c i n lg 1 0 2 清华大学 宋斌恒 33 Amortized feeling Amortized feeling Insert实际成本 没有扩张：1 有扩张：n＋1，不计算分配空间的成本 Insert均摊成本:把未来的扩张成本预付 插入：1 为消费掉一个空间付帐：1【为扩张安排自己 的位置做准备】 为准备一个新空间付帐：1【为扩张安排同样 多的其它数据做准备】 清华大学 宋斌恒 34 势函数 Potential function【 capacity ＝size】 Φ(T) = 2num[T] –capacity[T] 清华大学 宋斌恒 35 注意： capacity i = capacity i-1，没有变化 1 ˆi = i + Φi − Φi− c c 1 (2 capacity ) (2 capacity ) −1 − −1 = + ⋅ − − ⋅ i i i i num num 1 (2 capacity ) (2( 1) capacity ) − − − − −1 = + ⋅ i i i i num num = 3. If the i th operation does not trigger an expansion, then we have: 清华大学 宋斌恒 36 If the i th operation does trigger an expansion, then we have capacity i =2· capacity i-1 and capacity i-1=numi-1=numi -1,which implies that capacity i =2·(numi -1). Thus, the amortized cost of the operation is