功能數(shù)據(jù)結(jié)構(gòu)課件

功能數(shù)據(jù)結(jié)構(gòu)精品文檔幾種常見的操作插入（insert）在數(shù)據(jù)結(jié)構(gòu)中增加一個(gè)數(shù)據(jù)。刪除（delete）在數(shù)據(jù)結(jié)構(gòu)中刪除一個(gè)數(shù)據(jù)。查找（search）在數(shù)據(jù)結(jié)構(gòu)中查找指定的數(shù)據(jù)。大部分?jǐn)?shù)據(jù)結(jié)構(gòu)都需要檢索。靜態(tài)數(shù)據(jù)結(jié)構(gòu)不需要插入和刪除的數(shù)據(jù)結(jié)構(gòu)稱為靜態(tài)數(shù)據(jù)結(jié)構(gòu)。往往犧牲一些預(yù)處理時(shí)間和附加空間來換取更好的性能而不必?fù)?dān)心維護(hù)的復(fù)雜度。半靜態(tài)數(shù)據(jù)結(jié)構(gòu)、動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)對象空間分解關(guān)鍵碼空間分解精品文檔數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的常見問題時(shí)間效率和空間開銷的關(guān)系矛盾。用時(shí)間去換空間或用空間換時(shí)間。需要做時(shí)空平衡統(tǒng)一。精簡數(shù)據(jù)表示有可能在縮減空間的同時(shí)設(shè)計(jì)出更快速的操作不同操作的關(guān)系例子：維護(hù)一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可修改，可查詢里面是否有需要的元素有序數(shù)組。插入O(n)，查找O(logn)鏈表。插入O(1)，查找O(n)如何讓兩者的時(shí)間復(fù)雜度都比較低呢？可擴(kuò)充性：并查集、線段樹實(shí)現(xiàn)復(fù)雜度：AVL樹vsTreap精品文檔功能數(shù)據(jù)結(jié)構(gòu)舉例并查集堆哈希表排序二叉樹線段樹精品文檔并查集：概念與操作不相交集合合并查找Tarjan數(shù)據(jù)結(jié)構(gòu)(Tarjan1975):森林表示法每棵樹一個(gè)集合,根為集合標(biāo)識(shí)樹的形態(tài)并不重要,重要的是有哪些節(jié)點(diǎn)合并:讓一棵樹成為另一棵的子樹,即修改父親查找:不停找父親,直到到達(dá)樹根特點(diǎn):只需要維護(hù)父親信息,不需要維護(hù)子女信息精品文檔并查集：實(shí)現(xiàn)與優(yōu)化基本實(shí)現(xiàn):父親表示法father:array[1..maxn]ofinteger;初始father[i]:=i;合并:father[u]:=v;查找:while(father[u]!=u)u:=father[u];優(yōu)化(啟發(fā)式合并+路徑壓縮)合并:深度較小的樹成為深度較大的樹的子樹查找:把經(jīng)過路徑上的點(diǎn)的父親都設(shè)為根效果？精品文檔并查集：時(shí)間復(fù)雜度分析回憶原始方案：合并基于深度值復(fù)雜之處：路徑壓縮對深度的影響不規(guī)則解決方案：設(shè)計(jì)基于rank值的合并rank的定義和計(jì)算規(guī)則剛建立的新集合的rank為0rank不同的樹合并：rank大的擁有新根，兩樹rank不變。rank相同的樹合并：任選一個(gè)擁有新根，把它的rank加1精品文檔均攤分析(amortizedanalysis)二進(jìn)制計(jì)數(shù)器問題有一個(gè)初始值為0的k位二進(jìn)制計(jì)數(shù)器只支持加一操作，該操作的時(shí)間復(fù)雜度如何？我們把改變一個(gè)二進(jìn)制位看作常數(shù)時(shí)間。均攤分析最壞情況下（k個(gè)1再加1）所有位都需要改變，為O(k)但是由于計(jì)數(shù)器在不斷加一，不可能連續(xù)若干次都遇到最壞情況應(yīng)分析一個(gè)操作序列的總時(shí)間，而非單個(gè)操作的時(shí)間。比較：平均情況時(shí)間復(fù)雜度是針對不同輸入來計(jì)算平均值的均攤分析是一個(gè)序列的所有操作取平均值二者從不同方面說。均攤分析可以是最壞情況，也可是平均情況。精品文檔累計(jì)分析（aggregateanalysis）

