算法之道(第2版)

前言

前言：起初神創(chuàng)造天地。地是空虛混沌，淵面黑暗；神的靈運行在水面上。神說："要有光?！本陀辛斯?。神看光是好的，就把光與暗分開了。神稱光為晝，暗為夜。有晚上，有早晨，這是頭一日。……神就照著自己的形象造人?！裾f："看啊！我將遍地上一切結種子的菜蔬和一切樹上所結有核的果子，全賜給你們做食物。至于地上的走獸和空中的飛鳥，以及各樣在地上爬的有生命的物，我將青草賜給它們做食物。"事就這樣成了。神看著一切所造的都甚好。有晚上，有早晨，是第六日。天地萬物都造齊了。6天圣經上寫著：神6天創(chuàng)造天地萬有，第7日安歇。對于神創(chuàng)論者來說，這是不可懷疑的事實。但對于進化論者來說，6天創(chuàng)造一切根本就不可能。作為一本算法書，我們當然不打算加入神創(chuàng)論和進化論者的永無休止的爭論當中去。我們關心的是這么一個問題：圣經上為什么給出的是6天，而不是其他的時間長度。不管是神創(chuàng)論者還是進化論者，弄清楚6這個數(shù)字的來歷很可能會對己方的觀點有所幫助。在這6天里，神將他的創(chuàng)作方程式重復了6次，每天1次。對于全能的神來說，他完全可以在1天、1秒或者任何他所愿意的時間長度里創(chuàng)造天地萬物，但卻為什么是不多不少的6天呢？而不管圣經上的“1天”是多長，這個問題都是值得討論的。我們知道，任何一個自然數(shù)的約數(shù)中都有1和它本身，而所有小于它本身的因數(shù)叫做這個自然數(shù)的真約數(shù)。例如，6的所有真約數(shù)是1、2、3；數(shù)字8的真約數(shù)是1、2、4。如果一個數(shù)的真約數(shù)之和等于這個自然數(shù)本身，則這個自然數(shù)就稱為完全數(shù)，或者完美數(shù)。例如，6=1＋2＋3，因此6是完美數(shù)；而8(1+2+4，因此8不是完美數(shù)。因此，神6天創(chuàng)造世界，暗示著該創(chuàng)造是完美的！以完美數(shù)來昭示創(chuàng)造的完美，似乎合情合理。但問題是，完美數(shù)只有6這一個數(shù)嗎？如果不是，為什么不使用其他的完美數(shù)呢？答案是，完美數(shù)雖然不只有6這一個，但確實數(shù)量稀少。一直到現(xiàn)在(2009年6月)，數(shù)學家們探索了2600年，并且現(xiàn)代數(shù)學家們還借助了超級計算機的幫助，但也僅僅找到了47個完美數(shù)。其中第1個完美數(shù)是6，接下來的4個完美數(shù)分別是：28、496、8128、33550336。而第47個完美數(shù)有25956377個數(shù)位(注意，是數(shù)位，不是數(shù)值)，它的數(shù)值為：243112608×(243112609?1)。完美數(shù)的稀少昭示著達到完美的難度，而神選擇6天來創(chuàng)造天地萬有也許是因為6是最小的完美數(shù)，即創(chuàng)造天地萬有對于神來說是輕而易舉的一件事情……完美與算法完美數(shù)由于其各種神秘屬性(真約數(shù)之和等于自身只是其中的一種性質)而受到了特殊的關注。但到底哪些數(shù)是完美數(shù)則不是一件容易判斷的事情。顯然，按照完美數(shù)的定義，判斷一個數(shù)是否是完美數(shù)的不二法則是找出它的所有真約數(shù)，然后求和看看其是否等于自身。而這種方法效率太過低下，因為這意味著因式分解，而這是十分困難的(本書后面將會討論到這個問題)。如果判斷一個數(shù)是否是完美數(shù)就已經非常困難，那么要找出所有的完美數(shù)則更是一個難上加難的任務。因為這就意味著將所有的數(shù)進行上面描述的判斷驗證：因式分解。這似乎是人類不可能完成的任務。即使用世界上超快的計算機來進行計算，情況也不會有任何數(shù)量級的改善。顯然，我們需要新的解決方案，而不是發(fā)明或使用新的計算工具！研究這樣的解決方案就可以歸結到算法的范疇里，因為如何高效地解決問題正是算法要研究的核心課題。有意思的是，判斷和搜索完美數(shù)是算法的研究范疇，而算法本身的追求卻也是“完美”。算法無處不在如果你覺得算法只是用來研究解決找出完美數(shù)之類的“漫無邊際的問題”，那就大錯特錯了。也許算法這個名詞聽上去很抽象，讓人聯(lián)想不到任何具體的物體。也許你會覺得算法與自己的生活并無太多關系，它只不過存在于那些閑得無聊的數(shù)學家或計算機專業(yè)人士的腦海中。但事實真是這樣嗎？當然不是。如果我們告訴你算法就是解決各種問題的方法，你就不會覺得它太抽象，與生活無關了吧。事實是，算法無處不在。每個人每天都在使用不同的算法來活出自己的人生，比如你去食堂買飯會選擇一個較短的隊列，而有人則可能選擇一個推進速度更快的隊列。每天起床后，你可能先讀一會兒書，再去吃早飯；另外一個人則可能先去吃早飯，然后再看書。所有這些行為都是算法或算法一部分的體現(xiàn)。也許運行這些算法并不在你的思想意識里，也許你并不知道算法在幫助自己的生活，但它確實存在。這些算法也許沒有經過精心設計，沒有經過仔細分析，但它還是算法！2009年7月23日下午，我在游覽云南省大理市的蝴蝶泉時由于泉水邊的石頭很滑，在用泉水洗手時(導游金花說用該泉水洗手會帶來好運)不慎滑落到蝴蝶泉水(見圖3)里面全身濕透。(據說一天至多只會有一個人滑落到泉里，可見我的運氣不錯！看來“蝴蝶泉邊好梳妝”的歌詞也許應該改為“蝴蝶泉里好沖涼”。)泉水冰冷透涼，而大理的氣溫又低。這樣，我就面臨一個是否更換全身衣服的選擇。問題是，旅游團需要馬上趕去登游船游覽洱海風光，而若找地方或者回旅店換衣服就將趕不上游船。如何處理這件事情就是一個算法問題：是先上游船再在船上找地方換衣服，還是找個地方換衣服而放棄游覽蒼山洱海。顯然不同的算法有著不同的收益和代價。如果能夠在游船上找到合適的地方更換衣服，則采用先上游船再換衣服的算法為佳；否則就是放棄游覽的算法更好，因為如果凍病了顯然就不劃算了。最后，我選擇了在游船上更換衣服的算法：在游船上找到了一個貴賓室更衣。算法由問題驅動算法的發(fā)現(xiàn)總是由相關的問題驅動的。拿排序來說，因為生活中到處都充滿次序，每個人都要接受自己在某個次序里的位置。比如，各種排名、評優(yōu)、民意調查等，最后的結果都體現(xiàn)為一個次序！看來，“沒有次序無以成方圓”并不是空穴來風！而談到排序用的方法，人們很自然地想到了插入法。因為這種樸素的算法和人的思維方式非常類似：它就是人們打牌時整理手中撲克牌的算法。但是隨著數(shù)據量的增多，插入排序的效率缺陷迅速變?yōu)槿藗儫o法容忍的缺點。于是人們發(fā)明了歸并排序、堆排序、快速排序等，這些排序的方法大大改善了速度，但是人們卻并不滿足于此，因此又發(fā)明了效率更高的線性排序。表1給出的是各種排序算法平均情況下的效率比較：最上面一行的數(shù)字代表輸入的規(guī)模，如10表示一共有10個數(shù)據項，1M表示一共有100萬個數(shù)據項。其他格子里面的數(shù)據為相應算法在相應輸入規(guī)模下完成排序所需要的時間，單位為毫秒。所有輸入數(shù)據為隨機產生。一個個新的算法都是為了解決前面算法遺留的問題而產生的。從表1里的數(shù)字可以看出，一般來說，隨著新的算法出現(xiàn)，排序效率在不斷提高。不過，雖然每個算法似乎解決了前面算法的遺留問題，但新的問題也會被有意或無意地引入。例如，線性排序雖然將排序的時間復雜性降低到線性級，但各種前提條件極大地限制了其應用范圍。也許這就是算法永遠也不能或不會停止發(fā)展的一個原因吧。算法是計算機的靈魂因為人不是全能的，一個時刻只能做一件事情，所以做事情就要有一個步驟。由于算法要滿足人的這種特性，因此它通常表示為一個做事情的行為序列。因此，從一般意義上說，算法就是求解問題的步驟。由于計算機的計算操作完全是一步一步進行，因此算法的上述性質用于計算機是再合適不過了，可以說算法彌漫在計算機的一切行為上。如果說操作系統(tǒng)是計算機的心智，那么算法就是計算機的靈魂。理解靈魂當然不是一件容易的事情，由于它高度抽象與簡潔，許多學生都望而卻步。先看一個紙牌魔術：1)任選一位觀眾將一副撲克牌充分洗好。2)背對觀眾，請觀眾隨機抽出一張牌，記住牌面，然后將這張牌放回整副牌的最上面。3)接過牌后，洗牌幾次。洗牌的時候保持最上面一張牌不動。4)對觀眾說：“我來教你魔法，只要吹一口氣，就能把剛才你抽的牌吹到任意位置上”。5)請觀眾說出一個數(shù)字，比如說10，然后一邊吹氣，一邊想著剛才說的數(shù)字10。6)在吹完氣后，請觀眾一張一張地將上面的牌取出放在桌上。7)到第10張時，將牌翻開，發(fā)現(xiàn)并不是其原來抽的牌。8)接回整副牌，并把上一個步驟里取出堆放在桌上的牌收起，仍放在整副牌的最上面。9)然后洗牌幾次，洗牌的時候保持上面放回來的那堆牌不動。10)從觀眾手上拿回剛才翻開的那張牌，插入最上面9個位置中的任意一個。11)對觀眾說：“你剛才不是在想著那個數(shù)字的時候吹的氣，而是在吹氣的時候想著那個數(shù)字，而這是完全不同的兩回事。我現(xiàn)在演示如何吹氣?！睂χ拼狄豢跉?。12)請觀眾從上到下數(shù)牌，到第10張時翻開。13)這張翻開的牌就是觀眾一開始抽的那張牌。讀者看明白了上面的這個魔術了嗎？這里面隱藏著一個算法。如果看懂了就可以在朋友面前一顯身手了。當然，如果沒有看懂也沒有什么關系。算法本來就不是輕易讓人看懂的嘛。如果這些問題讀者都能回答，那么恭喜你?？磥硭惴ǚ治鰧τ谧x者來說將是件很容易的事情，不過可能也不一定。如果你回答不出這些問題，不用擔心，因為回答諸如此類的問題就是本書的目的。當然了，本書回答的遠不止這么幾個簡單問題，而是會闡述更重要的算法精髓：算法思想、戰(zhàn)略和分析！

