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