算法設(shè)計與分析ch6

1、在平攤分析中，執(zhí)行一系列數(shù)據(jù)結(jié)構(gòu)操作所需要時間是通過對執(zhí)行的所有操作求平均而得出的 對一個數(shù)據(jù)結(jié)構(gòu)要執(zhí)行一系列操作：有的代價很高有的代價一般有的代價很低?各個操作的代價？將總的代價平攤到每個操作上平攤代價不涉及概率不同于平均情況分析 聚集方法會計方法勢能方法對數(shù)據(jù)結(jié)構(gòu)共有n個操作最壞情況下：操作1： t1操作2： t2。操作n: tnT(n)=niit1平攤代價：T(n)/n操作序列中的每個操作被賦予相同的代價，不管操作的類型普通棧操作 PUSH(S,x)：將對象壓入棧S POP(S)：彈出并返回S的頂端元素 時間代價: 兩個操作的運行時間都是O(1) 我們可把每個操作的代價視為1 n個PUS

2、H和POP操作系列的總代價是n n個操作的實際運行時間為(n) 新的棧操作新的棧操作 操作MULTIPOP(S,k)： 去掉S的k個頂端對象 或當(dāng)S中包含少于k個對象時彈出整個棧 實現(xiàn)算法 輸入：棧S，k 輸出：返回S頂端k個對象 MULTIPOP(S,k) 1 While not STACK-EMPTY(S) and k0 Do 2 POP(S); 3 kk-1 實際運行時間與實際執(zhí)行的POP操作數(shù)成線性關(guān)系 While循環(huán)執(zhí)行的次數(shù)是從棧中彈出的對象數(shù)min(s,k) 執(zhí)行一次While循環(huán)要調(diào)用一次POP MULTIPOP的總代價即為min(s,k) 初始為空的棧上的初始為空的棧上的n個

3、棧操作序列的分析個棧操作序列的分析 由PUSH、POP和MULTIPOP長為n的棧操作序列 操作1： t1操作2： t2。操作n: tnT(n)=?最壞情況下，每個操作都是:MULTIPOP每個MULTIPOP的代價最壞是？T(n)=n2 上面的分析太粗糙了！我們從元素進出棧的情況來分析所以在一個非空棧上調(diào)用P O P 的 次 數(shù) ( 包 括 在MULTIPOP內(nèi)的調(diào)用)至多等于PUSH的次數(shù)， 即至多為n T(n)=2n 平攤代價=T(n)/n=O(1)一個對象在每次被壓入棧后至多被彈出一次 ！Note: 分析過程沒有使用任何的概率！于是：最壞情況下這樣的一個操作序列的時間復(fù)雜度最多為O(n

4、)1. 問題定義問題定義 實現(xiàn)一個由開始向上計數(shù)的k位二進計數(shù)器。 輸入：k位二進制變量x，初始值為0。 輸出：x+1 mod 2k。 數(shù)據(jù)結(jié)構(gòu)： A0.k-1作為計數(shù)器，存儲x x的最低位在A0中，最高位在Ak-1中 x = kiA ii102 l 2. 計數(shù)器加計數(shù)器加1算法算法l 輸入：A0.k-1，存儲二進制數(shù)xl 輸出：A0.k-1，存儲二進制數(shù)x+1 mod 2kINCREMENT(A) 1 i0 2 while ilengthA and Ai=1 Do 3 Ai0; 4 ii+1; 5 If ilengthA Then Ai1l 3.初始為零的計數(shù)器上初始為零的計數(shù)器上n個個IN

5、CREMENT操作的分析操作的分析 Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 1Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 12 0 0 0 0 0 0 1 0 3Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0

6、0 0 0 01 0 0 0 0 0 0 0 1 12 0 0 0 0 0 0 1 0 33 0 0 0 0 0 0 1 1 4Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 12 0 0 0 0 0 0 1 0 33 0 0 0 0 0 0 1 1 44 0 0 0 0 0 1 0 0 7Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 12 0 0 0 0 0 0 1 0 33 0 0

