Stack operation Incrementing a binary counter 啼d(D)= Length(D) m =b the number of ]'s in the counter Push a1=c1+ΦD)-①①1)=1+1=2 after the ith opertion, 啼Popa1=c1+Φ(D)-ΦD)=11=0 w The ith opertaion reset t bits b, sb; 1-t+1 Multihop(k)a1=c1+Φ①D)-D1)=k Φb(D)-dD1) k=0 ≤(t1+1)+(1t 中解释:【课堂提问】 As o(d is nonnegative hence the n sequence of operation cannot exceed 2n of cost hence the amortized cost is o(1 势方法小结 Sample: Dynamic tables 中当因素太多时,做账分摊太难 m Dynamic table is a base data structure for 势方法把帐做到一起:势 store variation objects in a table ≌操作对势有贡献【一般是原始操作,为其后的 动态表上可以加许多操作,我们先考虑 肖除操作付帐】,增加势 下两种: 区操作对势有索取【一般是消除操作,有人已经 iNsert【事实上是 Append】 付帐】,势减少 Deee【事实上是删除最后的数据 区混合操作,则根据不同操作分别累计即可 Insert an element TABLE-INSERT(T,x) I if size[T- 啼插入过程 2 then allocate tabler with I slot sie[←1 alf there are enough space to store the element, just put it after the last element, then allocate new- table with2· size[门 slots ZIf there is not enough space, than apply a insert all items in table[l]into new-table double more space, and then copy the free table[7] original value to the new one and append the table[]+new-table new element sie[们←2·sie[们 11nam[门nm[7+1 55 清华大学 宋斌恒 25 Stack operation Φ(Di )=length(Di ) Push ai =ci + Φ(Di ) – Φ(Di-1)=1+1=2 Pop ai =ci + Φ(Di ) – Φ(Di-1)=1-1=0 Multipop(k) ai =ci + Φ(Di ) – Φ(Di-1)=k￾k=0 解释：【课堂提问】 清华大学 宋斌恒 26 Incrementing a binary counter Incrementing a binary counter Φ= bi the number of 1’s in the counter after the ith opertion, The ith opertaion reset ti bits bi ≤bi-1 –ti +1 ai =ci + Φ(Di ) – Φ(Di-1) ≤(ti +1) + (1-ti ) ≤2 As Φ(Di ) is nonnegative hence the n sequence of operation cannot exceed 2n of cost hence the amortized cost is O(1) 清华大学 宋斌恒 27 势方法小结 当因素太多时，做账分摊太难 势方法把帐做到一起：势 操作对势有贡献【一般是原始操作，为其后的 消除操作付帐】，增加势 操作对势有索取【一般是消除操作，有人已经 付帐】，势减少 混合操作，则根据不同操作分别累计即可 清华大学 宋斌恒 28 Sample: Dynamic tables Sample: Dynamic tables Dynamic table is a base data structure for store variation objects in a table. 动态表上可以加许多操作，我们先考虑一 下两种： Insert【事实上是Append】 Delete【事实上是删除最后的数据】 清华大学 宋斌恒 29 Insert an element Insert an element 插入过程： If there are enough space to store the element, just put it after the last element, If there is not enough space, than apply a double more space, and then copy the original value to the new one and append the new element. 清华大学 宋斌恒 30 TABLE-INSERT( INSERT(T,x) 1 if size[T]=0 2 2 then allocate allocate table[T] with 1 slot ] with 1 slot 3 3 size[T]← 1 4 if num[T]=size[T] 5 5 then allocate allocate new-table with 2 • size[T] slots ] slots 6 insert all items in 6 insert all items in table[T]into new-table 7 7 free table[T] 8 8 table[T]←new-table 9 9 size[T]←2 • size[T] 10 insert 10 insert x into table[T] 11 num[T]←num[T]+1