演算法信息量不可計算

Ⅰ 演算法怎麼就這么難

廣大碼農同學們大多都有個共識，認為演算法是個硬骨頭，很難啃，悲劇的是啃完了還未必有用——除了面試的時候。實際工程中一般都是用現成的模塊，一般只需了解演算法的目的和時空復雜度即可。

不過話說回來，面試的時候面演算法，包括面項目中幾乎不大可能用到的演算法，其實並不能說是毫無道理的。演算法往往是對學習和理解能力的一塊試金石，難的都能掌握，往往容易的事情不在話下。志於高者得於中。反之則不成立。另一方面，雖說教科書演算法大多數都是那些即便用到也是直接拿模塊用的，但不幸的是，我們這群搬磚頭的有時候還非得做些發明家的事情：要麼是得把演算法當白盒加以改進以滿足手頭的特定需求；要麼乾脆就是要發明輪子。所以，雖說面試的演算法本身未必用得到，但熟悉各種演算法的人通常更可能熟悉演算法的思想，從而更可能具備這里說的兩種能力。

那麼，為什麼說演算法很難呢？這個問題只有兩種可能的原因：

演算法本身就很難。也就是說，演算法這個東西對於人類的大腦來說本身就是個困難的事兒。
講得太爛。
下面會說明，演算法之所以被絕大多數人認為很難，以上兩個原因兼具。

我們說演算法難的時候，有兩種情況：一種是學演算法難。第二種是設計演算法難。對於前者，大多數人（至少我當年如此）學習演算法幾乎是在背演算法，就跟背菜譜似的（「Cookbook」是深受廣大碼農喜愛的一類書），然而演算法和菜譜的區別在於，演算法包含的細節復雜度是菜譜的無數倍，演算法的問題描述千變萬化，邏輯過程百轉千回，往往看得人愁腸百結，而相較之下任何菜譜涉及到的基本元素也就那麼些（所以程序員肯定都具有成為好廚師的潛力:D）注意，即便你看了演算法的證明，某種程度上還是「背」（為什麼這么說，後面會詳述）。我自己遇到新演算法基本是會看證明的，但是發現沒多久還是會忘掉，這是死記硬背的標准症狀。如果你也啃過演算法書，我相信很大可能性你會有同感：為什麼當時明明懂了，但沒多久就忘掉了呢？為什麼當時明明非常理解其證明，但沒過多久想要自己去證明時卻發現怎麼都沒法補上證明中缺失的一環呢？

初中學習幾何證明的時候，你會不會傻到去背一個定理的證明？不會。你只會背結論。為什麼？一方面，因為證明過程包含大量的細節。另一方面，證明的過程環環相扣，往往只需要注意其中關鍵的一兩步，便能夠自行推導出來。演算法邏輯描述就好比定理，演算法的證明的過程就好比定理的證明過程。但不幸的是，與數學裡面大量簡潔的基本結論不同，演算法這個「結論」可不是那麼好背的，許多時候，演算法本身的邏輯就幾乎包含了與其證明過程等同的信息量，甚至演算法邏輯本身就是證明過程（隨便翻開一本經典的演算法書，看幾個經典的教科書演算法，你會發現演算法邏輯和演算法證明的聯系有多緊密）。於是我們又回到剛才那個問題：你會去背數學證明么？既然沒人會傻到去背整個證明，又為什麼要生硬地去背演算法呢？

那麼，不背就不背，去理解演算法的證明如何？理解了演算法的證明過程，便更有可能記住演算法的邏輯細節，理解記憶嘛。然而，仍然不幸的是，絕大多數演算法書在這方面做的實在糟糕，證明倒是給全了，邏輯也倒是挺嚴謹的，可是似乎沒有作者能真正還原演算法發明者本身如何得到演算法以及演算法證明的思維過程，按理說，證明的過程應該反映了這個思維過程，但是在下文關於霍夫曼編碼的例子中你會看到，其實飽受贊譽的CLRS和《Algorithms》不僅沒能還原這個過程，反而掩蓋了這個過程。

