Stack operation Incrementing a binary counter 3d①)= length①D) a b= b the number of 1's in the counter → Push a1=c1+Φ①D)-(D1)=1+1=2 after the ith opertion Popa1=c1+Φ(D)-dD1)=11=0 "The in opertaion reset t bits b, sb;1-t+1 → Multihop(k)a1=c1+d①D)-D1)=k a1=c1+(D)-①D21) k=0 ≤(t1+1)+(1t) ◆解释:【课堂提问】 is nonnegative hence the n sequence operation cannot exceed 2n of cost hence amortized cost is O 势方法小结 Sample: Dynamic tables →当因素太多时,做账分摊太难 -Dynamic table is a base data structure for →势方法把帐做到一起:势 store variation objects in a table 操作对势有贡献【一般是原始操作,为其后的 动态表上可以加许多操作,我们先考虑 操作对势有索取【一般是消除操作,有人已经 烈 lInsert【事实上是 Append】 付帐】,势减少 Delete【事实上是删除最后的数据 混合操作,则根据不同操作分别累计即可 Insert an element TABLE-INSERT(T,x) I if size[T0 插入过程 alf there are enough space to store the element, just put it after the last element, hen allocate new-table with 2. size[l] slots aIf there is not enough space, than apply a insert all items in table[f]into new-table double more space, and then copy the free table[门 original value to the new one and append the table[T]+new-table new element 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