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

1、功能數(shù)據(jù)結(jié)構(gòu)1幾種常見的操作插入（insert）在數(shù)據(jù)結(jié)構(gòu)中增加一個數(shù)據(jù)。刪除（delete）在數(shù)據(jù)結(jié)構(gòu)中刪除一個數(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ù)處理時間和附加空間來換取更好的性能而不必?fù)?dān)心維護(hù)的復(fù)雜度。半靜態(tài)數(shù)據(jù)結(jié)構(gòu)、動態(tài)數(shù)據(jù)結(jié)構(gòu)對象空間分解關(guān)鍵碼空間分解2數(shù)據(jù)結(jié)構(gòu)設(shè)計的常見問題時間效率和空間開銷的關(guān)系矛盾。用時間去換空間或用空間換時間。需要做時空平衡統(tǒng)一。精簡數(shù)據(jù)表示有可能在縮減空間的同時設(shè)計出更快速的操作不同操作的關(guān)系例子：維護(hù)一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可修改，可查詢里面是否有

2、需要的元素有序數(shù)組。插入O(n)，查找O(logn)鏈表。插入O(1)，查找O(n)如何讓兩者的時間復(fù)雜度都比較低呢？可擴(kuò)充性：并查集、線段樹實現(xiàn)復(fù)雜度：AVL樹 vs Treap3功能數(shù)據(jù)結(jié)構(gòu)舉例并查集堆哈希表排序二叉樹線段樹4并查集：概念與操作不相交集合合并查找Tarjan數(shù)據(jù)結(jié)構(gòu)(Tarjan 1975): 森林表示法每棵樹一個集合, 根為集合標(biāo)識樹的形態(tài)并不重要, 重要的是有哪些節(jié)點合并: 讓一棵樹成為另一棵的子樹, 即修改父親查找: 不停找父親, 直到到達(dá)樹根特點: 只需要維護(hù)父親信息, 不需要維護(hù)子女信息5并查集：實現(xiàn)與優(yōu)化基本實現(xiàn): 父親表示法father:array1.maxn

3、 of integer;初始 fatheri := i;合并: fatheru := v;查找: while(fatheru!=u) u:=fatheru;優(yōu)化(啟發(fā)式合并+路徑壓縮)合并: 深度較小的樹成為深度較大的樹的子樹查找: 把經(jīng)過路徑上的點的父親都設(shè)為根效果？6并查集：時間復(fù)雜度分析回憶原始方案：合并基于深度值復(fù)雜之處：路徑壓縮對深度的影響不規(guī)則解決方案：設(shè)計基于rank值的合并rank的定義和計算規(guī)則剛建立的新集合的rank為0rank不同的樹合并：rank大的擁有新根，兩樹rank不變。rank相同的樹合并：任選一個擁有新根，把它的rank加17均攤分析(amortized an

4、alysis)二進(jìn)制計數(shù)器問題有一個初始值為0的k位二進(jìn)制計數(shù)器只支持加一操作，該操作的時間復(fù)雜度如何？我們把改變一個二進(jìn)制位看作常數(shù)時間。均攤分析最壞情況下（k個1再加1）所有位都需要改變，為O(k)但是由于計數(shù)器在不斷加一，不可能連續(xù)若干次都遇到最壞情況應(yīng)分析一個操作序列的總時間，而非單個操作的時間。比較：平均情況時間復(fù)雜度是針對不同輸入來計算平均值的均攤分析是一個序列的所有操作取平均值二者從不同方面說。均攤分析可以是最壞情況，也可是平均情況。 8累計分析（aggregate analysis） 基本思想先計算n個操作的總時間T(n)每個操作的均攤時間復(fù)雜度就是T(n)/n了二進(jìn)制計數(shù)器問

5、題第0位每次變化，因此一共變化n次；第1位每兩個操作變一次，一共變n/2次第k位變化n/2k次，故總變化數(shù)小于2n次每次操作的均攤復(fù)雜度為O(n)/n = O(1)。 9會計分析法（accounting method） 問題有的數(shù)據(jù)結(jié)構(gòu)支持多種操作，那么累計分析就無法計算出一個確定的值會計分析法把每個操作的實際時間消耗看做資金消耗（時間比做金錢?。┒x這種操作的“投資額”，供以后操作的使用。如果可以保證始終有可用資金，那么實際消費的資金不會超過投資總量算法的時間耗費（即資金消耗）的上限為總投資額。 關(guān)鍵：投資額如何設(shè)計？10會計分析法一投資額設(shè)計方法一把任何一個0變成1的操作時投資2美元，而把

