 |
 |
 |
| 24小時(shí)熱門(mén)版塊排行榜 |
- >論壇更新日志 (6072)
- >導(dǎo)師招生 (1258)
- >考研 (1119)
- >文獻(xiàn)求助 (491)
- >蟲(chóng)友互識(shí) (302)
- >考博 (208)
- >休閑灌水 (185)
- >基金申請(qǐng) (183)
- >碩博家園 (140)
- >招聘信息布告欄 (108)
- >博后之家 (91)
- >綠色求助(高懸賞) (51)
- >論文投稿 (46)
- >找工作 (40)
- >SciFinder/Reaxys (26)
- >外文書(shū)籍求助 (19)
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 2309 | 回復(fù): 8 | ||||
formleaf木蟲(chóng) (正式寫(xiě)手)
|
[交流]
【轉(zhuǎn)帖】《數(shù)據(jù)結(jié)構(gòu)與算法分析》5000字縮寫(xiě)(上) 已有4人參與
|
|
http://www.matrix67.com/blog/archives/90 4月7日買(mǎi)起來(lái)看，前幾天才看完。這可以說(shuō)明很多問(wèn)題，比如，學(xué)習(xí)很緊張，沒(méi)有時(shí)間；書(shū)本身很好，很有看頭；看書(shū)看得很細(xì)心，很有耐心。 打算大致寫(xiě)一下書(shū)里的內(nèi)容。 Data Structures and Algorithm Analysis in C, Second Edition，機(jī)械工業(yè)出版社。封面很丑，一個(gè)黑底版，上面有些大理石花紋，正中間生硬的擺一個(gè)原版封面，同樣丑。一共12章，近400頁(yè)。 400多頁(yè)是很多的。我們必須要“把厚書(shū)讀薄”，厚的變薄的，薄的變一頁(yè)，一頁(yè)變一行，一行變成一個(gè)字。因此，我要在有限的字?jǐn)?shù)內(nèi)把整本書(shū)說(shuō)完。 算法分析，就是復(fù)雜度的問(wèn)題。復(fù)雜度只算“最要命的”，比如，執(zhí)行n^2的算法前來(lái)個(gè)快排根本不拖速度，n^2多的都豁出去了不在乎區(qū)區(qū)一個(gè)nlogn。書(shū)里對(duì)復(fù)雜度進(jìn)行了嚴(yán)格的定義，包括O()、o()、Θ()、Ω()四種符號(hào)。簡(jiǎn)單地說(shuō)，O(n^2)就是頂破天了搞個(gè)n^2次；o(n^2)就是天花板不到n^2，比n^2矮一點(diǎn)（比如希爾排序就是o(n^2)，因?yàn)樗俚姑挂策_(dá)不到n^2）；Ω(n^2)就是說(shuō)某個(gè)算法隨便怎么至少都要耗費(fèi)n^2，比如所有基于比較的排序都是Ω(nlogn)；Θ(n^2)就是說(shuō)它即是O(n^2)又是Ω(n^2)，被天花板和水泥地夾在中間了，動(dòng)不了了，就是它了。這里面有一個(gè)經(jīng)典的例子，就是最大子序列（找數(shù)列中連續(xù)一段數(shù)之和最大）的四種算法，復(fù)雜度分別為O(n^3)、O(n^2)、O(nlogn)和O (n)。這書(shū)一個(gè)特色在于，對(duì)每種數(shù)據(jù)結(jié)構(gòu)都有嚴(yán)格的算法復(fù)雜度證明，這往往是看上去最頭痛的部分。 表、棧和隊(duì)列是三個(gè)基本的數(shù)據(jù)結(jié)構(gòu)。說(shuō)穿了表就是把數(shù)據(jù)找起來(lái)排排坐吃果果，找什么東西都來(lái)把整個(gè)隊(duì)伍找一遍。棧就是一個(gè)桶，后放進(jìn)去的先拿出來(lái)，它下面本來(lái)有的東西要等它出來(lái)之后才能出來(lái)，就好像你看到了一個(gè)丑人不可能今天的中飯還沒(méi)吐出來(lái)就先把早飯吐出來(lái)了。棧是拿來(lái)模擬多個(gè)過(guò)程的調(diào)用的（比如遞歸），實(shí)際點(diǎn)的用途就是表達(dá)式計(jì)算。隊(duì)列好比堵車(chē)，先進(jìn)去的先出來(lái)。先進(jìn)隊(duì)先買(mǎi)票，不能插隊(duì)。常拿來(lái)實(shí)現(xiàn)廣搜。 樹(shù)，是一種植物，有很多枝枝丫丫。不同的是這里的樹(shù)是倒著的，樹(shù)枝朝下長(zhǎng)。最上面叫根，尖尖的地方叫樹(shù)葉，生出樹(shù)葉的是他爸，他爸生的是他兒子。不管是根是樹(shù)葉還是兒子還是兒子他爸都叫節(jié)點(diǎn)。我們常常把數(shù)據(jù)儲(chǔ)存在節(jié)點(diǎn)上，并且以后還要不斷地插入、改變和刪除數(shù)據(jù)。 二叉樹(shù)就是每個(gè)分叉的地方最多分兩個(gè)岔，而且還分得清左右。二叉查找樹(shù)就是說(shuō)把數(shù)據(jù)存在節(jié)點(diǎn)上，而且左邊的都比他爸小，右邊的都比他爸大，以后要找哪個(gè)數(shù)就可以只找其中的一邊，一半一半地扔掉。在二叉查找樹(shù)里也可以插入一個(gè)數(shù)，刪掉一個(gè)數(shù)（只有一個(gè)兒子好辦，有兩個(gè)就把右邊的最小的一個(gè)拿來(lái)替代這個(gè)），找最小的數(shù)（一直往左走），找最大的數(shù)（一直往右走），但是容易搞著搞著的樹(shù)就變畸形了，比如說(shuō)左邊猛起長(zhǎng)右邊萎縮導(dǎo)致以后往左邊走要走很久。我們就需要一種方法來(lái)讓樹(shù)左右差不多一樣多而且左邊的值仍然比右邊的小。事實(shí)上這種方法已經(jīng)找到了，而且不只一種方法，而是一卡車(chē)的方法，比如AVL、Splay、紅黑樹(shù)、Treap等。幾種方法都靠一個(gè)叫“旋轉(zhuǎn)”的技巧，就是把幾個(gè)節(jié)點(diǎn)怎么個(gè)一轉(zhuǎn)，左邊的就跑到右邊去了一點(diǎn)�？聪旅孢@個(gè)圖你就明白了。 ① ② / \ 旋轉(zhuǎn) / \ ② ZZ ------> XX ① / \ / \ XX YY YY ZZ 這樣一來(lái)左邊就少了，如果左邊的XX本來(lái)很多的話(huà)就可以往上提一層從而平衡。同樣地，右邊多了反過(guò)來(lái)做就是了。這只是最簡(jiǎn)單的“單旋轉(zhuǎn)”，事實(shí)上還有很多其它的較復(fù)雜的旋轉(zhuǎn)方法。Splay樹(shù)就是把剛才訪問(wèn)過(guò)的節(jié)點(diǎn)轉(zhuǎn)啊轉(zhuǎn)啊轉(zhuǎn)啊轉(zhuǎn)轉(zhuǎn)到最頂上去，Treap就是每個(gè)節(jié)點(diǎn)附加一個(gè)隨機(jī)的數(shù)，隨時(shí)通過(guò)旋轉(zhuǎn)保持兒子的這些隨機(jī)數(shù)比他爸大，其余的有點(diǎn)復(fù)雜。這些方法都能使二叉查找樹(shù)相對(duì)地平衡一些，防止畸變導(dǎo)致的時(shí)間浪費(fèi)。 B-樹(shù)和二叉查找樹(shù)有兩個(gè)不同，一個(gè)是節(jié)點(diǎn)不存數(shù)據(jù)，數(shù)據(jù)全在樹(shù)葉子上，二個(gè)是它不一定是二叉。數(shù)據(jù)仍然左邊小右邊大方便查找。每個(gè)節(jié)點(diǎn)最多的兒子數(shù)有限制，最多三叉的叫2-3樹(shù)，最多四叉的叫2-3-4樹(shù)。因?yàn)橹挥袠?shù)葉上有數(shù)據(jù)，所以可以遞歸地用分裂的方法處理新插入后出現(xiàn)的分叉比規(guī)定的最多的兒子個(gè)數(shù)時(shí)還多的情況。比如，2-3樹(shù)中如果哪里分了四個(gè)岔，就把它重新分成兩個(gè)兩個(gè)的岔。我們還規(guī)定，除了根以外，每個(gè)節(jié)點(diǎn)最少的兒子數(shù)是規(guī)定的最多兒子數(shù)的一半，除不盡取上整。容易想到，刪除的話(huà)可以把插入時(shí)的分裂反過(guò)來(lái)做，什么時(shí)候只剩一個(gè)兒子了就和旁邊的合并起來(lái)。 Hash表又叫散列表，一般用于判斷有沒(méi)有重復(fù)。比如我想找我們班有沒(méi)有兩個(gè)一天生的，我們不必每?jī)蓚�(gè)人都來(lái)比較一次，而是準(zhǔn)備一個(gè)年歷，讓人一個(gè)一個(gè)上去在他的生日那天那里畫(huà)一個(gè)圈，如果誰(shuí)要畫(huà)圈時(shí)發(fā)現(xiàn)那里已經(jīng)有一個(gè)圈了，就找到了一對(duì)。這個(gè)很簡(jiǎn)單，不說(shuō)了。 那天班上流行一個(gè)心里測(cè)試，當(dāng)時(shí)我還真發(fā)現(xiàn)了一個(gè)和我一天生的，女的。 |
回復(fù)此樓» 收錄本帖的淘帖專(zhuān)輯推薦
 數(shù)據(jù)結(jié)構(gòu)與算法 |