基本思想先計(jì)算n個(gè)操作的總時(shí)間T(n)每個(gè)操作的均攤時(shí)間復(fù)雜度就是T(n)/n了二進(jìn)制計(jì)數(shù)器問題第0位每次變化，因此一共變化n次；第1位每兩個(gè)操作變一次，一共變n/2次……第k位變化n/2k次，故總變化數(shù)小于2n次每次操作的均攤復(fù)雜度為O(n)/n=O(1)。精品文檔會(huì)計(jì)分析法（accountingmethod）

問題有的數(shù)據(jù)結(jié)構(gòu)支持多種操作，那么累計(jì)分析就無法計(jì)算出一個(gè)確定的值會(huì)計(jì)分析法把每個(gè)操作的實(shí)際時(shí)間消耗看做資金消耗（時(shí)間比做金錢?。┒x這種操作的“投資額”，供以后操作的使用。如果可以保證始終有可用資金，那么實(shí)際消費(fèi)的資金不會(huì)超過投資總量算法的時(shí)間耗費(fèi)（即資金消耗）的上限為總投資額。關(guān)鍵：投資額如何設(shè)計(jì)？精品文檔會(huì)計(jì)分析法一投資額設(shè)計(jì)方法一把任何一個(gè)0變成1的操作時(shí)投資2美元，而把1變成0時(shí)不進(jìn)行投資，則這2美元中的一個(gè)當(dāng)時(shí)就會(huì)用掉，而另一個(gè)可以提供給這個(gè)1變回到0時(shí)使用，因此可用資金數(shù)目等于1的數(shù)目，即總是非負(fù)的。由于每次最多只有一個(gè)0變成1（但可能有多個(gè)1變成0），因此投資總量不超過2n美元。雖然每改變一位都要用掉一個(gè)美元，但是由于剛才證明了始終有可用資金，因此資金消耗不超過2n美元，即：n個(gè)操作的總時(shí)間不超過O(n)。精品文檔會(huì)計(jì)分析法二投資額設(shè)計(jì)方法二每次操作時(shí)給第i個(gè)位投資2-i美元，則它從上一次翻轉(zhuǎn)起一共累計(jì)得到了1美元投資，正好夠它這一次翻轉(zhuǎn)，因此資金不會(huì)短缺每次操作投資2美元，所以一共投資了2美元，因此總時(shí)間不超過O(1)?？偨Y(jié)時(shí)間比作金錢，資金消耗代表時(shí)間消耗對操作或?qū)ο笸顿Y使得資金始終可用則資金消耗=O(投資額)微操作法、對象分類法精品文檔勢能分析法（potentialmethod）

勢能勢能為整個(gè)數(shù)據(jù)結(jié)構(gòu)的一個(gè)狀態(tài)函數(shù)。用Di表示經(jīng)過i次操作以后的數(shù)據(jù)結(jié)構(gòu)Φi表示Di的勢能原理ci為第i次操作（把Di-1變成Di）的實(shí)際時(shí)間耗費(fèi)第i次操作的均攤時(shí)間耗費(fèi)αi=ci+Φi-Φi-1把操作代價(jià)ci和勢能變化ΔΦ結(jié)合起來考慮精品文檔勢能分析法(續(xù))方法a的總和為sum{ci}+Φn-Φ0只要Φn>=0Φ0=0，則sum{ai}是sum{ci}的上界用均攤時(shí)間耗費(fèi)用真實(shí)時(shí)間耗費(fèi)設(shè)計(jì)合理的勢能函數(shù)，使得ai容易計(jì)算。好的勢函數(shù)應(yīng)讓ai均衡且容易計(jì)算快速操作時(shí)稍微增加一點(diǎn)耗時(shí)操作時(shí)迅速下降二進(jìn)制計(jì)數(shù)器問題定義當(dāng)前計(jì)數(shù)器的勢能為它包含的1的個(gè)數(shù)，則Φ0=0，Φi≥0(i>0)均成立，勢函數(shù)合法令第i個(gè)操作把a(bǔ)個(gè)0變成1，把b個(gè)1變成0，則ci=a+b，勢能增量為a-b，因此αi

