算法有多快

讓我們回到鮑比的算法上债沮。我們肯定使事情得到了改善，新的算法肯定比我們最初的辦法要好，可是一個(gè)顯而易見(jiàn)的問(wèn)題是——這個(gè)算法到底有多快吟宦，用它來(lái)寫那本書要花多長(zhǎng)時(shí)間。這是我們有可能做到的的最佳方式嗎涩维？還是我們能想到更好的算法殃姓，能幫鮑比更容易的把那本書寫出來(lái)。

我們需要一個(gè)測(cè)量方法去試驗(yàn)一下一個(gè)算法有多好瓦阐。也許我們可以通過(guò)用不同的算法來(lái)傳達(dá)一些特定的文字來(lái)測(cè)試每種算法需要的時(shí)間蜗侈，我們可以花大量的時(shí)間找不同的人進(jìn)行測(cè)試得出平均值，但是這會(huì)花費(fèi)大量時(shí)間和精力垄分。

有一個(gè)更好的辦法宛篇。我們可以運(yùn)用“分析思維”來(lái)做這件事，我們會(huì)運(yùn)用簡(jiǎn)單的數(shù)學(xué)方法解出答案薄湿。

我們先不考慮時(shí)間叫倍，我們來(lái)想一想我們要做的事情。如果我們數(shù)清楚每猜出一個(gè)字母助手需要說(shuō)的字母的數(shù)量豺瘤，我們就可以把“猜出一個(gè)字母需要多少時(shí)間”這個(gè)問(wèn)題變成“猜出一個(gè)字母需要說(shuō)多少個(gè)字母”這個(gè)新問(wèn)題了吆倦。

這樣做，我們其實(shí)是運(yùn)用了“抽象思維”坐求，這也是計(jì)算思維的一部分蚕泽，通常被用來(lái)簡(jiǎn)化問(wèn)題。抽象的意思其實(shí)是“隱藏部分細(xì)節(jié)”桥嗤，這種想法被用于計(jì)算的各個(gè)環(huán)節(jié)來(lái)使問(wèn)題變得更容易须妻。在這里，我們用“猜出一個(gè)字母需要說(shuō)的字母的數(shù)量”來(lái)抽象代替“猜出一個(gè)字母需要花費(fèi)的時(shí)間”泛领。

所以我們要做的事情是弄清猜出一個(gè)字母到底需要說(shuō)多少個(gè)字母荒吏。我們需要問(wèn)幾個(gè)問(wèn)題，最簡(jiǎn)單的就是：看一下最好的情況是什么樣渊鞋，為了把書寫出來(lái)绰更，助手最少可能要說(shuō)多少個(gè)字母瞧挤。還要看看最差的情況是什么樣，如果我們很不幸儡湾，情況會(huì)有多糟糕特恬。最后我們看一下平均情況是什么樣，這可以讓我們對(duì)實(shí)際花費(fèi)的時(shí)間有一個(gè)真實(shí)的估計(jì)徐钠。

最好和最差

為了便于討論癌刽，我們這里只討論字母表上的26個(gè)字母，不討論阿拉伯?dāng)?shù)字丹皱、標(biāo)點(diǎn)符號(hào)等等妒穴。如果這本書的內(nèi)容是“ZZZZZZZ……”,那么用“按從A-Z的順序讓助手讀字母”的算法，每猜出一個(gè)字母都需要說(shuō)25個(gè)字母摊崭，這是最糟糕的情況讼油。最好的情況是書的內(nèi)容是“AAAAAA……”,那么每猜出一個(gè)字母只需說(shuō)1個(gè)字母就可以了。當(dāng)然書的內(nèi)容不會(huì)是最好的情況也不會(huì)是最差的情況呢簸，也就是說(shuō)實(shí)際每猜出1個(gè)字母平均需要說(shuō)的字母數(shù)量在1-25之間矮台。