必須說明的是，沒有哪位作者是故意這樣做的，但任何人在講解一個自己已經理解了的東西的時候，往往會無意識地對自己的講解進行「線性化」，例如證明題，如果你回憶一下高中做平面幾何證明題的經歷，就會意識到，其實證明的過程是一個充滿了試錯，聯想，反推，特例，修改問題條件，窮舉等等一干「非線性」思維的，混亂不堪的過程，而並不像寫在課本上那樣——引理1，引理2，定理1，定理2，一口氣直到最終結論。這樣的證明過程也許容易理解，但絕對不容易記憶。過幾天你就會忘記其中一個或幾個引理，其中的一步或幾步關鍵的手法，然後當你想要回過頭來自己試著去證明的時候，就會發現卡在某個關鍵的地方，為什麼會這樣？因為證明當中並沒有告訴你為什麼作者當時會想到證明演算法需要那麼一個引理或手法，所以，雖說看完證明之後，對演算法這個結論而言你是知其所以然了，但對於演算法的證明過程你卻還沒知其所以然。在我們大腦的記憶系統當中，新的知識必須要和既有的知識建立聯系，才容易被回憶起來（《如何有效地學習與記憶》），聯系越多，越容易回憶，而一個天外飛仙似地引理，和我們既有的知識沒有半毛錢聯系，沒娘的孩子沒人疼，自然容易被遺忘。（為什麼還原思維過程如此困難呢？我曾經在知其所以然（一）里詳述）

正因為絕大多數演算法書上悲劇的演算法證明過程，很多人發現證明本身也不好記，於是寧可選擇直接記結論。當年我在數學系，考試會考證明過程，但似乎計算機系的考試考演算法證明過程就是荒謬的？作為「工程」性質的程序設計，似乎更注重使用和結果。但是如果是你需要在項目中自己設計一個演算法呢？這種時候最起碼需要做的就是證明演算法的正確性吧。我們面試的時候往往都會遇到一些演算法設計問題，我總是會讓應聘者去證明演算法的正確性，因為即便是一個「看上去」正確的演算法，真正需要證明起來往往發現並不是那麼容易。

所以說，絕大多數演算法書在作為培養演算法設計者的角度來說是失敗的，比數學教育更失敗。大多數人學完了初中平面幾何都會做證明題（數學書不會要求你記住幾何所有的定理），但很多人看完了一本演算法書還是一團漿糊，不會證明一些起碼的演算法，我們背了一坨又一坨結論，非但這些結論許多根本用不上，就連用上的那些也不會證明。為什麼會出現這樣的差異？因為數學教育的理想目的是為了讓你成為能夠發現新定理的科學家，而碼農系的演算法教育的目的卻更現實，是為了讓你成為能夠使用演算法做事情的工程師。然而，事情真的如此簡單么？如果真是這樣的話乾脆連演算法結論都不要背了，只要知道演算法做的是什麼事情，時空復雜度各是多少即可。

如果說以上提到的演算法難度（講解和記憶的難度）屬於Accidental Complexity的話，演算法的另一個難處便是Essential Complexity了：演算法設計。還是拿數學證明來類比（如果你看過《Introction to Algorithms：A Creative Approach》就知道演算法和數學證明是多麼類似。），與單單只需證明相比，設計演算法的難處在於，定理和證明都需要你去探索，尤其是前者——你需要去自行發現關鍵的那（幾）個定理，跟證明已知結論相比（已經確定知道結論是正確的了，你只需要用邏輯來連接結論和條件），這件事情的復雜度往往又難上一個數量級。

一個有趣的事實是，演算法的探索過程往往蘊含演算法的證明過程，理想的演算法書應該通過還原演算法的探索過程，從而讓讀者不僅能夠自行推導出證明過程，同時還能夠具備探索新演算法的能力。之所以這么說，皆因為我是個懶人，懶人總夢想學點東西能夠實現以下兩個目的：