=2a=2精品文檔并查集的時(shí)間復(fù)雜度結(jié)論（非最優(yōu)）m次操作，其中有n個(gè)是MAKESET操作運(yùn)行總時(shí)間為O(mlog*n)log*n定義為最小的i使得log(i)n≤1log(i)n即n連續(xù)取i次以2為底的對數(shù)如log(0)n=nlog(2)n=loglognlog*(265535)=5，故log*n≤4引入記號2^^b表示2的2的2的…2次方(b個(gè)2)(Knuth1976)2^^0=1,2^^1=2,2^^2=4,2^^3=16,2^^4=65536,2^^5=265536n<=1則log*x=0否則log*x=b當(dāng)且僅當(dāng)2^^(b-1)<x<=2^^b近似：所有操作均為O(1)精品文檔rank的性質(zhì)回憶：剛建立的新集合的rank為0rank不同的樹合并：rank大的擁有新根，兩樹rank不變。rank相同的樹合并：任選一個(gè)擁有新根，把它的rank加1不是根結(jié)點(diǎn)的元素，它的rank一定嚴(yán)格小于父親的rank。如果根結(jié)點(diǎn)的rank為r，那么整棵子樹的大小size≥2r結(jié)論一：對于大小為n的樹，它的根的rank最多為[log2n]對于任意整數(shù)r，在操作執(zhí)行過程中一旦有一棵樹的根的rank從r-1變到r，標(biāo)記該樹的所有結(jié)點(diǎn)（由剛才的結(jié)論，我們至少標(biāo)記了2r個(gè)結(jié)點(diǎn)）。由于這棵樹一旦有新根以后該根的rank至少為r+1，因此每個(gè)元素最多被標(biāo)記一次。由于每一個(gè)rank為r的元素都標(biāo)記了2r個(gè)結(jié)點(diǎn)，而一共有n個(gè)結(jié)論二：rank為r的元素最多有n/2r個(gè)。結(jié)論二是結(jié)論一的加深（rank的取值范圍和每個(gè)值的數(shù)量）精品文檔rank的性質(zhì)n個(gè)結(jié)點(diǎn)的樹根的rank最多為[log2n]rank嚴(yán)格遞減rank為r的元素最多有n/2r個(gè)進(jìn)一步把元素分類？分塊某個(gè)元素i的rank為rank(i)，那么它被分到第log*(rank(i))塊。rank最大值為[log2n]，因此最大塊的編號為log*(log2n)=log*n–1。可以證明，每一個(gè)塊b里面元素最多有n/(2^^b)個(gè)第r塊元素不超過n/2r個(gè)對r從2^^(b-1)+1到2^^b對n/2r求和結(jié)論三：共有l(wèi)og*n個(gè)塊，每塊b的元素最多有n/(2^^b)個(gè)精品文檔并查集的會(huì)計(jì)分析MAKESET和UNION每次都只用常數(shù)時(shí)間只需證明m個(gè)FIND所花時(shí)間是O(mlog*n)分析FIND(x0)從x0開始經(jīng)過序列x0，…，xL到達(dá)根結(jié)點(diǎn)xL。讓這個(gè)序列中的每個(gè)元素投資1美元但是不同的元素可能對不同的項(xiàng)目進(jìn)行投資序列中rank是嚴(yán)格遞增的各rank屬于log*n個(gè)塊，每個(gè)塊最多n/(2^^b)個(gè)精品文檔并查集的會(huì)計(jì)分析根xL對“l(fā)eader項(xiàng)目”投資。根的兒子xL-1對“child項(xiàng)目”投資。在其他情況中——xi和父親結(jié)點(diǎn)xi+1不屬同一塊的對在“block項(xiàng)目”投資。xi和父親結(jié)點(diǎn)xi+1屬同一塊的對“path項(xiàng)目”投資。每次FIND操作leader項(xiàng)目投資1美元child項(xiàng)目投資不超過1美元block項(xiàng)目投資不超過log*n美元（每個(gè)塊最多對應(yīng)1美元）因此m次FIND操作以后LCB三個(gè)項(xiàng)目的投資額不超過2m+mlog*n元惟一不好計(jì)算的是path項(xiàng)目

