這幾天看到了吳軍的文章，主要是說明好的計算機算法的一些概念和方法，我覺得相當的受用，所在接下來幾天就來整理一下相關的重點。
在計算機裡面，控制部分很重要，而控制硬體執行的是程序。史元春教授講了計算機思維的本質是翻譯，也就是把人想要做的具體事倩，翻譯成計算機能夠理解的程序語言。很多時候，張三希望計算機做的一件事，和李四希望它做的一件事，有一些共性的地方，久而久之大家發現使用計算機工作的流程是相似的，於是科學家們在翻譯現實世界的需求和計算機虛擬過程時，就提煉出一些高效的、不斷被驗證過的標準流程，這些流程就是我們所說的計算機算法。
人和人水平的差別，東西和東西質量的差別，是數量級的，這個認識恰恰來自於計算機算法。因為在計算機算法上稍微差了一點，最後計算機執行的效率很容易差出千萬倍。
人「本能」地對大數沒有概念，其實對超過我們生活經驗的小數也是如此，計算機算題的速度很決， 以至於人們對一毫秒（千分之一秒）和一微秒的差別是無感的，但是，計算機要處理的數據量也是非常大的，因此累計起來，後者就比前者快了很多（一干倍）。很多計算機從業者對計算機資源的數量沒有概念，總覺得是無窮大，因此無端浪費很多資源，這樣做事倩，在行業裡是很難出人頭地的。即使在Google，軟體工程師因為水平不行，無意中多用掉十倍的計算資源的事情也時常發生。
既然講到了算法的好壞，就必須先要明確衡量算法的標準，以及測試的方法， 這和任何科學都一樣。什麼是好算法呢， 很多人首先會想到速度決，當然還有人會想到佔用內存空間不要太大。制定這樣兩個標準，大方向本身都沒有問題，但用多少數據來測試算法的速度和空間卻是一個問題，因為用不同數量的數據測試時， 兩個算法的相對錶現可能會完全不一樣。
1965年哈特馬尼斯（Juris Hartmanis ) 和斯坦恩斯 ( Richard Stearns ）提出了算法複雜度的概念（ 二人後來因此獲得了圖靈獎 ），計算機科學家們開始考慮一個公平的、一致的評判算法好壞的方法。不過，最早將複雜度嚴格量化衡量的是著名計算機科學家、算法分析之父高德納（Don Knuth)。今天，全世界計算機領域都以高德納的思想為準。
高德納的思想主要包括這三個部分：
-
在比較算法的快漫時，需要考慮數據量特別特別大，大到近乎無窮大時的清況。為什麼要比大數的清況，而不比小數的清況呢？因為計算機的發明就是為了處理大量數據的，而且數據越處理越多。
-
決定算法決漫的因素雖然可能很多，但是所有的因素都可以被分為兩類。第一類是不隨數據量變化的因素，第二類是隨著數量變化的。高德納講，我們在研究算法時，不必考慮前面那個不變的常數，它是10倍，還是1倍， 或者是100倍，只需要看後面那個變化的因素即可。更廣泛地講，任何隨著 N 變化的因素，通常會造成量級的差異。關於量級，量級就如同芝麻和西瓜的差異，西瓜和地球的差異。100個芝麻是無法和一個西瓜去對比的。
-
如果兩種算法在量級上相當，在計算機科學裡，就認為它們是一樣好的，也就是計算機科學家並不關心三五倍的差別，這就好比1粒芝麻和5粒芝麻都是芝麻量級的東西，大家就不要比了。只有當科學家們不關心幾倍的差異後，才可能集中精力考慮量級的差異。也就是說，計算機科學家要盡可能地去撿西瓜。事實上在計算機科學領域，如果誰說自己把目前最好的算法速度提升了一倍，這種論文是無法發表的。
高德納關於算法複雜度的思想，其實又是建立在一個相對理想狀態之下的，也就是說計算機要解決的問題都近乎無限大。很顯然，現實世界並非如此，那麼高德納這樣理想化的假設是否有意義呢？非常有意義，而且非常重要。回顧一下科學發展的歷史，那些能總結出理論的人要做的第一件事，就是過濾掉所有次要的因素，構建一個理想的環境（或者虛擬的環境）。
當年亞里士多德就是因為無法濾除空氣阻力對重力加速度的影響，得到了重物比輕物下降速度快的荒唐結論。而後來伽利略和牛頓在研究運動時，也是假設空氣阻力和摩擦力可以忽略不計的，那就是構建理想狀態。
高德納比同時代的人高出一籌的地方也在於，他構建出了計算機科學的理想狀態。當然，凡事不能走極端，我們有時發現一些科學家想法非常天真，他們把整個世界全都理想化了這當然也不行。從明天開始，我們通過實際例子，說明在計算機這個行業裡，成千上萬倍的效率是如何差出來的，那些不同的做法對我們有什麼啟發。
來源：《吳軍-什麼是好的計算機算法？對效率影響有多大？》