7、0 0 0 0 1 1 44 0 0 0 0 0 1 0 0 75 0 0 0 0 0 1 0 1 8 6 0 0 0 0 0 1 1 0 10 7 0 0 0 0 0 1 1 1 11每次INCREMENT操作的代價與被改變值的位數(shù)成線性關(guān)系 粗略地講：每次INCREMENT最多改變k位 共nk每次操作發(fā)生一次變化共n次每隔2次發(fā)生一次改變共n/2每隔4次發(fā)生一次改變共n/4每隔8次發(fā)生一次改變共n/8總共發(fā)生的改變?yōu)椋簄/2i (i=0,2,log2n2n一個操作序列中有不同類型的操作不同類型的操作的操作代價各不相同于是我們?yōu)槊糠N操作分配不同的平攤代價平攤代價可能比實際代價大，也可能比實際

8、代價小操作被執(zhí)行時，支付了平攤代價如果平攤代價比實際代價高：平攤代價的一部分用于支付實際代價，多余部分作為存款附加在數(shù)據(jù)結(jié)構(gòu)的具體數(shù)據(jù)對象上如果平攤代價比實際代價低：平攤代價及數(shù)據(jù)對象上的存款用來支付實際代價只要我們能保證：在任何操作序列上，存款的總額非負則所有操作平攤代價的總和就是實際代價總和的上界 平攤代價的總和 ？ 實際代價的總和于是：我們在各種操作上定義平攤代價使得任意操作序列上存款總量是非負的，將操作序列上平攤代價求和即可得到這個操作序列的復(fù)雜度上界1. 各棧操作的實際代價各棧操作的實際代價： PUSH 1, POP 1, MULTIPOP min(k,s)2. 各棧操作的平攤代價各

9、棧操作的平攤代價： PUSH 2, POP 0, MULTIPOP 0,3. 棧操作序列代價分析棧操作序列代價分析 只要我們的操作序列市合理的，則可以保證存款總和非負于是所有操作的平攤代價總和就是操作序列的是及代價總和的上界=？長度為n的操作序列中:PUSH操作的個數(shù)=n于是：平攤代價的總和=2n1. 計數(shù)器加計數(shù)器加1算法算法 輸入：A0.k-1，存儲二進制數(shù)x 輸出：A0.k-1，存儲二進制數(shù)x+1 mod 2kINCREMENT(A)1 i02 while ilengthA and Ai=1 Do3 Ai0;4 ii+1;5 If ilengthA6 Then Ai1初始為零的計數(shù)器上初

10、始為零的計數(shù)器上n個個INCREMENT操操作的分析作的分析 顯然：這個操作序列的代價與0-1或者1-0翻轉(zhuǎn)發(fā)生的次數(shù)成正比定義：0-1翻轉(zhuǎn)的平攤代價為 21-0翻轉(zhuǎn)的平攤代價為0任何操作序列，存款余額是計數(shù)器中1的個數(shù)，非負因此，所有的翻轉(zhuǎn)操作的平攤代價的和是這個操作序列代價的上界對每個INCREMENT操作 ：找到左起的第一個0，將他翻轉(zhuǎn)成1支付平攤代價2將這個0之前的所有1翻轉(zhuǎn)成0支付平攤代價0對這個INCREMENT操作而言，支付了憑攤代價2對于長度為n的INCREMENT操作序列：支付的評攤代價的總和為2n因此，這樣一個操作序列的復(fù)雜度上界為2n任何操作序列，存款余額是計數(shù)器中1的個