“1-25”這個(gè)范圍似乎過(guò)于大了，其實(shí)情況可以變得更簡(jiǎn)單根时。我們可以把26個(gè)字母分成13組字母瘦赫，“A-Z”“B-Y”“C-X”等等。想一想在一段長(zhǎng)長(zhǎng)的文字中蛤迎，每有一個(gè)“A”,都能在接下來(lái)的文字中找到一個(gè)“Z”确虱，猜出一個(gè)“A”(需要說(shuō)的字母數(shù)量是1)和一個(gè)“Z”（需要說(shuō)的字母數(shù)量是25），所以每猜出一組“A和Z”需要說(shuō)的字母數(shù)量總共是26替裆，其他字母組“B和Y”“C和X”“D和W”等也是這樣校辩，那么這樣算的話，平均猜出一個(gè)字母的需要說(shuō)的字母數(shù)量是13辆童。用全書內(nèi)容包含的字母數(shù)乘以13宜咒，再乘以助手每說(shuō)一個(gè)字母花費(fèi)的時(shí)間，就能得出寫完整本書所需的大致時(shí)間了把鉴。

鮑比的改進(jìn)故黑，先問(wèn)常見(jiàn)單詞的做法，使事情得到了改善庭砍。按鮑比的做法场晶，每猜出一個(gè)字母需要說(shuō)的字母大概是9-10個(gè)。通過(guò)使用字母出現(xiàn)的頻率怠缸，我們能更精確地猜出鮑比要說(shuō)的字母峰搪，但是最糟糕的情況依然還是要說(shuō)25個(gè)字母才能猜對(duì)。

然而正如任何一個(gè)計(jì)算機(jī)科學(xué)家了解的凯旭，我們可以做得好的多概耻。僅用5個(gè)問(wèn)題猜出一個(gè)字母是可能的」藓簦可以保證鞠柄，不是平均需要問(wèn)5個(gè)問(wèn)題，而是最多需要問(wèn)5個(gè)問(wèn)題嫉柴。

五次之內(nèi)猜出字母

無(wú)論你能否想出問(wèn)題的答案厌杜，我保證你一定知道問(wèn)題所屬的正確類別。來(lái)做一個(gè)“20個(gè)問(wèn)題”的兒童游戲计螺，游戲內(nèi)容是我想出一個(gè)名人夯尽，你來(lái)猜這個(gè)名人是誰(shuí)。難點(diǎn)在于我每次只會(huì)告訴你“Yes”或“No”登馒。和朋友一起玩一玩這個(gè)游戲匙握。

這個(gè)游戲可能的過(guò)程是這樣的：

A：是女性嗎？

B：No

A: 還活著嗎陈轿？

B：No

A：是電影明星嗎圈纺？

B:? No

A：是來(lái)自亞洲嗎？

B：No

A：是來(lái)自印度嗎麦射？

B：Yes

A：是甘地嗎蛾娶？

B：Yes

機(jī)會(huì)就是當(dāng)你在玩這個(gè)游戲的時(shí)候，你也問(wèn)類似的問(wèn)題潜秋。你當(dāng)然不太可能會(huì)問(wèn)這樣的問(wèn)題：是阿黛爾嗎蛔琅？是博爾特嗎？是女王嗎峻呛？ 那樣的話你永遠(yuǎn)不能在20個(gè)問(wèn)題內(nèi)猜對(duì)答案罗售。你應(yīng)該問(wèn)“問(wèn)完之后你能更清楚這個(gè)人是誰(shuí)”這一類的問(wèn)題。所以你該先問(wèn)“是女性嗎”這種問(wèn)題杀饵。