內容概要

　　本書追求的目標是算法背后的邏輯，是一本啟示書，而不是一本包羅萬象的算法大全。因此，本書甄選了那些最能展現(xiàn)算法思想、戰(zhàn)略和精華，并能夠有效訓練算法思維的內容。本書將算法的討論分為五篇：算法基礎篇、算法設計篇、算法分析篇、經典算法篇、難解與無解篇。每篇分別討論算法的一個方面：基礎、設計、分析、經典和難解問題。第2版還對進程調度問題、跳轉表問題、概率分析應用、遺傳算法等方面進行了論述。
　　本書既可以作為大學本科或研究生的算法教材或參考書，也可以作為對算法有興趣的讀者提升認知深度的讀物。

作者簡介

　　鄒恒明，美國密歇根大學（University of Michigan-Ann
Arbor）計算機科學與工程博士、中國科學院計算技術研究所碩士、華中科技大學計算機科學與技術學士。曾先后在美國IBM、美國國家數(shù)據公司、美國朗訊和美國EMC公司任職8年多。現(xiàn)為上海交通大學教授。

書籍目錄

前言
第一篇　算法基礎篇
　第1章　從無有到無窮
　　1.1　意念與現(xiàn)實
　　1.2　什么是算法
　　1.3　算法的表示
　　1.4　算法之魂
　　1.5　如何比較速度
　　1.6　算法與計算機的關系
　　1.7　算法的范疇
　　1.8　為什么學習算法
　　思考題
　第2章　計數(shù)與漸近
　　2.1　算法的分析
　　　2.1.1　正確性分析
　　　2.1.2　時空效率分析
　　　2.1.3　時空特性分析
　　2.2　計數(shù)：算法分析的核心
　　2.3　算法設計
　　2.4　算法效率表示
　　2.5　漸近分析
　　2.6　表示
　　2.7　最好、最壞、平均
　　2.8　另一類定義
　　2.9　性質
　　2.10　要更快的計算機還是要更快的算法
　　思考題
　第3章　分治與遞歸
　　3.1　分而治之為上策
　　3.2　分治策略
　　3.3　遞歸表達式求解
　　　3.3.1　遞歸樹法
　　　3.3.2　替換解法
　　　3.3.3　大師解法
　　3.4　分治策略舉例1：乘方運算
　　3.5　生命中不能承受之重：矩陣乘法
　　3.6　魔鬼序列：斐波那契序列
　　　3.6.1　由底至上
　　　3.6.2　使用通式
　　　3.6.3　使用矩陣乘方
　　3.7　VLSI 布線
　　3.8　多項式乘法
　　3.9　分治就在潛意識
　　思考題
第二篇　算法設計篇
　第4章　動態(tài)規(guī)劃思想
　　4.1　什么是動態(tài)規(guī)劃
　　4.2　流水線問題
　　4.3　最長公共子序列
　　　4.3.1　第一種解法：蠻力策略
　　　4.3.2　第二種解法：動態(tài)規(guī)劃
　　4.4　最長公共子序列變種
　　4.5　記憶遞歸法
　　4.6　空間效率改善
　　4.7　最優(yōu)二叉搜索樹
　　　4.7.1　遞歸解法
　　　4.7.2　計算最優(yōu)答案
　　4.8　最優(yōu)子結構與重疊子問題
　　　4.8.1　最優(yōu)子結構
　　　4.8.2　重疊子問題
　　4.9　動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關系
　　4.10　動態(tài)規(guī)劃與靜態(tài)規(guī)劃的相互轉換
　　思考題
　第5章　貪婪選擇思想
　　5.1　僅有動態(tài)規(guī)劃是不夠的
　　5.2　什么是貪婪
　　5.3　背包問題
　　5.4　貪婪選擇屬性
　　5.5　教室規(guī)劃問題
　　5.6　最小生成樹
　　　5.6.1　Kruskal算法的正確性
　　　5.6.2　Kruskal算法的時間分析
　　5.7　Prim算法
　　5.8　霍夫曼樹和霍夫曼編碼
　　　5.8.1　霍夫曼樹
　　　5.8.2　霍夫曼編碼
　　　5.8.3　霍夫曼編碼的無前綴編碼性質
　　5.9　進程調度問題
　　5.10　貪婪選擇屬性
　　5.11　標準分治、動態(tài)規(guī)劃和貪婪選擇的比較
　　思考題
　第6章　隨機化思想
　　6.1　為什么要隨機化
　　6.2　隨機的平方
　　6.3　什么是隨機化算法
　　6.4　拉斯維加斯算法
　　6.5　蒙特卡羅算法
　　6.6　素性測試
　　6.7　矩陣乘積驗證器
　　6.8　隨機化最小生成樹算法
　　　6.8.1　Karger-Klein-Tarjan算法
　　　6.8.2　結點降低算法
　　　6.8.3　線性時間最小生成樹算法
　　　6.8.4　線性時間最小生成樹算法的時間成本分析
　　6.9　隨機數(shù)的生成
　　6.10　隨機化算法的應用
　　思考題
第三篇　算法分析篇
　第7章　概率分析
　　7.1　一切都在概率中
　　7.2　什么是概率分析
　　7.3　夢幻情人的代價
　　　7.3.1　直接分析
　　　7.3.2　最壞情況分析
　　　7.3.3　最好情況分析
　　　7.3.4　平均情況分析
　　　7.3.5　平均情況下成本的概率分析
　　　7.3.6　概率分析結果的有效性
　　　7.3.7　正確概率分析的保障
　　7.4　夢幻情人的概率
　　7.5　隨機排列問題
　　7.6　跳轉表問題
　　　7.6.1　跳轉表插入操作
　　　7.6.2　隨機化跳轉表構建算法
　　7.7　南柯一夢：從無窮到無有
　　7.8　概率分析的其他應用
　　思考題
　第8章　攤銷分析
　　8.1　什么是攤銷分析
　　8.2　攤銷分析與數(shù)據結構
　　8.3　攤銷分析的幾種方法
　　8.4　聚類分析
　　　8.4.1　棧操作的聚類分析
　　　8.4.2　二進制計數(shù)器的聚類分析
　　8.5　會計分析
　　8.6　勢能分析
　　　8.6.1　棧操作的勢能分析
　　　8.6.2　二進制計數(shù)器的勢能分析
　　8.7　攤銷分析應用：表格擴展的代價
　　　8.7.1　動態(tài)表插入操作的聚類分析
　　　8.7.2　動態(tài)表插入操作的會計分析
　　　8.7.3　動態(tài)表插入操作的勢能分析
　　8.8　運氣不好就攤銷
　　思考題
　第9章　競爭分析
　　9.1　什么是競爭分析
　　9.2　在線算法和離線算法
　　9.3　競爭力
　　9.4　健忘對手和優(yōu)良對手
　　9.5　線性表更新問題
　　9.6　前置移動算法的競爭分析
　　9.7　聚類問題
　　　9.7.1　聚類問題的次優(yōu)解算法
　　　9.7.2　CLUSTERING-ALGORITHM算法的競爭分析
　　9.8　競爭分析與普通算法分析
　　思考題
第四篇　經典算法篇
　第10章　排序與次序
　　10.1　排序無處不在
　　10.2　插入排序
　　　10.2.1　插入排序的效率分析
　　　10.2.2　折半插入排序
　　10.3　歸并排序
　　10.4　快速排序
　　　10.4.1　快速排序的過程
　　　10.4.2　快速排序的時間復雜性分析
　　　10.4.3　最壞情況分析
　　　10.4.4　最好情況分析
　　　10.4.5　平均情況分析
　　10.5　隨機化快速排序
　　10.6　排序的下限
　　10.7　線性排序
　　10.8　計數(shù)排序
　　10.9　基數(shù)排序
　　　10.9.1　基數(shù)排序的正確性
　　　10.9.2　基數(shù)排序的時間效率分析
　　10.10　桶排序
　　　10.10.1　桶排序的定義
　　　10.10.2　桶排序的正確性
　　　10.10.3　桶排序的時間復雜性分析
　　10.11　次序選擇
　　10.12　快速次序選擇算法
　　10.13　隨機快速次序選擇算法
　　10.14　最壞情況下的線性選擇算法
　　　10.14.1　杠桿點好壞分析
　　　10.14.2　算法時間復雜性分析
　　思考題
　第11章　搜索與散列
　　11.1　搜索問題
　　11.2　順序搜索
　　11.3　折半搜索
　　11.4　常數(shù)搜索
　　11.5　散列搜索
　　11.6　散列函數(shù)選擇
　　　11.6.1　直接散列
　　　11.6.2　除法（模除法）散列
　　　11.6.3　乘法散列
　　　11.6.4　乘法散列的賭徒原理
　　　11.6.5　乘方取中法
　　11.7　散列算法的碰撞問題
　　　11.7.1　開放尋址散列
　　　11.7.2　開放尋址散列的時間成本
　　　11.7.3　開放尋址下成功搜索的時間成本
　　　11.7.4　封閉尋址散列
　　　11.7.5　探尋序列的設計
　　　11.7.6　封閉尋址散列的效率分析
　　　11.7.7　搜索不成功的時間成本
　　　11.7.8　成功搜索的效率分析
　　11.8　散列表元素刪除
　　11.9　隨機化散列
　　11.10　全域散列
　　11.11　完美散列
　　思考題
　第12章　最短路徑
　　12.1　劍指羅馬
　　12.2　最短路徑問題
　　12.3　單源單點最短路徑問題
　　　12.3.1　深度優(yōu)先與廣度優(yōu)先搜索
　　　12.3.2　深度優(yōu)先解法
　　12.4　單源多點最短路徑問題
　　　12.4.1　最短路徑的性質
　　　12.4.2　Dijkstra最短路徑算法
　　　12.4.3　Dijkstra算法舉例
　　　12.4.4　Dijkstra算法與洪水泛濫
　　　12.4.5　Dijkstra算法的正確性
　　　12.4.6　Dijkstra算法的時間復雜性
　　12.5　Bellman-Ford算法
　　　12.5.1　負權重的應對方式
　　　12.5.2　Bellman-Ford算法的正確性
　　　12.5.3　負循環(huán)檢查問題
　　　12.5.4　Bellman-Ford算法的時間復雜性
　　12.6　多源多點最短路徑問題
　　　12.6.1　多源多點最短路徑問題解決思路
　　　12.6.2　直接動態(tài)規(guī)劃解法
　　　12.6.3　矩陣乘法解法
　　　12.6.4　Floyd-Warshall算法
　　　12.6.5　Johnson算法
　　　12.6.6　Johnson等效變換
　　　12.6.7　差限問題解決
　　12.7　天意難違
　　思考題
第五篇　難解與無解篇
　第13章　易解與難解
　　13.1　我們戰(zhàn)無不勝嗎
　　13.2　易解與難解
　　13.3　決策問題和優(yōu)化問題
　　13.4　決策問題
　　13.5　P類問題
　　13.6　NP類問題
　　13.7?。ù_定性）圖靈機
　　13.8　非確定性圖靈機
　　13.9　非確定性算法
　　13.10　回到NP類問題
　　13.11　P和NP
　　13.12　搜索問題、決策問題和優(yōu)化問題
　　13.13　有沒有解和是否可決定
　　思考題
　第14章　NP完全問題
　　14.1　玉龍雪山下的審判
　　14.2　NP完全問題的定義
　　14.3　NP完全的重要性
　　14.4　多項式時間規(guī)約
　　14.5　如何證明一個問題S是NP完全問題
　　14.6　第1個NP完全問題的證明
　　14.7　庫克定理
　　14.8　3-SAT問題
　　14.9　證明NP難的技巧
　　14.10　整數(shù)規(guī)劃
　　14.11　獨立集問題
　　14.12　漢密爾頓回路問題
　　14.13　討論：弱NP完全、強NP完全和中NP完全
　　思考題
　第15章　無解與近似
　　15.1　難解問題
　　15.2　不可決定問題
　　15.3　程序終結的判斷
　　15.4　難解之題的求解
　　15.5　智能窮舉、近似算法和本地搜索
　　15.6　智能窮舉之回溯策略
　　15.7　智能窮舉之分支限界
　　15.8　貪婪近似策略
　　15.9　啟發(fā)式搜索策略
　　15.10　模擬退火算法
　　　15.10.1　模擬退火算法的思想
　　　15.10.2　模擬退火算法的基本循環(huán)
　　　15.10.3　退火算法描述
　　15.11　基因／遺傳算法
　　　15.11.1　生物進化與遺傳
　　　15.11.2　遺傳算法的基本要義
　　　15.11.3　遺傳算法的實現(xiàn)
　　　15.11.4　遺傳算法的基本運算過程
　　　15.11.5　遺傳算法的現(xiàn)狀
　　15.12　概率盡在一切中
　　思考題
結語　算法之道
附錄　算法隨想
參考文獻