11、數(shù)，非負因此，所有的翻轉(zhuǎn)操作的平攤代價的和是這個操作序列代價的上界在會計方法中，如果操作的平攤代價比實際代價大，我們將余額與具體的數(shù)據(jù)對象關(guān)聯(lián)如果我們將這些余額都與整個數(shù)據(jù)結(jié)構(gòu)關(guān)聯(lián)，所有的這樣的余額之和，構(gòu)成數(shù)據(jù)結(jié)構(gòu)的勢能勢能如果操作的平攤代價大于操作的實際代價-勢能增加如果操作的平攤代價小于操作的實際代價，要用數(shù)據(jù)結(jié)構(gòu)的勢能來支付實際代價-勢能減少勢能的定義：勢能的定義：對一個初始數(shù)據(jù)結(jié)構(gòu)對一個初始數(shù)據(jù)結(jié)構(gòu)D0執(zhí)行執(zhí)行n個操作個操作 對操作對操作i: 實際代價Ci, 將數(shù)據(jù)結(jié)構(gòu)Di-1 變?yōu)镈i 勢函數(shù)將每個數(shù)據(jù)結(jié)構(gòu)Di映射為一個實數(shù)(Di) 平攤代價ci定義為：cici + (Di)-(D

12、i-1) ln個操作的總的平攤代價為： niniDDc10)()()1)1()(1niiDiDicniic于是勢函數(shù)滿足(Dn)(D0)，則總的平攤代價就是總的實際代價的一個上界 在實踐中，我們定義(D0)為0，然后再證明對所有i有(Di)0 平攤代價依賴于所選擇的勢函數(shù)。不同的勢函數(shù)可能會產(chǎn)生不同的平攤代價，但它們都是實際代價的上界 (D)=棧D中對象的個數(shù) 初始棧D0為，(D0)=0 因為棧中的對象數(shù)始終非負，第i個超作之后的棧DI滿足(Di)0=(D0)于是： 以表示的n個操作的平攤代價的總和就表示了實際代價的一個上界 作用于包含s個對象的棧上的棧操作的平攤代價 如果第i個操作是個PUS

13、H操作 實際代價：ci=1 勢差：(Di) (Di-1)=(s+1) s=1， 平攤代價：ci =ci+(Di)(Di-1)=1+1=2 如果第i個操作是MULTIPOP(S, k)且彈出了k=min(k,s)個對象 實際代價：ci=k 勢差：為(Di) (Di-1)= k 平攤代價：ci=ci+(Di)(Di-1)=k k=0如果第i個操作是POP 實際代價：ci=1 勢差：(Di) (Di-1)= 1 平攤代價：ci=ci+(Di)(Di-1)=11=0 平攤分析 ：每個棧操作的平攤代價都是O(1) n個操作序列的總平攤代價就是O(n) 因為(Di)(D0)， n個操作的總平攤代價即為總的

14、實際代價的一個上界，即n個操作的最壞情況代價為O(n) (D)=計數(shù)器D中1的個數(shù)計數(shù)器初始狀態(tài)D0中1的個數(shù)為0，(D0)=0因為棧中的對象數(shù)始終非負，第i個超作之后的棧Di滿 足(Di)0=(D0)l于是：n個操作的平攤代價的總和就表示了實際代價的一個上界 第i次INCREMENT操作的平攤代價 設(shè)第i次INCREMENT操作對ti個位進行了置0, 至多將一位置1 該操作的實際代價：ci=ti+1 在第i次操作后計數(shù)器中1的個數(shù)為bi bi-1- t i+1 勢差：(Di)-(Di-1)(bi-1- t i+1)-bi-1=1- t i， 平攤代價：ci = ci+(Di)-(Di-1)(

15、 t i+1)+(1- t i)=2 計數(shù)器初始狀態(tài)為0時的平攤分析 ：每個棧操作的平攤代價都是O(1) n個操作序列的總平攤代價就是O(n) 因為(Di)(D0)， n個操作的總平攤代價即為總的實際代價的一個上界，即n個操作的最壞情況代價為O(n) l開始時不為零的計數(shù)器上n個INCREMENT操作的分析 設(shè)：開始時有b0個1 0b0 在n次INCREMENT操作之后有bn個1)0()(11DnDniicniic將公式重寫為：因為(D0)=b0，(Dn)=bn，n次INCREMENT操作的總的實際代價為： cbbnbbiininnn110022如果我們執(zhí)行了至少n=(k)次INCREMENT

16、操作，則無論計數(shù)器中包含什么樣的初始值，總的實際代價都是O(n) 正是勢能法，給我們這樣的分析帶來了方便!動態(tài)表的概念本節(jié)的目的：研究表的動態(tài)擴張和收縮的問題利用平攤分析證明插入和刪除操作的平攤代價為O(1)，即使當(dāng)它們引起了表的擴張和收縮時具有較大的實際代價研究如何保證一動態(tài)表中未用的空間始終不超過整個空間的一部分動態(tài)表支持的操作 TABLE-INSERT：將某一元素插入表中 TABLE-DELETE：將一個元素從表中刪除 數(shù)據(jù)結(jié)構(gòu):用一個（一組）數(shù)組來實現(xiàn)動態(tài)表非空表T的裝載因子(T)= T存儲的對象數(shù)/表大小 空表的大小為0，裝載因子為1如果動態(tài)表的裝載因子以一個常數(shù)為下界，則表中未使用

17、的空間就始終不會超過整個空間的一個常數(shù)部分 設(shè)T表示一個表:ltableT是一個指向表示表的存儲塊的指針lnumT包含了表中的項數(shù)lsizeT是T的大小l開始時，numT=sizeT=0 l向表中插入一個數(shù)組元素時，分配一個包含比原表更多的槽的新表，再將原表中的各項復(fù)制到新表中去l一種常用的啟發(fā)式技術(shù)是分配一個比原表大一倍的新表，如果只對表執(zhí)行插入操作，則表的裝載因子總是至少為1/2，這樣浪費掉的空間就始終不會超過表總空間的一半算法：TABLEINSERT(T, x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If num

18、T=sizeT Then5 allocate new table with 2sizeT slots;6 insert all items in tableT into new-table;7 free tableT;8 tableTnew-table;9 sizeT2sizeT;10 Insert x into tableT;11 numTnumT+1 復(fù)雜插入操作基本插入操作開銷為常數(shù)開銷由sizeT決定初始為空的表上n次TABLE-INSERT操作的代價分析-粗略分析粗略分析算法：TABLEINSERT(T, x)1 If sizeT=02 Then allocate tableT wi

19、th 1 slot;3 sizeT1;4 If numT=sizeT Then5 allocate new table with 2sizeT slots;6 insert all items in tableT into new-table;7 free tableT;8 tableTnew-table;9 sizeT2sizeT;10 Insert x into tableT;11 numTnumT+1 第i次操作的代價Ci:如果i=1ci=1 如果表有空間ci=1 如果表是滿的ci=i 如果以共有n次操作：最壞情況下 每次進行n次操作 總的代價上界為n2這個界不精確，因為執(zhí)行n次TABL

20、EINSERT操作的過程中并不常常包括擴張表的代價。僅當(dāng)i-1為2地整數(shù)冪時第i次操作才會引起一次表地擴張 初始為空的表上n次TABLE-INSERT操作的代價分析-聚集分析聚集分析算法：TABLEINSERT(T, x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 allocate new table with 2sizeT slots;6 insert all items in tableT into new-table;7 free tableT;8 tableTnew-tabl

21、e;9 sizeT2sizeT;10 Insert x into tableT;11 numTnumT+1 第i次操作的代價Ci:如果i=2mci=i 否則ci=1 n次TABLEINSERT操作的總代價為： 每一操作的平攤代價為3n/n=3 nnnnjjnniic32lg021初始為空的表上n次TABLE-INSERT操作的代價分析-會計法分析會計法分析算法：TABLEINSERT(T, x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 allocate new table with

22、 2sizeT slots;6 insert all items in tableT into new-table;7 free tableT;8 tableTnew-table;9 sizeT2sizeT;10 Insert x into tableT;11 numTnumT+1 每次執(zhí)行TABLEINSERT平攤代價為3 1支付第11步中的基本插入操作的實際代價 1作為自身的存款 1存入表中第一個沒有存款的數(shù)據(jù)上當(dāng)發(fā)生表的擴張時，數(shù)據(jù)的復(fù)制的代價由數(shù)據(jù)上的存款來支付任何時候，存款總和非負初始為空的表上n次TABLE-INSERT操作的平攤代價總和為3n初始為空的表上n次TABLE-INSE

23、RT操作的代價分析-勢能法分析勢能法分析算法：TABLEINSERT(T, x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 allocate new table with 2sizeT slots;6 insert all items in tableT into new-table;7 free tableT;8 tableTnew-table;9 sizeT2sizeT;10 Insert x into tableT;11 numTnumT+1 ?勢怎么定義才能使得表滿發(fā)生擴張時

24、勢能能支付擴張的代價如果勢能函數(shù)滿足：1 剛擴充完，(T)=0 2 表滿時 (T)=size(T)(T)=2*numT-sizeT 勢能函數(shù)滿足要求并且：由于numTsizeT/2，(T)0 n次TABLEINSERT操作的總的平攤代價就是總的實際代價的一個上界 第i次操作的平攤代價： 如果發(fā)生擴張： ci= 3否則 ci= 3初始為空的表上n次TABLE-INSERT操作的平攤代價總和為3n表的擴張表的收縮理想情況下，我們希望表滿足：表具有一定的豐滿度表的操作序列的復(fù)雜度是線性的表的收縮策略根據(jù)表的擴張策略，很自然地想到下滿的收縮策略但表的裝載因子小于1/2時，收縮表委員表的一半n是2的方冪，下面的一個長度為n的操作序列：