6、1變成0時不進(jìn)行投資，則這2美元中的一個當(dāng)時就會用掉，而另一個可以提供給這個1變回到0時使用，因此可用資金數(shù)目等于1的數(shù)目，即總是非負(fù)的。由于每次最多只有一個0變成1（但可能有多個1變成0），因此投資總量不超過2n美元。雖然每改變一位都要用掉一個美元，但是由于剛才證明了始終有可用資金，因此資金消耗不超過2n美元，即：n個操作的總時間不超過O(n)。 11會計分析法二投資額設(shè)計方法二每次操作時給第i個位投資2-i美元，則它從上一次翻轉(zhuǎn)起一共累計得到了1美元投資，正好夠它這一次翻轉(zhuǎn)，因此資金不會短缺每次操作投資2美元，所以一共投資了2美元，因此總時間不超過O(1)。 總結(jié)時間比作金錢，資金消耗代表

7、時間消耗對操作或?qū)ο笸顿Y使得資金始終可用則資金消耗=O(投資額)微操作法、對象分類法12勢能分析法（potential method） 勢能勢能為整個數(shù)據(jù)結(jié)構(gòu)的一個狀態(tài)函數(shù)。用Di表示經(jīng)過i次操作以后的數(shù)據(jù)結(jié)構(gòu)i表示Di的勢能原理ci為第i次操作（把Di-1變成Di）的實際時間耗費第i次操作的均攤時間耗費i = ci + i - i-1把操作代價ci和勢能變化結(jié)合起來考慮13勢能分析法(續(xù))方法a的總和為sumci + n-0只要n=00=0，則sumai是sumci的上界用均攤時間耗費用真實時間耗費設(shè)計合理的勢能函數(shù)，使得ai容易計算。好的勢函數(shù)應(yīng)讓ai均衡且容易計算快速操作時稍微增加一點耗

8、時操作時迅速下降二進(jìn)制計數(shù)器問題定義當(dāng)前計數(shù)器的勢能為它包含的1的個數(shù)，則0=0，i0(i0)均成立，勢函數(shù)合法令第i個操作把a(bǔ)個0變成1，把b個1變成0，則ci = a+b，勢能增量為a-b，因此i = 2a = 2 14并查集的時間復(fù)雜度結(jié)論（非最優(yōu)）m次操作，其中有n個是MAKESET操作運行總時間為O(mlog*n)log*n定義為最小的i使得log(i)n1log(i)n即n連續(xù)取i次以2為底的對數(shù)如log(0)n=nlog(2)n = loglognlog*(265535) = 5，故log*n4引入記號2b表示2的2的2的2次方(b個2) (Knuth 1976)20=1, 21

9、=2, 22= 4, 23 = 16, 24=65536, 25=265536n=1則log*x = 0否則log*x=b當(dāng)且僅當(dāng)2(b-1)x1) and (heapuheapu div 2) begin su, heapu div 2); u := u div 2; end;刪除heap1 := heapn; dec(n);u:=1; while true dobegin v := min(u); if u = v then break else u := v end;24堆排序堆排序先建立堆，再每次取出最小值可以實現(xiàn)排序，而且它可以是部分排序。不穩(wěn)定排序建立堆一個一個插入元素嗎？不是的，

10、那樣的時間復(fù)雜度將達(dá)到O(nlogn)，還不如直接排序后構(gòu)建一個堆。正確的做法是先將自底向上一層一層地調(diào)整每個結(jié)點到正確的位置，則交換操作執(zhí)行次數(shù)不超過4n。 25堆例題賽車有n輛賽車(1n250 000)，從各不相同的地方(位置0 xi1 000 000)，以各種的速度(速度0vi100)開始往右行駛，不斷有超車現(xiàn)象發(fā)生。給出n輛賽車的描述（位置xi，速度vi），賽車已按照位置排序（x1x2xn）。輸出超車的總數(shù)，以及按照時間排序的前m(m10 000)個超車事件（如果事件同時發(fā)生，先輸出超車位置早的，數(shù)據(jù)保證沒有超車事件會同時同地發(fā)生）26哈希表(桶式)目標(biāo): 插入O(1), 查找O(1)