為什么這種問(wèn)題是好問(wèn)題呢莽囤？因?yàn)闊o(wú)論答案如何，它都能排除一半的可能性切距。假設(shè)我們從100萬(wàn)名人中選一個(gè)朽缎，那問(wèn)完第一個(gè)問(wèn)題后，還剩50萬(wàn)人谜悟。問(wèn)完第二個(gè)话肖，剩250000;第3個(gè)，剩125000葡幸，第4個(gè)大約剩64000最筒，這樣問(wèn)下去，問(wèn)完第10個(gè)問(wèn)題蔚叨，就只剩1000人了床蜘，問(wèn)完第19個(gè)問(wèn)題辙培，就只剩大約2人了，所以最多問(wèn)20個(gè)問(wèn)題就能猜出正確的答案邢锯。因此扬蕊，如果你能問(wèn)出完美的二等分式的問(wèn)題，你肯定能贏丹擎。

通過(guò)正確的提問(wèn)尾抑，最多用20個(gè)問(wèn)題就可以從100萬(wàn)個(gè)選項(xiàng)中找到答案。想一想蒂培，“是不是A” “是不是B”這類問(wèn)題和“是不是阿黛爾” “是不是博爾特”這類問(wèn)題是一樣的再愈。

一種新算法

“問(wèn)題轉(zhuǎn)化思維”又來(lái)啦，如果是同樣的問(wèn)題护戳，那同樣的策略就能讓我們想出更好的解決方案翎冲。對(duì)于字母表里的字母來(lái)說(shuō)，什么是等效的方法呢灸异？我們需要每次把字母表等分府适。顯而易見(jiàn)第一個(gè)問(wèn)題是“是在N之前嗎？“肺樟，下一個(gè)問(wèn)題取決于前一個(gè)問(wèn)題的回答檐春。如果第一個(gè)回答是“Yes”,接下來(lái)我們就問(wèn)“是在F之前嗎？”如果第一個(gè)回答是“No”,接下來(lái)我們就問(wèn)“是在T之前嗎”么伯，依次類推疟暖，無(wú)論答案是哪個(gè)字母，我們都能只用5個(gè)問(wèn)題就一定可以得到答案田柔。

我們還可以運(yùn)用頻率分析的技巧讓速度變得更快俐巴。我們可以英文字母把按照使用頻率的高低，分為高頻詞（使用頻率最高的7個(gè)字母ETAONRI）和低頻詞（頻率較低的19個(gè)字母SHD LFCMU GYPWB VKJXQ Z）硬爆。那么按照二等分的算法去問(wèn)欣舵，第一次提問(wèn)“是高頻詞嗎”，如果回答是“Yes”缀磕，第二次提問(wèn)“是在O之前嗎”缘圈，如果回答是“Yes”第三次提問(wèn)“是在T之前么”，如果回答是“Yes”,答案就是E袜蚕。

通過(guò)把字母分為高頻詞和低頻詞后糟把，任意一個(gè)高頻詞只需提問(wèn)3次就能得到答案，任意一個(gè)低頻詞需要提問(wèn)5次就能得到答案牲剃。算法速度再次得到了提升遣疯。

搜索算法

我們的算法能夠起作用是因?yàn)椴氯嗣筒伦帜高@兩個(gè)問(wèn)題的本質(zhì)相同，本質(zhì)上它是一個(gè)“搜索問(wèn)題”：在一系列給定的東西中凿傅，找到我們想找的那個(gè)特定的東西缠犀。解決這個(gè)問(wèn)題的方法叫“搜索算法”数苫。這是一個(gè)找東西的必定成功的方法。第一種方法夭坪，按照逐一核對(duì)的形式（是不是A文判？是不是B？是不是C室梅？……）去核實(shí)每個(gè)可能答案，這是一種叫作“線性搜索”的算法疚宇。有時(shí)候這是你能采取的最好的做法亡鼠。例如，如果你目睹了一次搶劫敷待，警方安排了一次列隊(duì)認(rèn)人间涵，那你最好的做法就是線性搜索——依次核對(duì)每張臉直到在隊(duì)伍中找到那個(gè)你看到的搶劫犯。

當(dāng)你在一堆無(wú)序的東西中搜索時(shí)榜揖，線性算法非常好用勾哩。如果你要在一列抽屜里找一件針織衫的話，那就從最上面的抽屜開(kāi)始一個(gè)個(gè)地翻吧举哟。