» 猜你喜歡
085600材料與化工調(diào)劑
已經(jīng)有10人回復(fù)
-
279分求調(diào)劑 一志愿211
已經(jīng)有18人回復(fù)
-
0703化學(xué)求調(diào)劑
已經(jīng)有5人回復(fù)
-
材料292調(diào)劑
已經(jīng)有3人回復(fù)
-
一志愿陜師大生物學(xué)071000，298分，求調(diào)劑
已經(jīng)有3人回復(fù)
-
306求0703調(diào)劑一志愿華中師范
已經(jīng)有7人回復(fù)
-
333求調(diào)劑
已經(jīng)有3人回復(fù)
-
335求調(diào)劑
已經(jīng)有4人回復(fù)
-
336求調(diào)劑
已經(jīng)有4人回復(fù)
-
303求調(diào)劑
已經(jīng)有4人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 有沒(méi)有注意到不同操作系統(tǒng)下字體不一的情況
已經(jīng)有16人回復(fù)
- 求該段最后文字的翻譯
已經(jīng)有5人回復(fù)
- Springer投稿要求參考文獻(xiàn)刊名縮寫(xiě)問(wèn)題
已經(jīng)有7人回復(fù)
- 請(qǐng)問(wèn)反應(yīng)器物料和熱量平衡中ZMX和CPCVMX是什么的縮寫(xiě)，代表什么意思？
已經(jīng)有7人回復(fù)
- JHM字?jǐn)?shù)超過(guò)5000，怎么辦？字?jǐn)?shù)管的嚴(yán)嗎?
已經(jīng)有6人回復(fù)
- 【求助】請(qǐng)教各位，知道幾種物質(zhì)的縮寫(xiě)，不知道具體的物質(zhì)是什么
已經(jīng)有4人回復(fù)
- 30篇英文參考文獻(xiàn)占了5000字符，怎么處理參考文獻(xiàn)呢。
已經(jīng)有7人回復(fù)
- 求助英文縮寫(xiě)規(guī)則
已經(jīng)有9人回復(fù)
formleaf
木蟲(chóng) (正式寫(xiě)手)
- 應(yīng)助: 0 (幼兒園)
- 貴賓: 1.097
- 金幣: 3383.1
- 散金: 2780
- 紅花: 3
- 帖子: 991
- 在線(xiàn): 69.6小時(shí)
- 蟲(chóng)號(hào): 698652
- 注冊(cè): 2009-02-09
- 性別: GG
- 專(zhuān)業(yè): 組合數(shù)學(xué)
《數(shù)據(jù)結(jié)構(gòu)與算法分析》5000字縮寫(xiě)(中)
★
haixing2008(金幣+1): 2010-02-13 09:39
haixing2008(金幣+1): 2010-02-13 09:39
|
http://www.matrix67.com/blog/archives/91 堆，就是一陀一陀的東西。頭重腳輕不算堆，要上面小下面大才算一個(gè)堆。堆是一棵二叉樹(shù)，滿(mǎn)足下面的始終比上面的大。它和二叉查找樹(shù)比較起來(lái)既有好的又有不好的：好的就是要想知道數(shù)據(jù)里的最小值時(shí)根本就不用找了，直接就是最頂上的那個(gè)了；不好的就是堆除了這個(gè)以外基本上不能做別的事了。除了最頂上的那個(gè)以外，你幾乎沒(méi)辦法控制其余的部分。當(dāng)然，插入和刪除數(shù)據(jù)這種基本操作還是可以做的。插入就是把數(shù)據(jù)暫時(shí)先放在最下面的某個(gè)位置，然后通過(guò)與它上面一個(gè)進(jìn)行比較、交換不斷往上冒直到已經(jīng)到了自己的位置不能再向上為止。刪除反起來(lái)，通過(guò)不斷交換往下沉一直沉到底。因?yàn)槭峭伦�，所以要考慮到一個(gè)把左邊的放上來(lái)還是把右邊的放上來(lái)的問(wèn)題。當(dāng)然，為了保證堆上小下大的性質(zhì)，應(yīng)該把小的一邊換上來(lái)。剛才說(shuō)過(guò)，由于你只能“看”到最頂上的東西，不知道中間部分是什么樣，我們通常只刪除最小的（最上面的）那個(gè)節(jié)點(diǎn)。其實(shí)堆還有一個(gè)最大的好處：容易寫(xiě)代碼。因?yàn)槲覀兛梢杂幸庾寯?shù)據(jù)把樹(shù)“排得滿(mǎn)滿(mǎn)的”，滿(mǎn)到它是一行一行挨著排下來(lái)的。這叫做“完全二叉樹(shù)”。我們可以給完全二叉樹(shù)編個(gè)號(hào)，從上到下從左到右挨著數(shù)下來(lái)。根是1，找左兒子就乘2，找右兒子就乘2加1，找它爸就 div 2。以后叫誰(shuí)就是誰(shuí)，很方便。這樣整個(gè)樹(shù)就可以用一個(gè)數(shù)組實(shí)現(xiàn)了。由于堆基本上只用來(lái)找最小，因此如果某個(gè)問(wèn)題要求很復(fù)雜的話(huà)，最好還是用成二叉查找樹(shù)；當(dāng)然，如果問(wèn)題只要求插入、刪除和找最小三種操作，你應(yīng)該毫不猶豫地選擇堆，畢竟找最小時(shí)堆方便得多，寫(xiě)起又簡(jiǎn)單。什么時(shí)候出現(xiàn)這種問(wèn)題呢？比如說(shuō)，我的女友排起隊(duì)的，我每次要選一個(gè)最純潔的，就是受那些的影響最小的人。每當(dāng)我遇見(jiàn)了一個(gè)新的美女，我就把她放在這個(gè)隊(duì)伍里合適的位置供我以后娛樂(lè)。這時(shí)，我只關(guān)心每次插入、取最小和刪最小。這個(gè)隊(duì)伍就可以用一個(gè)堆來(lái)優(yōu)化。因此，堆還有一個(gè)形象的名字叫優(yōu)先隊(duì)列。如果誰(shuí)問(wèn)題目要求不找最小找最大怎么辦，那人肯定是個(gè)傻子，把堆變通一下，上大下小不就完了嗎？ 研究堆麻煩的地方就是堆的合并。如何把兩個(gè)堆合并成一個(gè)堆？這個(gè)解決了很有用，至少上面的這些操作跟著全部統(tǒng)一了：插入就是與一個(gè)單節(jié)點(diǎn)的堆合并，刪除根就是把根不要了，把根的左右兩邊（顯然還是堆）合并起來(lái)。一個(gè)簡(jiǎn)單的辦法就是遞歸地不斷把根大的堆往根小的堆的右邊合并，把新得到的堆替換原來(lái)的右兒子。注意遞歸過(guò)程中哪個(gè)根大哪個(gè)根小是不停在改變的。這樣下來(lái)的結(jié)果就是典型的“右傾錯(cuò)誤”，而且破壞了完全二叉樹(shù)的完美。為此，我們想要隨時(shí)保證堆的最右邊盡量少。于是，干脆不要完全二叉樹(shù)了，不過(guò)是多寫(xiě)幾行代碼嘛。這個(gè)不存在像二叉查找樹(shù)那樣“某一邊越做越多”的退化問(wèn)題，因?yàn)閷?duì)于一個(gè)堆來(lái)說(shuō)，反正我只管最頂上的東西，下面平不平衡無(wú)所謂，只要不擋我合并的道就行。于是，我們想到人為下一個(gè)能讓堆盡量往左邊斜的規(guī)定。這個(gè)規(guī)定就是，對(duì)于左右兩個(gè)兒子來(lái)說(shuō)，左邊那個(gè)離它下面最近的兩個(gè)兒子不全（有可能一個(gè)都沒(méi)有）的節(jié)點(diǎn)的距離比右邊那個(gè)的遠(yuǎn)。這規(guī)定看著麻煩，其實(shí)還真有效，最右邊的路徑的長(zhǎng)比想像中的變得短得多。這就叫左式堆（左偏樹(shù)）。這下合并倒是方便了，但合并著合并著要不了多少次右邊又多了。解決的辦法就是想辦法隨時(shí)保持左式堆的性質(zhì)。辦法很簡(jiǎn)單，你合并不是遞歸的嗎？每次遞歸一層后再看看左右兩邊兒子離它下面沒(méi)有兩個(gè)兒子的節(jié)點(diǎn)哪個(gè)遠(yuǎn)，如果右邊變遠(yuǎn)了就把左邊右邊調(diào)一下。由于我們已經(jīng)沒(méi)有用數(shù)組實(shí)現(xiàn)這玩意了，因此鏈表搞起很簡(jiǎn)單。這個(gè)對(duì)調(diào)左右的方法給了我們一個(gè)啟發(fā)：哪里還要管什么到?jīng)]有兩個(gè)兒子的節(jié)點(diǎn)的距離嘛，既然我每次都在往右合并，我為什么不每次合并之后都把它對(duì)調(diào)到左邊去呢？這種想法是可行的，事實(shí)上它還有一個(gè)另外的名字，叫斜堆。 二項(xiàng)堆更強(qiáng)，它也是堆，也能合并，不過(guò)它已經(jīng)超越了堆的境界了：它不是一個(gè)堆，而是滿(mǎn)屋子的堆。也就是說(shuō)，找最小值不能再一下子找到了，而是要把二項(xiàng)堆中的每個(gè)堆的頂部都看一下。二項(xiàng)堆的合并也很強(qiáng)，直接把根大的堆放在根小的堆的下面。這意味著二項(xiàng)堆的每個(gè)堆都可能不是二叉樹(shù)了。這增加了編程的難度，不過(guò)可以用一個(gè)叫做“左兒子右兄弟”的技巧來(lái)解決問(wèn)題。這個(gè)技巧，說(shuō)穿了就是仍然用二叉樹(shù)來(lái)表示多叉樹(shù)：把樹(shù)畫(huà)好，然后規(guī)定節(jié)點(diǎn)的左兒子是下一層的最左邊那個(gè)，右兒子就是它右邊那個(gè)。就是說(shuō)，左兒子才是真正的兒子，右兒子不過(guò)是一起生出來(lái)的。為了讓二項(xiàng)堆好看些，讓堆的個(gè)數(shù)和大小保持在一個(gè)能快速操作的數(shù)目和比例內(nèi)，二項(xiàng)堆作出了一個(gè)明智的規(guī)定：每個(gè)堆的大�。ǹ偟墓�(jié)點(diǎn)個(gè)數(shù)）只能是1、2、4、8、16…中的一個(gè)，且每種大小的堆只能有一個(gè)。若干個(gè)互不相同的2的冪足以表示任意一個(gè)正整數(shù)，因此這個(gè)規(guī)定可以保證不管多大的二項(xiàng)堆都能表示出來(lái)。保持這個(gè)性質(zhì)很簡(jiǎn)單，遇到兩個(gè)大小相等的堆就合并起來(lái)成為一個(gè)大一號(hào)的堆。由于總是兩個(gè)大小相等的堆在合并，因此二項(xiàng)堆中的每一個(gè)堆都有一個(gè)奇妙的樣子，看看本文結(jié)束后下面附的一個(gè)大小為16的堆的示意圖，再看一下，再看一下，你就能體會(huì)到了。圖下面有一個(gè)用“左兒子右兄弟”法表示的同樣的樹(shù)，其中，往下走的線(xiàn)是左兒子，往右走的線(xiàn)是右兒子。 最后簡(jiǎn)單說(shuō)一下Fibonacci堆。保持一個(gè)跟著變的數(shù)組記錄現(xiàn)在某個(gè)節(jié)點(diǎn)在堆中的位置，我們還是可以對(duì)堆里的數(shù)據(jù)進(jìn)行一些操作的，至少像刪除、改變數(shù)值等操作是完全可以的。但這個(gè)也需要耗費(fèi)一些時(shí)間。Fibonacci堆相當(dāng)開(kāi)放，比二項(xiàng)堆更開(kāi)放，它可以不花任何時(shí)間減少（只能是減少）某個(gè)節(jié)點(diǎn)的值。它是這樣想的：你二項(xiàng)堆都可以養(yǎng)一屋子的堆，我為什么不行呢？于是，它懶得把減小了的節(jié)點(diǎn)一點(diǎn)一點(diǎn)地浮上去，而是直接就把它作為根拿出來(lái)當(dāng)成一個(gè)新的堆。每次我要查最小值時(shí)我就再像二項(xiàng)堆一樣（但不要求堆的大小了）一個(gè)個(gè)合并起來(lái)還原成一個(gè)堆。當(dāng)然，這樣的做法是有適用范圍的，就是前面說(shuō)的數(shù)值只能是減少。在什么時(shí)候需要一個(gè)數(shù)值只減少不增加的堆結(jié)構(gòu)呢？莫過(guò)于Dijkstra一類(lèi)的圖論算法了。所以說(shuō)，這些圖論算法用Fibonacci堆優(yōu)化可以進(jìn)一步提速。 |
2樓2010-02-12 22:02:42
formleaf
木蟲(chóng) (正式寫(xiě)手)
- 應(yīng)助: 0 (幼兒園)
- 貴賓: 1.097
- 金幣: 3383.1
- 散金: 2780
- 紅花: 3
- 帖子: 991
- 在線(xiàn): 69.6小時(shí)
- 蟲(chóng)號(hào): 698652
- 注冊(cè): 2009-02-09
- 性別: GG
- 專(zhuān)業(yè): 組合數(shù)學(xué)
《數(shù)據(jù)結(jié)構(gòu)與算法分析》5000字縮寫(xiě)(下)
★
haixing2008(金幣+1): 2010-02-13 09:39
haixing2008(金幣+1): 2010-02-13 09:39
|
http://www.matrix67.com/blog/archives/92 有一個(gè)女人的男人很幸福。事實(shí)上，這是片面的。應(yīng)該說(shuō)，有不止一個(gè)女人的男人更幸福。但是，這樣會(huì)壞了我的人品，而且被女的知道了也不好。兩個(gè)耍得好的女人話(huà)很多，秘密在女人中傳得很快。于是，我打算不同時(shí)和兩個(gè)耍得好的女的耍朋友。后來(lái)我意識(shí)到，這樣也不行。女人太無(wú)敵了，即使A與B耍得好，B與C耍得好，A和C的消息也是互通的。哪怕只有一個(gè)朋友關(guān)系也能把兩群人聯(lián)系在一起。我不得不改變策略，使得我的女朋友之間沒(méi)有任何渠道傳遞信息。也就是說(shuō)，在上面的A、B、C三個(gè)人中，雖然A和C沒(méi)有直接的聯(lián)系，但我也不能同時(shí)和A、C耍。不久后，我想知道，某兩個(gè)女人是否可以通過(guò)某條“朋友鏈”傳遞信息。這就是所謂的等價(jià)關(guān)系——基本上算是判斷一個(gè)無(wú)向圖的連通性。就像很多個(gè)集合，每次選兩個(gè)并成一個(gè)，而且我們隨時(shí)想知道某兩個(gè)元素經(jīng)過(guò)前面的合并后是否在同一個(gè)集合內(nèi)。怎么辦呢？后來(lái)有一天，我發(fā)現(xiàn)那些小女生喜歡玩些認(rèn)親戚的游戲，什么誰(shuí)是誰(shuí)媽?zhuān)l(shuí)是誰(shuí)姐，誰(shuí)是誰(shuí)女兒之類(lèi)的（不知道為什么這些瘋女人喜歡搞這些）。我突然恍然大悟，我的問(wèn)題可以用樹(shù)結(jié)構(gòu)來(lái)完成。親戚的親戚還是親戚，但有一點(diǎn)總相同：所有親戚的始祖總是一樣的。始祖一樣的都是一伙的。因此，把兩個(gè)集合并在一起，只要讓其中一個(gè)集合的根成為另一個(gè)集合中的某個(gè)元素的一個(gè)兒子就行了，這種家譜關(guān)系的改變將使前面的集合中所有的元素?fù)碛泻秃竺婺莻�(gè)集合一樣的鼻祖，而這將成為這些元素的“標(biāo)志”。這個(gè)想法的靈感是來(lái)自女人世界的，因此女人還是有一定的作用。 這就叫并查集，又叫不相交集。它可以合并兩個(gè)集合并且查詢(xún)兩個(gè)元素是否在同一集合。我們有一個(gè)很有效的剪枝：遞歸時(shí)順便把路上經(jīng)過(guò)的祖祖輩輩全部變成根的兒子。這樣的程序只用2行來(lái)解決。 function find_set(x:integer):integer; begin if x<>p[x] then p[x]:=find_set(p[x]); exit(p[x]); end; p[x]表示元素x的父親的位置。一開(kāi)始，p[x]都等于x自己，表示自己一個(gè)人是一個(gè)集合。函數(shù)find_set(x)將返回x所在集合（一棵樹(shù)）的根。 并查集還有些其它的剪枝和一些很復(fù)雜的效率分析問(wèn)題，這里不多說(shuō)了。 寫(xiě)到這里，《數(shù)據(jù)結(jié)構(gòu)與算法分析》中的幾個(gè)大塊內(nèi)容算是說(shuō)清楚了。由于本文的敘述調(diào)整了原書(shū)各章節(jié)的順序且至此還沒(méi)有涉及書(shū)里的一些小問(wèn)題，因此這里想把遺漏下的一些小東西提一下。 有一些樹(shù)結(jié)構(gòu)可能要求同時(shí)滿(mǎn)足多個(gè)要求。比如一個(gè)簡(jiǎn)單的問(wèn)題：如果要求構(gòu)造一個(gè)堆使得既能查找最小元素又能查找最大元素怎么辦？這時(shí)，我們可以用一個(gè)特殊的方法來(lái)實(shí)現(xiàn)：樹(shù)的單數(shù)層滿(mǎn)足一種性質(zhì)，樹(shù)的雙數(shù)層滿(mǎn)足另一種性質(zhì)。我們用一個(gè)叫做最小-最大堆的東西來(lái)實(shí)現(xiàn)前面說(shuō)的問(wèn)題。這個(gè)堆的雙數(shù)層的數(shù)據(jù)小于它爸大于它爸的爸，單數(shù)層的數(shù)據(jù)反過(guò)來(lái)，大于它爸小于它爸的爸。用類(lèi)似的方法，我們還可以設(shè)計(jì)一個(gè)二叉查找樹(shù)，使得它能夠支持含有2種不同類(lèi)型元素的數(shù)據(jù)。在單數(shù)層按其中一種操作，在雙數(shù)層按另一種操作，這樣可以方便的查找同時(shí)位于兩個(gè)不同類(lèi)元素的指定區(qū)間內(nèi)的數(shù)據(jù)。這種二叉查找樹(shù)叫做2-d樹(shù)。擴(kuò)展2-d 樹(shù)，我們可以得到k-d樹(shù)。這些數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)方法這里不說(shuō)了，書(shū)上本來(lái)也是作為一個(gè)習(xí)題介紹的。 書(shū)里的第7章花了近50頁(yè)介紹并分析各種排序算法，分析得很全。其中第11節(jié)花了10頁(yè)介紹外部排序。所謂外部排序，就是說(shuō)怎樣快速地把一個(gè)根本無(wú)法全部讀入內(nèi)存的大文件進(jìn)行排序。很多排序之所以可行是因?yàn)樗鼈兛梢噪S意讀寫(xiě)任意一個(gè)指定的數(shù)。但在大文件里，我們無(wú)法實(shí)現(xiàn)“第1234567890個(gè)元素和第 123個(gè)元素交換位置”，更無(wú)法實(shí)現(xiàn)遞歸之類(lèi)的操作，而只能像磁帶一樣“過(guò)一遍”，從頭到尾掃一遍，由于文件太大內(nèi)存不能接受，因此必須要讀一截扔一截。于是，外部排序產(chǎn)生了。不要以為這個(gè)限制會(huì)把排序速度拖得很慢。事實(shí)上，外部排序同樣突破了O(n^2)的界限。它借助了歸并排序中的“合并兩個(gè)已經(jīng)有序的數(shù)組”的思想，因?yàn)檫@個(gè)操作可以邊讀就邊做。把文件先拆成兩個(gè)文件，再把每個(gè)文件處理成一段一段的等長(zhǎng)有序序列（一段多大取決于內(nèi)存能一次處理多大），然后不斷從兩個(gè)文件中各取一段出來(lái)合并�？梢钥吹�，每段有序序列的長(zhǎng)度變長(zhǎng)了，變成了2倍長(zhǎng)。過(guò)不了幾次，這個(gè)長(zhǎng)度將變成文件的總長(zhǎng)。注意，我們必須要讓每次合并時(shí)為下次合并做好準(zhǔn)備（就是說(shuō)合并后的結(jié)果仍然要是兩個(gè)分了段的文件）。一個(gè)好的方法是將合并的結(jié)果交替存在兩個(gè)不同的新文件中。 第9章講圖論算法。講了圖的遍歷（廣搜和深搜）、AOV、AOE、Dijkstra、網(wǎng)絡(luò)流、Prim、Kruskal和NP問(wèn)題。在講深搜時(shí)，我學(xué)到了兩個(gè)新東西，用線(xiàn)性時(shí)間查找割點(diǎn)（去掉了的話(huà)圖就不連通了的點(diǎn)）和強(qiáng)分支（有向圖中的一個(gè)分支滿(mǎn)足其中任兩個(gè)點(diǎn)之間都可以互相到達(dá)）。后來(lái)發(fā)現(xiàn)黑書(shū)上也有，又覺(jué)得這個(gè)東西很不好說(shuō)，因此這里不想說(shuō)了。說(shuō)到了黑書(shū)還想順便補(bǔ)一句：黑書(shū)真的看不得——太多錯(cuò)誤了。不是說(shuō)LRJ怎么了，LRJ在真正的大問(wèn)題上有他的思想和經(jīng)驗(yàn)，但很多細(xì)節(jié)的概念他也是昏的，這不利于初學(xué)者接受知識(shí)。不信哪天我還要寫(xiě)一篇日志糾正黑書(shū)的錯(cuò)誤。引用政治書(shū)上抨擊“人性自私論”的經(jīng)典語(yǔ)言：“從理論到實(shí)踐都是錯(cuò)的”。 第10章講“算法設(shè)計(jì)技巧”，大概是些貪心啊，分治啊，動(dòng)規(guī)啊，回溯啊，隨機(jī)化啊之類(lèi)的。調(diào)度問(wèn)題、Huffman樹(shù)、裝箱問(wèn)題近似算法、最近點(diǎn)距分治算法、最優(yōu)二叉查找樹(shù)、Floyd-Warshall、跳躍表、Miller-Rabin素性測(cè)試、博弈算法等都在這章中有講，并且講得相當(dāng)好。由于這不是本書(shū)的重點(diǎn)內(nèi)容，這里也不說(shuō)了。 第11章整章都在講攤還分析。這是一個(gè)相當(dāng)復(fù)雜的問(wèn)題，是分析時(shí)間復(fù)雜度的一個(gè)有力工具。它的分析告訴我們的不是某一個(gè)操作的復(fù)雜度，而是重復(fù)執(zhí)行某一個(gè)操作的平均復(fù)雜度。研究這個(gè)是很有必要的，因?yàn)槲覀儠?huì)遇到一些“越變?cè)铰钡耐嘶樾魏汀白晕冶３植蛔儭钡淖哉{(diào)整性等數(shù)據(jù)結(jié)構(gòu)，單個(gè)操作并不能反映它真正的效率。 到這里，這本書(shū)的所有東西都已經(jīng)介紹完了�？偟膩�(lái)說(shuō)，這本書(shū)很值得一看（雖然有些地方翻譯得很差）。它的理論性很強(qiáng)，證明過(guò)程完整（再?gòu)?fù)雜的分析它也證明得很清楚，滿(mǎn)足那些刨根問(wèn)底的人）；整本書(shū)自成一個(gè)體系，前后呼應(yīng)；習(xí)題具有研究性，與課文互相補(bǔ)充。事實(shí)上，這些都是國(guó)外教材共有的特點(diǎn)。這算是我完整讀過(guò)的第一本國(guó)外教材，今后我還會(huì)讀一些。這幾天在看《組合數(shù)學(xué)》（仍然是這個(gè)出版社出版的），看完后也打算寫(xiě)一下“對(duì)《組合數(shù)學(xué)》一書(shū)中部分內(nèi)容的形象理解”。讀一本國(guó)外教材，你會(huì)發(fā)現(xiàn)它與國(guó)內(nèi)書(shū)籍的不同并會(huì)從中獲益更多。 這篇文章就寫(xiě)到這里了。號(hào)稱(chēng)是一個(gè)5000字縮寫(xiě)，沒(méi)想到寫(xiě)著寫(xiě)著已經(jīng)超過(guò)8000字了。而且，這個(gè)并不是縮寫(xiě)，而是一些簡(jiǎn)單的、系統(tǒng)的、清晰的、形象化的思想和理解。這篇文章或許對(duì)已經(jīng)知道一些有關(guān)知識(shí)的人有用，但不適合一點(diǎn)也沒(méi)有接觸過(guò)數(shù)據(jù)結(jié)構(gòu)與算法分析的人。如果有一個(gè)人能從中收獲一件東西，我寫(xiě)這個(gè)的目的也就達(dá)到了。 （完） |
3樓2010-02-12 22:04:49
|
本帖內(nèi)容被屏蔽 |
4樓2010-02-13 21:36:13
bestsing
捐助貴賓 (著名寫(xiě)手)
- 應(yīng)助: 1 (幼兒園)
- 金幣: 2402.2
- 散金: 2096
- 紅花: 5
- 帖子: 2059
- 在線(xiàn): 115.2小時(shí)
- 蟲(chóng)號(hào): 88342
- 注冊(cè): 2005-08-23
- 性別: GG
- 專(zhuān)業(yè): 計(jì)算機(jī)軟件
5樓2010-02-14 08:45:00
洛陽(yáng)神龜
銀蟲(chóng) (正式寫(xiě)手)
- 應(yīng)助: 6 (幼兒園)
- 金幣: 264.2
- 散金: 250
- 紅花: 2
- 帖子: 317
- 在線(xiàn): 41.1小時(shí)
- 蟲(chóng)號(hào): 908049
- 注冊(cè): 2009-11-20
- 性別: GG
- 專(zhuān)業(yè): 地理信息系統(tǒng)
6樓2010-06-07 23:33:41
shenhanyou
銅蟲(chóng) (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 171.3
- 帖子: 21
- 在線(xiàn): 1.3小時(shí)
- 蟲(chóng)號(hào): 308270
- 注冊(cè): 2006-12-17
- 專(zhuān)業(yè): 信號(hào)理論與信號(hào)處理
7樓2010-11-23 13:41:59
jnow
木蟲(chóng) (正式寫(xiě)手)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 1865.5
- 散金: 782
- 紅花: 9
- 帖子: 722
- 在線(xiàn): 237.8小時(shí)
- 蟲(chóng)號(hào): 239839
- 注冊(cè): 2006-04-07
- 專(zhuān)業(yè): 自然語(yǔ)言理解與機(jī)器翻譯
8樓2011-09-24 15:49:37
wlp816
金蟲(chóng) (正式寫(xiě)手)
- 應(yīng)助: 4 (幼兒園)
- 金幣: 3632.2
- 散金: 17
- 紅花: 2
- 帖子: 320
- 在線(xiàn): 573.5小時(shí)
- 蟲(chóng)號(hào): 1143121
- 注冊(cè): 2010-11-10
- 性別: GG
- 專(zhuān)業(yè): 控制理論與方法
9樓2011-10-03 12:11:55
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 formleaf 的主題更新
| 9 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 336求調(diào)劑 +4 | 收到VS 2026-03-20 | 4/200 |
|
|---|---|---|---|---|
|
[考研] 一志愿上海交大生物與醫(yī)藥專(zhuān)碩324分，求調(diào)劑 +5 | jiajunX 2026-03-22 | 5/250 |
|
|
|
[論文投稿] 急發(fā)核心期刊論文 +3 | 賢達(dá)問(wèn)津 2026-03-23 | 5/250 |
|
|
|
[考研]
求調(diào)劑材料學(xué)碩080500，總分289分
 5+3
|
@taotao 2026-03-19 | 21/1050 |
|
|
|
[考研] 284求調(diào)劑 +6 | Zhao anqi 2026-03-22 | 6/300 |
|
|
|
[考研] 323求調(diào)劑 +6 | 洼小桶 2026-03-18 | 6/300 |
|
|
|
[考研] 尋找調(diào)劑 +4 | 倔強(qiáng)芒? 2026-03-21 | 4/200 |
|
|
|
[考研] 求調(diào)劑院校信息 +6 | CX 330 2026-03-21 | 6/300 |
|
|
|
[考研] 286分人工智能專(zhuān)業(yè)請(qǐng)求調(diào)劑愿意跨考！ +4 | lemonzzn 2026-03-17 | 8/400 |
|
|
|
[考研] 初試 317 +7 | 半拉月丙 2026-03-20 | 7/350 |
|
|
|
[考研] 0703化學(xué)調(diào)劑 +4 | 妮妮ninicgb 2026-03-21 | 4/200 |
|
|
|
[考研] 0805材料320求調(diào)劑 +3 | 深海物語(yǔ) 2026-03-20 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +3 | 白QF 2026-03-21 | 3/150 |
|
|
|
[考研] 332求調(diào)劑 +3 | 鳳凰院丁真 2026-03-20 | 3/150 |
|
|
|
[考研] 二本跨考鄭大材料306英一數(shù)二 +3 | z1z2z3879 2026-03-17 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +3 | Ma_xt 2026-03-17 | 3/150 |
|
|
|
[考研] 材料專(zhuān)業(yè)求調(diào)劑 +6 | hanamiko 2026-03-18 | 6/300 |
|
|
|
[考研] 一志愿蘇州大學(xué)材料求調(diào)劑，總分315（英一） +5 | sbdksD 2026-03-19 | 5/250 |
|
|
|
[考研] A區(qū)線(xiàn)材料學(xué)調(diào)劑 +5 | 周周無(wú)極 2026-03-20 | 5/250 |
|
|
|
[考研] 一志愿 南京航空航天大學(xué)大學(xué) ，080500材料科學(xué)與工程學(xué)碩 +5 | @taotao 2026-03-20 | 5/250 |
|