精品文檔path項(xiàng)目的投資額計(jì)算回憶如果一個(gè)結(jié)點(diǎn)現(xiàn)在不是根，則它以后永遠(yuǎn)也無法變成根只有根的rank才可能改變，因此——對于任何一個(gè)給path項(xiàng)目投資的結(jié)點(diǎn)xi它的rank始終不變每經(jīng)過一次FIND，xi的父親結(jié)點(diǎn)被設(shè)為了根而根的rank是嚴(yán)格比xi原來父親的rank大的因此它父親的rank每次嚴(yán)格增大，而它自己的rank不變因此它最終會(huì)和父親屬于不同的塊內(nèi)，不再為path項(xiàng)目投資了計(jì)算塊b的rank最大值為2^^b，因此xi最多投資2^^b次后父親脫離此塊塊b一共不超過n/(2^^b)個(gè)元素，因此塊b內(nèi)所有元素對path項(xiàng)目的投資額不超過n美元對于所有l(wèi)og*n個(gè)塊來說，對path項(xiàng)目的總投資額為nlog*n。四種投資額之和為2m+mlog*n+nlog*n=O(mlog*n)精品文檔并查集例題——可愛的猴子樹上掛著n只可愛的猴子（n≤2*105）。猴子1的尾巴掛在樹上每只猴子有兩只手，每只手可以抓住最多一只猴子的尾巴，也可以不抓。所有猴子都是懸空的，因此如果一旦脫離了樹，猴子會(huì)立刻掉到地上。第0，1，…，m（1≤m≤400000）秒中每一秒都有某個(gè)猴子把他的某只手松開，因此常有猴子掉在地上請計(jì)算出每個(gè)猴子掉到地上的時(shí)間精品文檔并查集例題——奇數(shù)偶數(shù)你的朋友寫下一個(gè)由0和1組成的字符串你從中選擇連續(xù)的子串（例如從第3到第5連續(xù)的3個(gè)數(shù)字），然后問他這個(gè)子串中1的個(gè)數(shù)是奇數(shù)還是偶數(shù)。你的朋友作出回答，然后你繼續(xù)問類似的問題。你估計(jì)你的朋友的回答中有一些錯(cuò)誤，你想證明他的錯(cuò)誤。你的目標(biāo)是找到第1個(gè)可能的錯(cuò)誤的回答，也就是說存在一個(gè)數(shù)字串滿足前面所有的問題，但對當(dāng)前的問題不滿足，而且沒有一個(gè)數(shù)字串滿足。例如，序列長度為10，信息條數(shù)為55條信息分別為12even，34odd，56even，16even，710odd正確答案是3，因?yàn)榇嬖谛蛄?0,0,1,0,1,1)滿足前3條信息，但是不存在滿足前4條的序列。精品文檔堆目標(biāo):快速插入O(logn),取最小值O(1),刪除O(logn)第一特點(diǎn)(形態(tài)):完全二叉樹第二特點(diǎn)(數(shù)據(jù)):每子樹最小值在根上插入:維持第一特點(diǎn):插到最后維持第二特點(diǎn):遞歸向上交換(判斷是否比父親小)刪除最小值維持第一特點(diǎn):根與最后節(jié)點(diǎn)交換,再刪除維持第二特點(diǎn):遞歸向下交換(如果需要,和較小兒子交換)精品文檔堆(續(xù))實(shí)現(xiàn)方法heap:array[1..maxn]ofinteger;i的父親為idiv2;左兒子2*i;右兒子2*i+1插入inc(n);heap[n]:=newnode;u:=n;while(u>1)and(heap[u]<heap[udiv2])begins[u],heap[udiv2]);u:=udiv2;end;刪除heap[1]:=heap[n];dec(n);u:=1;whiletruedobeginv:=min(u);ifu=vthenbreakelseu:=vend;精品文檔堆排序堆排序先建立堆，再每次取出最小值可以實(shí)現(xiàn)排序，而且它可以是部分排序。不穩(wěn)定排序建立堆一個(gè)一個(gè)插入元素嗎？不是的，那樣的時(shí)間復(fù)雜度將達(dá)到O(nlogn)，還不如直接排序后構(gòu)建一個(gè)堆。正確的做法是先將自底向上一層一層地調(diào)整每個(gè)結(jié)點(diǎn)到正確的位置，則交換操作執(zhí)行次數(shù)不超過4n。精品文檔堆例題——賽車有n輛賽車(1≤n≤250000)，從各不相同的地方(位置0≤xi≤1000000)，以各種的速度(速度0<vi<100)開始往右行駛，不斷有超車現(xiàn)象發(fā)生。給出n輛賽車的描述（位置xi，速度vi），賽車已按照位置排序（x1<x2<…<xn）。輸出超車的總數(shù)，以及按照時(shí)間排序的前m(m≤10000)個(gè)超車事件（如果事件同時(shí)發(fā)生，先輸出超車位置早的，數(shù)據(jù)保證沒有超車事件會(huì)同時(shí)同地發(fā)生）精品文檔哈希表(桶式)目標(biāo):插入O(1),查找O(1)實(shí)現(xiàn)用數(shù)組table:array[0..SIZE-1]儲(chǔ)存數(shù)據(jù)給數(shù)據(jù)d設(shè)計(jì)哈希函數(shù)hash(d)數(shù)據(jù)d放在table[hash(d)modSIZE]如果有多個(gè)d滿足hash(d)modSIZE=ktable[]只放第一個(gè)d的編號每個(gè)數(shù)據(jù)d附加一個(gè)域next,為hash表中的下一個(gè)項(xiàng)注意SIZE素?cái)?shù)為好hash函數(shù)本身的計(jì)算時(shí)間不要太長精品文檔哈希表例題——馬爾可夫鏈需要一些隨機(jī)的可以讀的英語文本，可以用一種相當(dāng)簡單的方法，讓計(jì)算機(jī)寫出一段比較像樣的文章來。這種技術(shù)被稱為“馬爾可夫鏈算法”，利用一個(gè)樣本來產(chǎn)生一段結(jié)構(gòu)與樣本相似的文章。算法具體過程如下(也可以根據(jù)需要隨時(shí)停止)：1．隨機(jī)在樣本中選連續(xù)的兩詞w1、w2作為文本的開頭2．輸出w1、w23．在樣本中隨機(jī)選取w1、w2的后繼w3，如果不存在w3，則結(jié)束算法4．輸出w35．令w1=w2，w2=w36．轉(zhuǎn)3對于一系列給定的前趨，分別輸出它們所有可能的后繼。樣本文件最多含有10000個(gè)單詞，大小不超過200k，前趨個(gè)數(shù)不超過2000000個(gè)，單詞不超過255個(gè)字母。文本完全是隨機(jī)生成。精品文檔排序二叉樹遞歸定義,左<根<右插入:直接遞歸刪除:先查找到該結(jié)點(diǎn)無兒子:直接刪除單個(gè)兒子:用兒子代替它兩個(gè)兒子:用后繼(在右子樹中一直左走)代替它問題:可能不平衡解決:AVL,RB-Tree,SplayTree,Treap…精品文檔排序二叉樹(續(xù))動(dòng)態(tài)實(shí)現(xiàn)TreeNode=recordv:integer;left,right,father:^TreeNode;end;優(yōu)點(diǎn):可實(shí)現(xiàn)在線算法缺點(diǎn):編程容易出錯(cuò)(刪除和指針操作),樹容易不平衡靜態(tài)實(shí)現(xiàn)Value:array[1..maxn]ofinteger;Count:array[1..maxn]ofinteger;優(yōu)點(diǎn):編程簡單(插入刪除查找統(tǒng)一),樹完美平衡缺點(diǎn):只能實(shí)現(xiàn)離線算法,需要知道所有數(shù)據(jù)并排序精