我們的另一種算法涉及發(fā)現(xiàn)二等分問(wèn)題：是在N之前嗎思劳？他是女性嗎？發(fā)現(xiàn)二等分問(wèn)題是一個(gè)通用的問(wèn)題解決策略妨猩，叫“分治”潜叛，也就是分而治之。如果你能想出一個(gè)問(wèn)題的分治解決辦法壶硅，那就很有可能像用重復(fù)等分的辦法得到一個(gè)答案那樣快威兜，會(huì)比一次核對(duì)一個(gè)東西的方法快得多得多。

最簡(jiǎn)單的分治搜索算法被稱為“對(duì)分搜索”庐椒。試想一下椒舵，把你要從中進(jìn)行搜索的東西們按順序排列好，一頭是最小的约谈，另一頭是最大的笔宿。對(duì)分搜索是先去核對(duì)目標(biāo)搜索對(duì)象是在中間那個(gè)東西的前面還是后面，排除一半的可能性窗宇，接下來(lái)在剩下的東西中再重復(fù)這種做法措伐，一直重復(fù)到只剩一個(gè)東西——這個(gè)東西就是你要找的。這和你從一個(gè)超大的電話號(hào)碼簿里找一個(gè)特定的名字類似军俊，你肯定不會(huì)從第一頁(yè)開(kāi)始一個(gè)個(gè)地查下去侥加，一直查到你要找的名字。

搜索算法不只“線性搜索”和“對(duì)分搜索”這兩種粪躬。例如担败， Google是如何在一秒之內(nèi)搜索完全球每個(gè)網(wǎng)頁(yè)頁(yè)面的昔穴？它當(dāng)然要有一個(gè)更好的算法。搜索算法充分利用了另一種抽象方法提前，我們從特定問(wèn)題中抽象出細(xì)節(jié)并將這個(gè)問(wèn)題視為一個(gè)搜索問(wèn)題吗货。這樣我們的搜索算法就成了一個(gè)可用于解決很多問(wèn)題的現(xiàn)成方案。

換個(gè)方式思考這個(gè)問(wèn)題狈网，一旦我們能想出一個(gè)策略在“用20個(gè)問(wèn)題猜出任意一個(gè)名人的名字”這個(gè)問(wèn)題上取勝宙搬，我們也就能夠把這個(gè)策略概括為分治法,這樣一來(lái)，我們就有了一個(gè)適用于其他問(wèn)題的通用策略拓哺。

算法思維優(yōu)先

然而需要注意的事情是我們我們根本沒(méi)有著眼于科技勇垛。我們一直在討論兩個(gè)人的“對(duì)話”。我們想出來(lái)了一個(gè)好辦法士鸥，一個(gè)好算法闲孤，現(xiàn)在我們可以思考如何使用適當(dāng)?shù)目萍紝⑺惴ㄗ詣?dòng)化。我們可以搭建一個(gè)眼球追蹤系統(tǒng)烤礁，用來(lái)觀察眨眼的次數(shù)讼积，也許可以用一個(gè)電極帽來(lái)檢測(cè)鮑比想說(shuō)“Yes”還是“No”。

關(guān)鍵是無(wú)論我們使用什么科技脚仔，在科技背后都要有一個(gè)算法勤众。選錯(cuò)了算法，無(wú)論使用的科技有多好玻侥，交流都會(huì)很慢决摧，解決同樣的問(wèn)題要問(wèn)13次而不是5次。無(wú)論助手是一個(gè)計(jì)算機(jī)還是人類凑兰。 如果我們沒(méi)有先考慮算法掌桩，我們可能會(huì)設(shè)計(jì)出一個(gè)很糟糕的慢吞吞的系統(tǒng)。計(jì)算并不是關(guān)于科技的姑食，而是關(guān)于計(jì)算思維的波岛，計(jì)算思維是用來(lái)想出一個(gè)很棒的解決方案的。

?