一勞永逸：程序員都知道「一次編寫到處運行」的好處，多省事啊。學了就忘，忘了又得學，翻來覆去浪費生命。為什麼不能看了一遍就再也不會忘掉呢？到底是教的不好，還是學得不好？
事半功倍：事實上，程序員不僅講究一次編寫到處運行，更講究「一次編寫到處使用」（也就是俗稱的「復用」）。如果學一個演算法所得到的經驗可以到處使用，學一當十，推而廣之，時間的利用效率便會大大提高。究竟怎樣學習，才能夠使得經驗的外推（extrapolate）效率達到最大呢？
想要做到這兩點就必須盡量從知識樹的「根節點」入手，雖然這是一個美夢，例如數學界尋找「根節點」的美夢由來已久（《跟波利亞學解題》的「一點歷史」小節），但哥德爾一個證明就讓美夢成了泡影（《永恆的金色對角線》））；但是，這並不阻止我們去尋找更高層的節點——更具普適性的解題原則和方法。所以，理想的演算法書或者演算法講解應該是從最具一般性的思維法則開始，順理成章地推導出演算法，這個過程應該盡量還原一個」普通人「思考的過程，而不是讓人看了之後覺得」這怎麼可能想到呢？

以本文上篇提到的霍夫曼編碼為例，第一遍看霍夫曼編碼的時候是在本科，只看了演算法描述，覺得挺直觀的，過了兩年，忘了，因為不知道為什麼要把兩個節點的頻率加在一起看做單個節點——一件事情不知道「為什麼」就會記不牢，知道了「為什麼」的話便給這件事情提供了必然性。不知道「為什麼」這件事情便可此可彼，我們的大腦對於可此可彼的事情經常會弄混，它更容易記住有理有據的事情（從資訊理論的角度來說，一件必然的事情概率為1，信息量為0，而一件可此可彼的事情信息量則是大於0的）。第二遍看是在工作之後，終於知道要看證明了，拿出著名的《Algorithms》來看，邊看邊點頭，覺得講得真好，一看就理解了為什麼要那樣來構造最優編碼樹。可是沒多久，又給忘了！這次忘了倒不是忘了要把兩個節點的頻率加起來算一個，而是忘了為什麼要這么做，因為當時沒有弄清霍夫曼為什麼能夠想到為什麼應該那樣來構造最優編碼樹。結果只知其一不知其二。

必須說明的是，如果只關心演算法的結論（即演算法邏輯），那麼理解演算法的證明就夠了，光背演算法邏輯難記住，理解了證明會容易記憶得多。但如果也想不忘演算法的證明，那麼不僅要理解證明，還要理解證明背後的思維，也就是為什麼背後的為什麼。後者一般很難在書和資料上找到，唯有自己多加揣摩。為什麼要費這個神？只要不會忘記結論不就結了嗎？取決於你想做什麼，如果你想真正弄清演算法設計背後的思想，不去揣摩演算法原作者是怎麼想出來的是不行的。

Ⅱ 計算機的演算法具有哪些特性

計算機的演算法具有可行性，有窮性、輸入輸出、確定性。

計算機演算法特點

1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他視為有效演算法。

2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。

3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。

4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。

5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。

拓展資料：

重要演算法

A*搜尋演算法

俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search

束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法

一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。

Branch and bound

分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。

數據壓縮

數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。

Diffie–Hellman密鑰協商

Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra』s 演算法

迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。

動態規劃

動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。

歐幾里得演算法

在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

最大期望（EM）演算法

在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。

快速傅里葉變換(FFT)

快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。

哈希函數

HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。

堆排序

Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。

歸並排序

Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

RANSAC 演算法

RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演演算法

這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。

並查集Union-find

並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm

尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。

參考資料：計算機演算法