算法評測

算法評測——復(fù)雜度記法

剛才說過，線性查找的計算量為O(n)，二分查找的復(fù)雜度為O(log n)。大多情況下，算法的復(fù)雜度可以這樣定量評測。算法評測一般使用復(fù)雜度記法（Order記法）。

復(fù)雜度記法表示的含義是，當算法的輸入大小為n時，大致需要這么多的計算量。

花費時間與n的大小無關(guān)，能在固定時間內(nèi)完成的處理，其復(fù)雜度為O(1)。例如從散列中查找數(shù)據(jù)，雖然要計算散列函數(shù)，但散列函數(shù)計算不依賴于n，所以復(fù)雜度為O(1)。而散列搜索中，給定鍵的值（幾乎）是唯一的，因此通過鍵搜索值的處理也是O(1)（也依賴于具體實現(xiàn)）。因此，散列搜索整體復(fù)雜度為O(1)^[1]。

如前所見，線性查找要從開頭開始查找，最大要查找n次。

某些情況下只需一次就能找到，但復(fù)雜度記法并不考慮這種特殊情況，而是表示平均值或最大值。因此記為O(n)。二分查找為O(log n)。

像這樣用復(fù)雜度記法表示各種算法，即可比較算法的性能。線性查找和二分查找分別為O(n)和O(log n)，因此二分查找的計算量比較少^[2]。

各種算法的復(fù)雜度記法

各種算法的復(fù)雜度記法中，下述幾種計算量經(jīng)常出現(xiàn)。

O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³) … < O(n^k) < O(2ⁿ)

越往右，復(fù)雜度越大。處理大規(guī)模數(shù)據(jù)時，也就是說n比較大時，實用算法也就到O(n logn)附近。再高，復(fù)雜度就會隨著n的增加而急劇增大，經(jīng)常導(dǎo)致計算無法結(jié)束。

感覺上而言，O(log n)比O(n)要快很多，O(n)和O(n log n)的差距不是很大，O(n)和O(n²)之間的鴻溝決定著著計算能否完成……。

關(guān)于速度問題，如果相當復(fù)雜的算法能用O(n²)的計算完成，那也可以說“相當快”了，畢竟速度取決于算法中的計算本身。例如，一般的基于比較的排序算法無論怎么優(yōu)化，也不可能比O(n logn)快，這一點在理論上可以證明。因此，排序算法能達到O(n logn)，就可以認為是高速算法。

復(fù)雜度的概念不僅用于表示計算的時間，也可以用于表示空間。也就是說，復(fù)雜度記法不僅可以表示執(zhí)行時間、操作步驟數(shù)，還可以表示內(nèi)存使用量等。

?

?

上面講述了算法評測。更為詳細的內(nèi)容，請參考講解算法的書籍。

算法評測

復(fù)雜度記法

復(fù)雜度

時間復(fù)雜度（執(zhí)行時間、操作步驟數(shù)）

空間復(fù)雜度（內(nèi)存使用量）

紙巾能折疊幾次？——O(logn)和O(n)的差距

剛才說過，線性查找和二分查找相比，數(shù)據(jù)量變大后，計算時間就會出現(xiàn)巨大差距。這里的重點不是復(fù)雜度記法本身，而是利用復(fù)雜度記法比較算法時，對算法間差距的感覺。就是說要掌握O(log n)和O(n)在n增大時，對于復(fù)雜度差距的感覺。

再看個身邊的例子。準備一張紙巾，然后將其多次對折。到底能對折多少次呢？第一次只需對半折疊即可，完全沒問題。第二次、第三次、第四次直到第五次應(yīng)該也沒問題。但第六次就比較難折了，第七次和第八次完全折不動而不得不放棄。可能有人會想“折100次肯定沒問題！”，而實際上7次就是極限了。為什么呢？

折紙所需的勞動量，依賴于要折的紙張的厚度。假設(shè)這個厚度最初為1mm，那么第一次折疊之后就是2mm。兩次折疊后是3mm……不對，是4mm。

這樣，厚度是1→2→4→8→16→32…這樣增加的?？梢哉J為，設(shè)折疊次數(shù)為n，計算量就按照2ⁿ增長。剛才看到，O(2ⁿ)是個相當大的復(fù)雜度，因此紙巾在n=8時無法折疊也就可以理解了。

另外有文章介紹過，厚度為0.11mm的衛(wèi)生紙折疊25次后會達到富士山的高度^[3]。要折疊富士山那么高的紙……一般方法絕對做不到吧。

對算法中指數(shù)增加、對數(shù)增加的感覺

計算量按照指數(shù)增加的算法，只需一點點數(shù)據(jù)量，計算量就會變得龐大無比。與指數(shù)相反，只以對數(shù)增加的O(log n)的算法，即使數(shù)據(jù)量變得非常大，也只需一點計算量就能解決，這點也能直觀地理解吧。

在思考算法復(fù)雜度時，這種感覺是最重要的。例如要操作的數(shù)據(jù)有1000萬條，如果能選擇對數(shù)算法，那么只需幾十次計算就可以了。相反，如果選錯了算法，使用O(n²)或O(2ⁿ)的算法實現(xiàn)的話，寫出的程序即使只有幾百條數(shù)據(jù)，也要浪費相當多資源。

?

本文節(jié)選自《大規(guī)模WEB服務(wù)開發(fā)技術(shù)》一書

圖書詳細信息:

?http://bvbroadview.blog.51cto.com/3227029/641619

?

轉(zhuǎn)載于:https://blog.51cto.com/bvbroadview/642542

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的算法评测的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。