11、實現(xiàn)用數(shù)組table:array0.SIZE-1 儲存數(shù)據(jù)給數(shù)據(jù)d設(shè)計哈希函數(shù)hash(d)數(shù)據(jù)d放在tablehash(d) mod SIZE如果有多個d滿足hash(d) mod SIZE = ktable只放第一個d的編號每個數(shù)據(jù)d附加一個域next, 為hash表中的下一個項注意SIZE素數(shù)為好hash函數(shù)本身的計算時間不要太長27哈希表例題馬爾可夫鏈需要一些隨機(jī)的可以讀的英語文本，可以用一種相當(dāng)簡單的方法，讓計算機(jī)寫出一段比較像樣的文章來。這種技術(shù)被稱為“馬爾可夫鏈算法”，利用一個樣本來產(chǎn)生一段結(jié)構(gòu)與樣本相似的文章。算法具體過程如下(也可以根據(jù)需要隨時停止)：1隨機(jī)在樣本中選連續(xù)的兩

12、詞w1、w2作為文本的開頭2輸出w1、w23在樣本中隨機(jī)選取w1、w2的后繼w3，如果不存在w3，則結(jié)束算法4輸出w35令w1=w2，w2=w36轉(zhuǎn)3對于一系列給定的前趨，分別輸出它們所有可能的后繼。樣本文件最多含有10 000個單詞，大小不超過200k，前趨個數(shù)不超過 2 000 000個，單詞不超過255個字母。文本完全是隨機(jī)生成。 28排序二叉樹遞歸定義, 左 根 右插入: 直接遞歸刪除: 先查找到該結(jié)點無兒子: 直接刪除單個兒子: 用兒子代替它兩個兒子: 用后繼(在右子樹中一直左走)代替它問題: 可能不平衡解決: AVL, RB-Tree, Splay Tree, Treap29排序二

13、叉樹(續(xù))動態(tài)實現(xiàn)TreeNode = record v:integer; left, right, father: TreeNode; end;優(yōu)點: 可實現(xiàn)在線算法缺點: 編程容易出錯(刪除和指針操作), 樹容易不平衡靜態(tài)實現(xiàn)Value:array1.maxn of integer;Count:array1.maxn of integer;優(yōu)點: 編程簡單(插入刪除查找統(tǒng)一), 樹完美平衡缺點: 只能實現(xiàn)離線算法, 需要知道所有數(shù)據(jù)并排序30排序二叉樹例題采礦金礦的老師傅年底要退休了。經(jīng)理為了獎賞他的盡職盡責(zé)的工作，決定在一塊包含n（n15 000）個采金點的長方形土地中劃出一塊長度為S，

14、寬度為W的區(qū)域獎勵給他（1s, w10 000）。老師傅可以自己選擇這塊地的位置，顯然其中包含的采金點越多越好。你的任務(wù)就是計算最多能得到多少個采金點。如果一個采金點的位置在長方形的邊上，它也應(yīng)當(dāng)被計算在內(nèi) 31線段樹靜態(tài)BST根:1,n左:左半?yún)^(qū)間右:右半?yún)^(qū)間葉:單位區(qū)間空間:2n高度:logn例: 1,7中有條線段3,632線段樹(續(xù))實現(xiàn)靜態(tài)數(shù)組: interval_tree:array1.2*n of tnode;Tnode的信息: 父親、左右兒子編號, 線段數(shù)c建立首先處理根用隊列維護(hù)未處理的點每次從隊列取出點, 二分后給兒子新建編號并加入隊列插入和刪除本質(zhì)一樣, 插入是inc(ci), 刪除是dec(ci)第一次可能同時往兩邊遞歸, 但以后只往一邊繼續(xù)時間復(fù)雜度O(h) =