教程名稱(chēng):算法導(dǎo)論
教程目錄:
1.課程簡(jiǎn)介及算法分析
2.漸近符號(hào)、遞歸及解法
3.分治法(1)
4.快排及隨機(jī)化算法
5.線(xiàn)性時(shí)間排序
6.順序統(tǒng)計(jì)、中值
7.哈希表
8.全域哈希和完全哈希
9.二叉搜索樹(shù)
10.平衡搜索樹(shù)
樹(shù)的結(jié)構(gòu),如果不能保持平衡,那么其搜索性能會(huì)大大打折扣,而本節(jié)課介紹了幾種經(jīng)典的平衡樹(shù),如AVL,2-3-4tree,紅黑樹(shù)等等,然后著重講了紅黑樹(shù),接下來(lái)就紅黑樹(shù)的基本性質(zhì),作一些簡(jiǎn)短的總結(jié)。
首先,紅黑樹(shù)除了具有BST的基本性質(zhì)外,還額外擁有以下的五大基本性質(zhì):
1)每個(gè)結(jié)點(diǎn)有一個(gè)色域,一個(gè)結(jié)點(diǎn)要么為黑結(jié)點(diǎn),要么為紅結(jié)點(diǎn)
2)根節(jié)點(diǎn)為黑結(jié)點(diǎn)
3)每個(gè)葉子結(jié)點(diǎn)都為黑結(jié)點(diǎn)(無(wú)鍵值)
4)每個(gè)紅結(jié)點(diǎn)的父親都為黑結(jié)點(diǎn),即不可能出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相連的情況
5)從根節(jié)點(diǎn)到任意葉節(jié)點(diǎn)的路徑中的黑色結(jié)點(diǎn)數(shù)目相等,這個(gè)數(shù)目也稱(chēng)為黑高度
由以上5點(diǎn)性質(zhì),可以保證紅黑樹(shù)的高度為O(lgn),證明如下:
將紅黑樹(shù)的所有紅結(jié)點(diǎn),都與其父節(jié)點(diǎn)(由性質(zhì)四得其父節(jié)點(diǎn)必定為黑)合并,可以得到一顆2-3-4 tree(即每個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目為2~4個(gè)),由數(shù)據(jù)結(jié)構(gòu)知識(shí)可得,原紅黑樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為帶鍵值結(jié)點(diǎn)個(gè)數(shù)n+1,假設(shè)整棵樹(shù)高度為h,那么葉子結(jié)點(diǎn)數(shù)應(yīng)為h^2~h^4,因此有h^2<=n+1<=h^4,即此時(shí)樹(shù)高度最高也只有l(wèi)og n+1,即樹(shù)的黑高度為log n+1,根據(jù)性質(zhì)3,樹(shù)最高情況也不過(guò)是紅黑相間的時(shí)候,因此其高度最高只有2log n+1 ,即樹(shù)的高度為O(lgn)。
紅黑樹(shù)的查詢(xún)操作和普通BST一樣,而刪除和插入操作則相對(duì)復(fù)雜,因?yàn)槲覀円WC紅黑樹(shù)的5大性質(zhì),為什么需要保證這五大性質(zhì)呢?因?yàn)檫@五大性質(zhì)是紅黑樹(shù)為平衡樹(shù)的保證,能夠保證紅黑樹(shù)的高度為Olgn,這樣紅黑樹(shù)的基本操作(刪,插,查)都可以保證在Olgn的時(shí)間復(fù)雜度內(nèi)完成。
接下來(lái)簡(jiǎn)單介紹一下插入操作是如何完成的,刪除操作思路類(lèi)似:
插入操作的原理就是插入一個(gè)紅結(jié)點(diǎn),然后通過(guò)向上重染色和旋轉(zhuǎn)的方式維持紅黑樹(shù)的性質(zhì)
這里有三種情況
case1 xa0直線(xiàn)型 且祖父結(jié)點(diǎn)為黑,父節(jié)點(diǎn)和父親兄弟結(jié)點(diǎn)為紅 將祖父結(jié)點(diǎn)的黑傳遞到兩個(gè)紅子節(jié)點(diǎn) xa0 每次向上傳 xa0 xa0 xa0遞2個(gè)結(jié)點(diǎn),樹(shù)高度2lgn 所以操作為O(lgn)
case2 xa0zigzag Z型 父親兄弟結(jié)點(diǎn)為黑 旋轉(zhuǎn)為case3 xa0 O(1)的旋轉(zhuǎn)
case3 xa0zigzig直線(xiàn)型 旋轉(zhuǎn)
由以上三種情況可得,插入的時(shí)間復(fù)雜度為重染色的Olgn+不超過(guò)3次的O(1)的旋轉(zhuǎn)操作
這里值得一提的是,在實(shí)際的運(yùn)用中,雖然向上重染色理論上花費(fèi)的時(shí)間多于旋轉(zhuǎn),但是當(dāng)多個(gè)用戶(hù)并發(fā)查詢(xún)?cè)L問(wèn)紅黑樹(shù)的時(shí)候,重染色并不會(huì)影響查詢(xún),因?yàn)橛脩?hù)并不關(guān)心每個(gè)結(jié)點(diǎn)的顏色,但是旋轉(zhuǎn)需要鎖定該子樹(shù)及其結(jié)點(diǎn),可能會(huì)影響并發(fā)查詢(xún)的操作。
最后,就AVL和紅黑樹(shù)做一下比較,就平衡程度而言,AVL是追求的絕對(duì)平衡,任意葉子結(jié)點(diǎn)的深度不會(huì)多于其他葉子結(jié)點(diǎn)深度+1,而紅黑樹(shù)只要求局部平衡,其紅黑性保證了其平衡性,因此在維護(hù)平衡方面,紅黑樹(shù)只需要不超過(guò)3次旋轉(zhuǎn)即可,這一點(diǎn)是AVL樹(shù)所做不到的,但查詢(xún)方面,由于AVL是絕對(duì)平衡,因此效率會(huì)略高于紅黑樹(shù),實(shí)際應(yīng)用中這一點(diǎn)并不明顯,就統(tǒng)計(jì)性能而言,紅黑樹(shù)會(huì)優(yōu)于AVL,而C++ STL中的set、multiset、map、multimap等,都是紅黑樹(shù)的一種變體。
值得一提的是,平衡樹(shù)都是動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu),其優(yōu)勢(shì)在于動(dòng)態(tài)操作下,也能保持優(yōu)越的查詢(xún)效率,如果是靜態(tài)數(shù)據(jù),那么使用hash表效率會(huì)更高一些。
11.擴(kuò)充的數(shù)據(jù)結(jié)構(gòu)、動(dòng)態(tài)有序統(tǒng)計(jì)和區(qū)間樹(shù)
本節(jié)課主要講了如何構(gòu)造自己想要的數(shù)據(jù)結(jié)構(gòu),或者擴(kuò)充已有數(shù)據(jù)結(jié)構(gòu)的功能,以實(shí)現(xiàn)想要的特定功能
比如設(shè)計(jì)一個(gè)動(dòng)態(tài)結(jié)構(gòu),滿(mǎn)足功能尋找第k大的數(shù)
其做法是維護(hù)每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)來(lái)推導(dǎo)其秩,而不維護(hù)其秩,因?yàn)閯?dòng)態(tài)操作會(huì)使得其難以維護(hù)
紅黑樹(shù)的插入操作 1.樹(shù)插入 2.rebalance
構(gòu)造自己需要的擴(kuò)充數(shù)據(jù)結(jié)構(gòu)的基本流程
1.選擇一個(gè)基本的數(shù)據(jù)結(jié)構(gòu) 例如紅黑樹(shù)
2.決定要添加到結(jié)點(diǎn)的基本信息 xa0例如實(shí)現(xiàn)查詢(xún)第k大數(shù)功能,應(yīng)添加的基本信息為所有子樹(shù)結(jié)點(diǎn)之和,而非直接保存該結(jié)點(diǎn)鍵值的秩
3 維持 插入+旋轉(zhuǎn)/刪除+旋轉(zhuǎn)
4 封裝為函數(shù),實(shí)現(xiàn)其功能
12.跳躍表
跳躍表是一種簡(jiǎn)單又有趣的動(dòng)態(tài)搜索數(shù)據(jù)結(jié)構(gòu),其主要優(yōu)點(diǎn)在于其易于實(shí)現(xiàn),而且很好的保證了其具有高效的性能,即2*O(lgn)的搜索性能
在此之前我想首先談?wù)勬湵恚湵淼膬?yōu)點(diǎn)在于其插入和刪除只需要常數(shù)項(xiàng)的時(shí)間(加上查找該元素需要額外的O(n)時(shí)間),但是其查找效率只有O(n),這里順帶補(bǔ)充一下鏈表類(lèi)的問(wèn)題,以下先給出兩個(gè)BAT公司面試時(shí)熱衷于考的兩個(gè)鏈表經(jīng)典問(wèn)題:
1.如何快速查找單向鏈表倒數(shù)第m個(gè)元素
2.如何快速判斷一個(gè)單向鏈表是否存在環(huán)
對(duì)于鏈表類(lèi)問(wèn)題,其核心思想不外乎兩點(diǎn),1是開(kāi)雙指針(甚至多指針),2是開(kāi)雙鏈表(甚至多鏈表),其實(shí)以上兩個(gè)問(wèn)題開(kāi)雙指針便能巧妙地解決,第一個(gè)問(wèn)題,先開(kāi)一個(gè)指針走m步,然后再開(kāi)一個(gè)指針同步走,當(dāng)前一個(gè)指針走到鏈表末端時(shí),后一個(gè)指針就正好指向倒數(shù)第m個(gè)元素了,第二個(gè)問(wèn)題,開(kāi)一個(gè)快指針和一個(gè)慢指針,快指針每次移動(dòng)兩步,慢指針每次移動(dòng)一步,如果存在環(huán),那么快指針一定會(huì)追到慢指針,可以想象兩個(gè)人在操場(chǎng)賽跑,快的人跑了很久之后會(huì)超慢的人一圈。
接下來(lái)我們繼續(xù)談跳躍表,其實(shí)跳躍表用到的就是第二個(gè)思路,開(kāi)雙鏈表甚至多個(gè)鏈表
首先考慮建立兩個(gè)鏈表L1和L2,L1為快表,即只保存部分元素,L2為慢表保存全部元素,注意,以下提到的鏈表均為排好序的鏈表
當(dāng)我們要搜索某一元素時(shí),我們先走快表,因?yàn)榭毂碇槐A袅瞬糠衷兀允翘S前進(jìn)的,直到快表走過(guò)該元素,我們?cè)偻嘶乜毂砬耙粋€(gè)結(jié)點(diǎn)換到慢表繼續(xù)走,這樣效率顯然比在慢表上進(jìn)行線(xiàn)性查找要好一些,這里的快慢表就像美國(guó)地鐵的快慢線(xiàn)地鐵一樣,快線(xiàn)的地鐵只在幾個(gè)站停頓,而慢線(xiàn)會(huì)在所有站停頓,乘客可以先乘快線(xiàn)到一個(gè)最接近目的地的前一個(gè)站,再轉(zhuǎn)乘慢線(xiàn)到達(dá)該地
那么問(wèn)題來(lái)了?
如何建表L1和 L2呢?L2無(wú)疑是一條包含所有結(jié)點(diǎn)的單向鏈表,那么L1應(yīng)該設(shè)置多少個(gè)結(jié)點(diǎn)最為合理呢,直觀上感受L1應(yīng)該是均勻分布最好,那么是以怎樣的密度分布最合適呢?
我們不難得出查找時(shí)間上界為|L1|+|L2|/|L1|+換乘的常數(shù),這里|L1|表示L1的長(zhǎng)度(最壞情況就是L1走到末端后,走回一個(gè)節(jié)點(diǎn)然后進(jìn)入L2,因?yàn)長(zhǎng)2可以看做被L1分成了L1個(gè)段,所以每段長(zhǎng)度為|L2|/|L1|,所以為|L1|+|L2|/|L1|+換乘的常數(shù)),因?yàn)長(zhǎng)2長(zhǎng)度為n(包括整個(gè)鏈表),換乘即鏈表L1向下走到L2的時(shí)間,為常數(shù),所以我們的目標(biāo)是要使得|L1|+n/|L1|最小,即|L1|為sqrt(n)時(shí)最優(yōu)(可以求導(dǎo)得出或者通過(guò)其他數(shù)學(xué)方法,證明略),此時(shí)時(shí)間消耗為2*sqrt(n),即每隔sqrt(n)設(shè)立一個(gè)快表的結(jié)點(diǎn),共sqrt(n)個(gè)快表結(jié)點(diǎn)
什么?sqrt(n)還不過(guò)癮?
那么我們還能做怎樣的優(yōu)化呢?答案是加更多的鏈表,我們看看三條鏈表應(yīng)是多少,直覺(jué)告訴我們是3*n的1/3次方
其實(shí),可以證明k條鏈表的時(shí)候?yàn)閗*n的1/k次方
因?yàn)閚是常數(shù),那么k多大比較合適呢?lgn! 讓我們看看k取lgn的時(shí)候?yàn)槎嗌伲磍gn*n^(1/lgn)為多少,即求lgn*n^logn(2),還記得我們計(jì)算遞歸時(shí)間復(fù)雜度時(shí)的換底公式嗎?這里n^logn(2)即2^logn(n)即2^1,即2,所以整個(gè)時(shí)間復(fù)雜度為2*lgn,這是一個(gè)非常好的性能。
這種情況下的跳躍表稱(chēng)為理想跳躍表,每一層數(shù)量減少一半,總共lgn層鏈表,從最上級(jí)鏈表開(kāi)始搜,搜不到就向下,最多下logn層,每層最多搜2個(gè)元素,所以搜索復(fù)雜度為O(2lgn)
那么問(wèn)題又來(lái)了,如何動(dòng)態(tài)維護(hù)這樣一個(gè)跳躍表呢?
先看刪除功能,刪除功能只要從上級(jí)鏈表搜到之后,就可以直接刪除,并向下將所有鏈表的該結(jié)點(diǎn)都刪除,這個(gè)比較簡(jiǎn)單,那么插入呢?
插入(x) 先search(x)在底表的位置然后插入該元素,是否結(jié)束了呢?不,因?yàn)樵谀骋欢芜B續(xù)插入若干個(gè)結(jié)點(diǎn)后,這一段會(huì)變得非常長(zhǎng),整個(gè)跳躍表的平衡結(jié)構(gòu)無(wú)疑會(huì)被打破,那么如何維護(hù)理想線(xiàn)段表的結(jié)構(gòu)呢?
1.保持每段之間的理想距離,如果距離過(guò)大,就從中間分割,然后將中點(diǎn)上升一層結(jié)點(diǎn)
這個(gè)方法從直觀上看非常巧妙,但是實(shí)行起來(lái)卻有一定難度,因?yàn)槟惚仨殞?shí)時(shí)記錄每一段的長(zhǎng)度
2.采用我們最喜歡的隨機(jī)化算法,拋硬幣 如果正面,就把這個(gè)結(jié)點(diǎn)提升一個(gè)level(即把該結(jié)點(diǎn)也加入上一級(jí)的鏈表中),再拋硬幣(看是否持續(xù)提升level),因?yàn)閮蓚€(gè)相鄰鏈表的長(zhǎng)度之比為1:2,而硬幣出正面的概率也是50%,事實(shí)證明這樣做是可行的,這里值得一提的是,老師在這節(jié)課發(fā)了兩個(gè)硬幣給同學(xué),一個(gè)利用拋硬幣產(chǎn)生隨機(jī)數(shù),一個(gè)利用拋硬幣決定當(dāng)前插入結(jié)點(diǎn)是否需要提升level,在課堂上直接做起了實(shí)驗(yàn),整個(gè)課程氛圍也很好,也讓同學(xué)們都對(duì)該算法有了直觀的理解,這一種教學(xué)方式很值得借鑒
注意,這里需要考慮一個(gè)特殊情況,就是當(dāng)我們插入的元素為最小的元素時(shí),如果它沒(méi)有提升一個(gè)level,那么上級(jí)鏈表的開(kāi)頭就不是第一個(gè)元素,這樣也會(huì)打亂整個(gè)跳躍表的理想結(jié)構(gòu),因此我們需要打個(gè)補(bǔ)丁:即把一個(gè)負(fù)無(wú)窮值插到所有鏈表頭,這樣就算插入了一個(gè)最小的元素也能保證每個(gè)表是以負(fù)無(wú)窮開(kāi)始,即每個(gè)鏈表都可以從最左邊開(kāi)始。
在課堂上,通過(guò)實(shí)驗(yàn)表明算法2似乎在平均情況下可以得到一個(gè)很好的跳躍表,其實(shí)不僅僅是平均情況可以得到一個(gè)好的跳躍表,在絕大多數(shù)情況都可以得到一個(gè)好的跳躍表.
可以證明,得到一個(gè)好的跳躍表的概率P>=1-O(1/n^a) xa0這里a是一個(gè)介于0到1的參數(shù),與n有關(guān),在課堂的最后,老師花了盡20分鐘的時(shí)間來(lái)證明,具體證明方式我們這里略過(guò)(其實(shí)是我根本沒(méi)看懂其證明過(guò)程 逃~~)
13.平攤分析,表的擴(kuò)增,勢(shì)能方法
先通過(guò)表的擴(kuò)增這一例子來(lái)引入今天的主題——平攤分析和勢(shì)能分析
一個(gè)哈希表的大小應(yīng)該為多少比較合適?
theta(n)比較合適
可是萬(wàn)一我們不知道n是多大呢
使用動(dòng)態(tài)表解決 xa0溢出就建立一個(gè)大小翻倍的空間,然后復(fù)制過(guò)去
這樣做插入的最壞時(shí)間復(fù)雜度為n
讓我們看看平均的時(shí)間復(fù)雜度,每次基本插入操作為1,空間溢出時(shí)需要開(kāi)一個(gè)更大一倍的空間,并復(fù)制當(dāng)前的元素過(guò)去,所以空間溢出時(shí)所需要的時(shí)間為2的i次方(i為第幾次溢出)
所以其真實(shí)的時(shí)間消耗為n+sigma(2^i) xa0 0<=i<=lg(n+1) xa0即3n
因此其實(shí)插入的時(shí)間復(fù)雜度為O(1)
盡管有時(shí)會(huì)有巨大開(kāi)銷(xiāo),但是會(huì)被平均的開(kāi)銷(xiāo)平攤掉,這就是平攤分析
平攤分析:平均操作復(fù)雜度不高,盡管有些操作會(huì)有較高的復(fù)雜度
三種類(lèi)型的平攤方法:
1.聚集分析
2.記賬方法(accounting)
3.勢(shì)能分析
2.3它們?yōu)槊恳粋€(gè)操作分配了特點(diǎn)的平攤代價(jià)
記賬方法:
想象自己擔(dān)任了一個(gè)會(huì)記
對(duì)第i個(gè)操作收費(fèi)為ci
收益?zhèn)€虛構(gòu)的平攤代價(jià)
每一步運(yùn)算需要花費(fèi)1$
未用到的余款就被存到銀行,用于償付以后的操作
如每次插入收費(fèi)為3,插入消耗1,剩下的2存入銀行為表翻倍時(shí)做準(zhǔn)備,要始終保證銀行的金額為正
即提前平攤,總能支付擴(kuò)充表的費(fèi)用,這樣某一個(gè)高開(kāi)銷(xiāo)的操作會(huì)被平攤掉
勢(shì)能方法:
算法分析里最漂亮的產(chǎn)物之一
剛開(kāi)始數(shù)據(jù)結(jié)構(gòu)狀態(tài)為D0
操作i的代價(jià)為ci
操作i可以看作把數(shù)據(jù)結(jié)構(gòu)由Di-1轉(zhuǎn)化為Di
定義勢(shì)能函數(shù)
將數(shù)據(jù)結(jié)構(gòu)的集合定位實(shí)數(shù)值
D0 = 0 初始的勢(shì)為0
所有Di >=0,我們不能讓勢(shì)低于0
定義平攤代價(jià)為Ai,對(duì)勢(shì)能Di有Ai=Ci+Di-Di-1
Di-Di-1 部分是勢(shì)能的改變量,如果其>=0 那么Ai>ci 我收取的費(fèi)用超過(guò)了實(shí)際的花費(fèi),即操作i儲(chǔ)存了后面數(shù)據(jù)結(jié)構(gòu)所需的功
如果勢(shì)能的改變量<0,即我們用存儲(chǔ)的勢(shì)能轉(zhuǎn)化為能量來(lái)幫助完成操作i
記賬方法考慮的是平攤代價(jià)
而勢(shì)能分析考慮的是銀行存款(存儲(chǔ)勢(shì)能)
有sigmaAi=sigma(ci+Di-Di-1)=sigma(ci+Dn-D0)
D0為0,Dn大于等于0,所以左邊大于右邊,是實(shí)際代價(jià)的一個(gè)上界
我們?cè)俅我员淼臄U(kuò)增為例感受一下勢(shì)能分析
我們的勢(shì)能函數(shù)為2i-2^ceil(lgi) xa0
如何推導(dǎo)出這樣的勢(shì)能函數(shù)的?
定義勢(shì)能函數(shù)難度低于定義平攤代價(jià)
第i個(gè)操作的平攤代價(jià)Ai=Ci+Di-Di-1= xa0i+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))(剛好i是2的冪)
case1 i-1是2的冪,那么Ai=i+2-2(i-1)+(i-1)=3
case2 i-1不是2的冪 那么Ai=1+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))=3
這樣得到的平攤代價(jià)也為3
不關(guān)注實(shí)時(shí)性能只關(guān)注聚集性能
14.競(jìng)爭(zhēng)性分析,自組織表
15.動(dòng)態(tài)規(guī)劃,最長(zhǎng)公共子序列
16.貪婪算法,最小生成樹(shù)
17.最短路徑算法:Dijkstra算法,廣度優(yōu)先搜索
18.最短路徑算法:Bellman和差分約束系統(tǒng)
19.最短路徑算法:點(diǎn)的最短路徑
20.高級(jí)課題 并行算法(一)
21.高級(jí)課題 并行算法(二)xa0
22.高級(jí)課題 緩存參數(shù)無(wú)關(guān)算法