算法导论笔记：17摊还分析
? ? ? ?在攤還分析中，通過求數(shù)據(jù)結(jié)構(gòu)的一系列的操作的平均時(shí)間，來(lái)評(píng)價(jià)操作的代價(jià)。這樣，即使這些操作中的某個(gè)單一操作的代價(jià)很高，也可以證明平均代價(jià)很低。攤還分析不涉及概率，它可以保證最壞情況下每個(gè)操作的平均性能。
?
?????? 攤還分析有三種常用的技術(shù)：
? ? ???聚合分析，它確定n個(gè)操作的總代價(jià)的上界為T(n)，所以每個(gè)操作的平均代價(jià)為T(n)/n。每個(gè)操作都有相同的攤還代價(jià)。
? ? ???核算法：分析每個(gè)操作的攤還代價(jià)，不同于聚合分析，每種操作的攤還代價(jià)是不同的，核算法將序列中較早的操作的余額作為“信用”儲(chǔ)存起來(lái)，與數(shù)據(jù)結(jié)構(gòu)中的特定對(duì)象相關(guān)聯(lián)，在隨后的操作中，儲(chǔ)存的信用可以用來(lái)進(jìn)行支付。
? ? ???勢(shì)能法，與核算法類似，也是分析每個(gè)操作的代價(jià)，但將勢(shì)能作為一個(gè)整體存儲(chǔ)，而與數(shù)據(jù)結(jié)構(gòu)中的某個(gè)對(duì)象無(wú)關(guān)。
一：聚合分析
?????? 聚合分析是證明n個(gè)操作的最壞情況下的總時(shí)間為T(n)，因而每個(gè)操作的平均代價(jià)（聚合代價(jià)）為T(n)/n。所以，聚合分析中的每個(gè)操作的聚合代價(jià)都是相同的。下面以棧操作和二進(jìn)制計(jì)數(shù)器為例說明：
??????
?????? 1：棧操作
?????? 棧操作有PUSH和POP，兩個(gè)操作的都是O(1)時(shí)間的。現(xiàn)在增加一種新的操作MULITIPOP(S, k)，該操作刪除棧頂?shù)膋個(gè)元素，如果k > S.size，則刪除所有元素。該操作與實(shí)際執(zhí)行的POP次數(shù)呈線性關(guān)系，代碼如下：
MULTIPOP(S, k)
?????? while not STACK-EMPTY(S) and k>0
????????????? POP(S)
????????????? k = k-1
?
因此，MULTIPOP的代價(jià)為min(s, k)，其中s表示S.size。
?
?????? 因?yàn)闂５拇笮∽畲鬄閚，所以MULTIPOP的最壞情況為O(n)，所以，由n個(gè)PUSH,POP,MULTIPOP組成的操作序列的最壞代價(jià)為O( n^2)，因?yàn)樾蛄锌赡馨琌(n)個(gè)操作序列。
?
?????? 上面的分析給出的界并不是緊確界，實(shí)際上，在一個(gè)空棧上執(zhí)行n個(gè)PUSH, POP, MULTIPOP的操作序列，代價(jià)最多為O(n)。這是因?yàn)?#xff0c;當(dāng)一個(gè)對(duì)象壓入棧后，至多將其彈出一次。所以，對(duì)于一個(gè)非空的棧，可以執(zhí)行的POP的次數(shù)（包含MULTIPOP中的POP）最多與PUSH操作次數(shù)一樣，即n次。所以，對(duì)任意的n，任意一個(gè)由n個(gè)PUSH, POP, MULTIPOP組成的操作序列，最多花費(fèi)O(n)。所以，每個(gè)操作的攤還代價(jià)為O(1)。
?
2：二進(jìn)制計(jì)數(shù)器遞增
?????? 用一個(gè)數(shù)組A[0..k-1]表示一個(gè)k位二進(jìn)制數(shù)x，x的最低位存儲(chǔ)在A[0]中，最高位在A[k-1]中，初始情況下x=0。遞增代碼如下：
INCREMENT(A)
?????? i=0
?????? while i < A.length and A[i] == 1
????????????? A[i] = 0
????????????? i = i+1
?????? if i< A.length
????????????? A[i]= 1
?
?????? 每次INCREMENT操作的代價(jià)，與翻轉(zhuǎn)的二進(jìn)制位的數(shù)目呈線性關(guān)系。下圖顯示了將一個(gè)二進(jìn)制數(shù)遞增16次的情況，初始值為0，最終變?yōu)?6：
?
?????? 最壞情況下，INCREMENT執(zhí)行一次需要花費(fèi)Θ(k)時(shí)間，因此，初始值為0的計(jì)數(shù)器執(zhí)行n個(gè)INCREMENT操作的最壞情況花費(fèi)為O(nk)時(shí)間。
?
?????? 所以，對(duì)于一個(gè)初始值為0的計(jì)數(shù)器，執(zhí)行n個(gè)INCREMENT操作序列最壞情況下時(shí)間為O(n)，所以，每個(gè)操作的攤還代價(jià)為O(1)。
?
二：核算法
?????? 核算法，對(duì)不同的操作賦予不同的費(fèi)用，這個(gè)費(fèi)用就是攤還代價(jià)。當(dāng)一個(gè)操作的攤還代價(jià)超過實(shí)際代價(jià)的時(shí)候，將差額存入數(shù)據(jù)結(jié)構(gòu)中的特定對(duì)象，存入的差額稱為信用。對(duì)于后續(xù)操作中，攤還代價(jià)小于實(shí)際代價(jià)的情況，信用可以用來(lái)支付差額。
?????? 因?yàn)橄Ｍㄟ^分析攤還代價(jià)來(lái)說明每個(gè)操作的平均代價(jià)的很小，所以應(yīng)該確保n個(gè)操作序列的攤還代價(jià)是實(shí)際代價(jià)的上界。如果 表示第i個(gè)操作的真實(shí)代價(jià)，而 表示攤還代價(jià)，則對(duì)于任意的n，有： ? 。因?yàn)樾庞镁褪菙傔€代價(jià)和實(shí)際代價(jià)的差值，即 ? ，所以需要保持?jǐn)?shù)據(jù)結(jié)構(gòu)中的總信用永遠(yuǎn)為非負(fù)值。
?
1：棧操作
?????? 棧操作的實(shí)際代價(jià)如下：PUSH?? 1;??? POP?????? 1;??? MULTIPOP??? min(k,s)。為這些操作賦予的攤還代價(jià)為：????? PUSH?? 2;??? POP?????? 0； MULTIPOP??? 0。
?
?????? 下面證明，如果按照攤還代價(jià)進(jìn)行繳費(fèi)，則可以支付任意的n個(gè)棧操作序列。在PUSH操作時(shí)，共繳費(fèi)2美元，其中1美元支付PUSH的實(shí)際代價(jià)，將剩余的1美元存入插入的元素，作為信用。這樣，每個(gè)插入的元素都具有1美元的信用。這1美元的信用，實(shí)際上是用來(lái)支付POP操作的預(yù)付費(fèi)。當(dāng)執(zhí)行一個(gè)POP的時(shí)候，并不繳額外的費(fèi)用，而是使用信用來(lái)支付實(shí)際代價(jià)。MULTIPOP也一樣。所以，對(duì)任意的n個(gè)PUSH, POP, MULTIPOP組成的序列，總攤還代價(jià)為實(shí)際代價(jià)的上界，總攤還代價(jià)為O(n)。
?
2：二進(jìn)制計(jì)數(shù)器遞增
?????? INCREMENT的操作時(shí)間與實(shí)際翻轉(zhuǎn)的位數(shù)成正比，所以可以用翻轉(zhuǎn)的位數(shù)作為操作的實(shí)際代價(jià)。
?????? 在攤還分析中，對(duì)一次置位操作（0->1），繳費(fèi)2美元，用1美元支付置位操作的實(shí)際代價(jià)，另存1美元在該位，作為信用，用來(lái)支付將來(lái)的復(fù)位操作(1->0)。所以，任何時(shí)刻，計(jì)數(shù)器中任何為1的位都存有1美元的信用。對(duì)于復(fù)位操作，無(wú)須繳納任何費(fèi)用。
?????? 所以，每個(gè)INCREMENT操作最多置位一次，因此攤還代價(jià)為2美元。所以，n個(gè)INCREMENT操作，總攤還代價(jià)為O(n)。
?
三：勢(shì)能法
?????? 勢(shì)能法與核算法類似，但是勢(shì)能法并不將預(yù)付代價(jià)表示為數(shù)據(jù)結(jié)構(gòu)中特定對(duì)象的信用，而是表示為“勢(shì)能”。勢(shì)能是與整個(gè)數(shù)據(jù)結(jié)構(gòu)相關(guān)聯(lián)，而不是某個(gè)特定的對(duì)象。將勢(shì)能釋放，就可以支付未來(lái)操作的代價(jià)。
?
?????? 勢(shì)能法如下：對(duì)一個(gè)初始數(shù)據(jù)結(jié)構(gòu) 執(zhí)行n個(gè)操作。對(duì)于i = 1, 2,...,n， 表示第i個(gè)操作的實(shí)際代價(jià)， 表示在數(shù)據(jù)結(jié)構(gòu) 上執(zhí)行第i個(gè)操作得到的數(shù)據(jù)結(jié)構(gòu)。勢(shì)函數(shù) 將每個(gè)數(shù)據(jù)結(jié)構(gòu) 映射到一個(gè)實(shí)數(shù) ，這個(gè)值就是關(guān)聯(lián)到數(shù)據(jù)結(jié)構(gòu) 的勢(shì)。所以，第i個(gè)操作的攤還代價(jià)為。每個(gè)操作的攤還代價(jià)等于其實(shí)際代價(jià)加上此操作引起的勢(shì)能變化。
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/gqtcgq/p/7247227.html
總結(jié)
以上是生活随笔為你收集整理的算法导论笔记：17摊还分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java高效读取大文件
- 下一篇： android转IOS开发学习计划