章節(jié)摘錄

版權頁：第1章 從無有到無窮在第一類弗里德曼宇宙模型中，第四維—時間，正如空間一樣，在范圍上是有限的。它如一根具有兩個端點或邊界的線。因此時間具有終結，而且它也有一個開端。事實上，在宇宙具有我們觀測到的物質總量的情形下，由愛因斯坦方程得出的所有解中，都有一個非常重要的特征：在過去某一時刻(大約137億年以前)相鄰星系之間的距離必須為零。換言之，整個宇宙被擠壓在零尺度的單獨一點，就像一個半徑為零的球。那時，宇宙的密度和時空曲率都為無限大。它是我們稱做大爆炸的時刻。—摘自史蒂文?霍金《時間簡史》這個零尺度的單獨一點被物理學家稱做“原點”。它的另一個名字是奇異點(singularity)。但是零尺度是什么意思呢？霍金曾解釋過：零尺度就是不占空間。那么不占空間是什么意思呢？也許讀者猜出來了：沒有(nothing)！即虛無。實際上，物理學家們普遍認為在原點之外沒有空間，空間也是大爆炸后的產物。也就是說，宇宙是從無到有的，用希臘文來說就是Ex Nihilo(見圖1-1)。圖1-1 Ex Nihilo：宇宙從無到有的一剎那整個宇宙從無到有對一般人來說都很難理解，而這個原點是誰或者如何放在那里也是眾說紛紜。不過，這不是本書準備要討論的問題。本書關心的是算法，而算法具有一個與宇宙起源類似的性質：從無到有。不過這個從無到有卻有著非同一般或者說更加豐富的意義，下面將詳細分析。1.1 意念與現(xiàn)實先看一個例子。給你一個無限容積的罐子和無限個球，球從1開始連續(xù)編號。在差1分鐘到零點時：將標號為1～10的10個球放進罐子，然后將10號球從罐子拿出。在差1/2分鐘到零點時：將標號為11～20的10個球放進罐子，然后將20號球從罐子拿出。在差1/4分鐘到零點時：將標號為21～30的10個球放進罐子，然后將30號球從罐子拿出?！瓦@樣將游戲進行下去。假定放球和取球不占時間，請問，當時鐘指向零點時，罐子里還剩多少個球？這個答案似乎很直接：無限個球！這是因為所有編號不是10n(n≥1)的球在放進去罐子里后就不會再拿出來；而在零點之前這種放球、取球的次數(shù)是無限的。因此，罐子里面的球數(shù)在零點時將是無數(shù)個。但是你很確信這個答案嗎？現(xiàn)在來讓我們改變拿球的方式，將每次拿10、20、30、…號球分別變?yōu)槟?、2、3、…號球，即第x次拿球，所拿出來的球的編號是x。結果又會怎樣呢？這個時候，神奇的事情發(fā)生了。這個罐子里面的球數(shù)將為0。我們來看，對于任意一個球，設其編號為n，則在差(1/2)n?1分鐘到零點時該球將被取出。也就是說，對于任意球n，在零點時它都不在罐子里。因此，零點時罐子里球的個數(shù)為0。對于有些人來說，這個答案似乎不可接受。但又確實找不到駁斥的辦法。你能找出來嗎？也許這個答案是合理的，因為拿球順序的變化使得算法發(fā)生了變化，即我們實際上討論的是兩個算法。可仔細一想又覺得不對，因為兩個算法都是每次放進10個球，拿出1個球，即從根本上說，這是兩個一樣的算法，怎么會有截然相反的結果呢(見圖1-2)圖1-2 到底剩多少個球？不同的拿球順序有不同的結果，如果我們再次改變試驗中拿球的方式，將拿某個特定標號的球改為取出任意標號的球，即：在差1分鐘到零點時：將標號為1～10的10個球放進罐子，然后從罐子任意拿出一球。在差1/2分鐘到零點時：將標號為11～20的10個球放進罐子，然后從罐子任意拿出一球。在差1/4分鐘到零點時：將標號為21～30的10個球放進罐子，然后從罐子任意拿出一球?！@種拿球方式又將產生何種結果呢？答案仍然是無有，即0(本書將在第1章對這個問題進行正面解析)。太不可思議了吧！這三個本質相同的算法怎么有如此匪夷所思的結果呢？如果非要說這三個算法有什么不同，那就是拿球時的標號不同。難道是，標號的不同使最后球的數(shù)量發(fā)生了變化?沒錯。就是這個標號對結果產生了深遠影響。從某種意義上說，標號是虛的，它只存在于我們的想象中，但確實對現(xiàn)實結果產生了影響，即我們的思維使算法發(fā)生了變化?；蛟S從另一個角度來看，這個問題就是：無有就是無窮，無窮就是無有。它們之間也許根本沒有什么不同，它們的不同只存在于人們的想象或者意念中。也許這是為什么無窮的符號(是由兩個0連接而成的，從左右兩面看都是無有，而從中間看則是無窮，如圖1-3所示。圖1-3 無有和無窮的區(qū)別也許只存在于人類的思維中從這個意義上說，算法是一種思維方式(algorithmic thinking)，或者說一種哲學。而本書就是從算法思維的角度出發(fā)，闡述算法的靈魂。1.2 什么是算法究竟什么是算法呢？顧名思義，算法就是計算的辦法或法則。這里的計算指的當然不只是加、減、乘、除等算術運算，而是廣義的做任何事情的計算，而辦法和法則意味著使用它就可以解決需要的問題。算法的歷史可以追溯到9世紀的古波斯。最初它僅表示“阿拉伯數(shù)字的運算法則”。后來，它被賦予更一般的含義，即所謂的一組確定的、有效的、有限的解決問題的步驟。這是算法的最初定義，注意，這個定義里面沒有包括“正確”。推動算法傳播的是生活在美索不達美亞的Al Khwarizmi于9世紀一本以阿拉姆語(Aramaic)著述的教科書。該書列舉了加、減、乘、除、求平方根和計算圓周率數(shù)值的方法。這些步驟的特點是：簡單、沒有歧義、機械、有效和正確—這就是算法。注意，這個定義加上了“正確”這個詞。幾百年后，當十進制計數(shù)法在歐洲被廣泛使用時，“算法”(algorithm)這個單詞被人們創(chuàng)造出來以紀念Al Khwarizmi先生。由上面提到的定義可推知，算法作為解決問題的方法，它必須具備以下特點：?確定性，即無歧義，能讓人照著執(zhí)行。?可行性，算法中的運算都是基本的，理論上能夠由人用紙和筆完成。?有限性，在有限輸入下，算法必須能在有限步驟內實現(xiàn)有限輸出。此外，算法必須有輸出、計算的結果，通常還有至少一個輸入量。這是因為算法用以解決的問題的描述均包括輸入和輸出。

編輯推薦

《算法之道(第2版)》既可以作為大學本科或研究生的算法教材或參考書，也可以作為對算法有興趣的讀者提升認知深度的讀物。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法之道(第2版) PDF格式下載

---