怎麼評價一個演算法的效率?

* 假如兩個演算法的時間複雜度都是O(n),是不是應該考慮n之前的係數?

* 假如A演算法需要做1000次比較,100次賦值;演算法B需要做500次比較,200次除法,200次賦值。那麼哪種演算法效率高?不同的步驟(賦值/加減/乘除/比較/空間佔用)的複雜度如何進行比較和評判?

* 評價演算法一般是考慮平均複雜度(或者針對某類問題的平均複雜度),如果通過實際測試來評價演算法的效率,是不是有說服力?


我覺得, 最簡單直接的辦法, 是考察演算法在特定條件下(時間、空間、其他開銷、特定的計算機、特定的輸入)解決問題的能力:

能解決, 那麼這個演算法就是可行的;

不能解決, 那麼這個演算法就是白搭。

如果要找尋通用的評價方法, 也應該根據演算法的

平均時間複雜度

平均空間複雜度

最壞時間複雜度

最壞空間複雜度

輸入與時間開銷的分布關係

特定輸入下的時間空間開銷

所用的資源開銷(如並行處理)

演算法運行的特殊要求(如硬體支持)

來綜合判斷,不能一概而論。


評價單個演算法,往往是通過將其與另外一個演算法進行比較。一般分為理論上與實踐中兩方面來評價一個演算法的效率。

理論上,大O記號是一個上界,通常可以在一定程度上反應演算法的真實效率。

該思想基於如下考慮:如果演算法A1在「最壞情況」下比演算法A2要好,那麼認為A1好於A2。

這裡特指「最壞情況」,而並非所有情況,即有時候A2反而會好於A1,比如希爾排序在n比較小的時候通常好於快速排序。演算法的時間空間開銷往往和問題規模成正比,所以「最壞情況」,實際上指的是當問題規模趨近於無窮的時候。因此通常在理論上認為,一個複雜度為O(n^1.68)的演算法,是好於一個複雜度為O(n^2)的演算法的,而與演算法中n前面的係數無關。

特別說明的是,大O記號只是理論上其中一種衡量上界的標準,而這個界並非是嚴格緊緻的,例如一個n^2複雜度的演算法也可以說它是O(n^3)的。而反應上下界的大Θ記號就要相對準確些。實際使用中,用大O記號一般都默認用的是該演算法所有可能上界中的最下界。

相比與時間複雜度,空間複雜度往往不太過追求,甚至為了更低的時間複雜度去犧牲空間複雜度,即「用空間換時間」。這是由於隨著計算機硬體的發展,演算法中數據的存儲往往不是太大問題,一般都考慮「誰用的時間更少」,而非「誰用的空間更小」。當然,在時間複雜度一樣的情況下,會去追求空間複雜度,比如原地歸併排序(in place merge sort)就是個很好的例子。

而在實踐中,從實驗上評價演算法的效率,就要考慮很多額外的因素。

1. 編碼實現的效率

由於演算法最後的實現效率在很大程度上和編碼實現方式有關,所以大家通常都會保證自己的實現方式盡量高效。比如用相對高效的語言(例如C)來實現、將遞歸演算法進行非遞歸改寫、結合編譯器做代碼上的優化等等。這樣一來,實現手段上的不同難免會給演算法真實效率上的評價帶來影響。比如一個很好實現的O(n^3)的演算法,的確有可能比一個相對差的實現的O(n^2)的演算法要快。但是,大O記號的魅力就在於,當n足夠大的時候,演算法複雜度上帶來的差異一定可以抹平不同實現方式上的差異——一個O(n^2)的演算法最終(n大於某個值時)一定是比O(n^3)的演算法要快的。

2. 機器硬體的影響

在不同計算機硬體上運行顯然會對演算法運行時間帶來影響,通常會指明運行的機器操作系統,CPU類型、主頻等參數,從而方便比較。比如演算法A1運行的機器比A2運行的機器差不多快一倍,那麼比較時間的時候就對應地將A2的運行時間乘以二分之一。一般很難在不同硬體上做到精確的比較,只能大概而為之。即使在同一台機器上進行比較,也和編譯時的參數設置,編譯器不同有關,比如gcc中O2可能會比O3快、intel晶元上用icc編譯的代碼通常比gcc編譯的要快等等,影響因素太多,無法做到精確。

這裡,要格外說明的一點是cache命中率的問題。由於CPU緩存和內存讀取速度上的巨大差異,cache的命中率過低往往會嚴重影響演算法真實性能的比較。這方面一個比較經典的例子就是堆排序,可以參考知乎上堆排序缺點何在? 問題中的高票回答。另,數據結構的設計也會影響演算法這方面的性能。此外,如果是在多核環境或者機群上運行,不同CPU的緩存之間會互相影響命中率的情況也應加以考慮並盡量避免。

3. benchmark測試

為了更客觀公正的比較演算法的真實效率,學術界(包括某些工業界)的做法是建立一個公認的針對某問題的演算法測試數據集,也稱為benchmark(見過翻譯為「演算法試金石」的,覺得很形象)。通常的做法是在給定問題的benchmark上,給定一個時間上限,運行不同的演算法,通過比較結果來評價演算法效率。這裡比較的標準一般有兩條,解的質量和求解速度,前者更為本質。

例如,在benchmark的100個問題中,每個問題給定7200秒的時間上限,演算法A1求解出了90個,平均時間100秒;演算法A2求解出了70個,平均時間60秒——一般認為A1好於A2。這是因為A2求解速度上的優勢可能和實現手段運行環境多方面因素有關;但是否能解出問題,更能反映演算法的本質。

除了統計平均值,還有一種是統計median值(中位數/中值)。在上面的例子中,A1所解出的90個平均花費100秒,但有可能是其中70個算例花費時間都小於60秒,只是其中某幾個算例花費很多時間才解出,從而拖高了平均值,顯然A1是全面好於A2的。此時平均時間就不是一個好的刻度,而median會更合適。比如比較A1、A2分別算出的算例中的median時間;或者比較總共100個算例的median時間,即看算出50個算例A1、A2的平均花費時間。諸如此類的統計方式很多,不一一詳述。但大體原則是,解的質量為主,求解速度為輔。

此外,對於隨機化演算法,還需要根據不同隨機種子上的不同運行情況來求平均值來進行比較,比如100個算例集,每個都用不同的隨機種子運行100次,再統計平均時間,平均成功率等等。這種規模的試驗計算量往往比較大,需要用到機群,但結果比較具有說服力。

總結

有些演算法的複雜度,難以從理論上給出定量分析,通常是以benchmark上的演算法實際效率比較為主;而可以定量分析出複雜度優劣的演算法,在實際應用中,也會受到多方面因素的影響,benchmark上的實驗結果往往更具有說服力。

實際上,基於合理的benchmark的實驗性比較和理論上的分析是完全一致的。因為無論是實現手段、還是運行環境等多方面因素帶來的影響,充其量只能影響演算法客觀複雜度里n前面的係數。這種差距,會隨著問題規模的增長而被演算法複雜度上的差異所抹平——當然,這需要新的演算法能有效抓住問題本質,帶來足夠大的改進才行。

希望有所幫助,歡迎討論。


我認為這裡其實有兩個問題,一個是演算法的時間複雜度,另一個是演算法實現後的執行效率。在兩個演算法的平均時間複雜度相近的情況下,係數是需要考慮的,同時還要考慮實際情況下最壞情況和最好情況出現的可能性,以及對於n較大時和n較小時的演算法時間複雜度的比較。演算法的執行效率相對來說屬於實現的問題,和硬體架構有關,不同運算指令的比較經常用指令執行需要消耗的時鐘周期來衡量。


複雜度是衡量性能的主要標準,但也不是唯一標準。主要是要對數據量有一個相對準確的估算。

畫一個圖,橫坐標是數據量,縱坐標是時間。複雜度高的斜率高,複雜度低的斜率低,而當複雜度低的係數高時,這兩個演算法的曲線在第一象限一定有一個交點。那麼到底選擇哪個演算法,在於你的數據量在這個交點的左邊還是右邊。

如果可以預估到,絕大多數時候數據量都在左邊,那完全可以選擇複雜度高的演算法。但如果不太確定數據量,要相信數據量總會增大的,所以選擇複雜度低的演算法擴展性更強。

舉個例子,我們經常要對某學校的幾千名學生的某項數據進行排序(假設數據範圍非常大,1~10億)。

程序員選擇了兩個演算法:

1、快速排序,O(nlgn)

2、點陣圖排序,O(n)

前者複雜度低,但開闢內存非常快。幾千名學生瞬間就排好了。後者複雜度到了極限,但該演算法要開闢數據範圍/8Byte的內存,開闢內存和初始化本身就需要幾秒的時間,實際執行的操作比快排多非常多,而且每次排序伺服器的內存都被佔滿了。那麼我們選擇哪個?必然前者,因為可以估算得出,該學校的學生十年內也不會超過1萬人。但如果這個系統以後會用來統計全球所有人的該項數值,那麼後者演算法更合適。


評價一個演算法的效率,一般有兩種大致的思路:

  1. 看代碼,找出關鍵操作,推導出該操作執行次數關於輸入規模的變化函數,並且一般找出最大項作為其時間複雜度大O表示
  2. 迭代,使用「doubling ratio experiments」迭代出大致的增長率


Big-O notation旨在描述一個演算法執行步驟的一個增長曲線,而非具體的執行時間。事實上在數據規模一定小的情況下,更高複雜度的演算法,可能執行速度更快。 舉例來說,

圖中的兩個函數,在數據範圍足夠小的情況下,O(n^2)的效率會更好。

如果我們把,數據擴大10倍再來看,

當數據量超過一個值c的時候,常數所起到的影響就已經微乎其微了。樓上的 @肖進 的答案中談到,

一般比較確定環境下的平均執行時間。

比如O(n)的基排一般都比O(n*log(n))的排序慢很多。

基排的單步操作可能要更耗時,但是終歸是複雜度以下的函數或者常數。當n的值達到某一個常數c後,O(n log (n)) 的效率總是會高於O(n)的,只是對數級函數增長的慢到,現實遇到的問題中都沒有超過這個常數而已。

比如我們加上一個n log n的函數,這麼看起來,總是要比線性的要差啊,把數據再翻上10倍,

這裡,n log n 已經明顯要比線性 n 的效率低了,而且隨著數據量的增大會越來越差。不論所談論的常數多大,總會在那麼一個點開始變的越來越差。實際應用中在有些分治的問題上,不同的數據規模下,可能會使用不同複雜度的演算法,比如用更高複雜度的演算法去處理邊界上小規模數據。像題主描述的問題中,如果知道數據規模,自然可以通過這個評價方法,綜合考量時間、空間以及編寫代碼的難度,選取一個更合適的演算法。


Big O可以用來表示增長情況,演算法負責度。對於第一個問題,Big O 指的是當輸入的量非常大的時候複雜度的增加速度,所以如果是一個常數,當輸入趨向無窮時可以忽略。對於前面的係數,比如2n,3n或1000n,將他們和指數增長比,無論是幾,當n很大時指數將遠大於冪函數,所以n有一些影響,但是在Big O 中這是不予考慮的。第二個問題不可一概而論,一般可以將每一步近似看成一樣的。但計算機在調取的時候數據會分層存儲,實際會有差別。處理的方法是將每一步看成一樣,一步就算一。如果有一個循環結構,這種情況才值得注意,因為一個循環結構可能運行1000次比較,這樣的差距遠比比較或除法的差距大,這是我們需要考慮的。對於第三個問題,理論上我們可以比較平均值,但實際上我們更關心最壞值。要知道理論值,我們得知道這種情況的概率分布,然後進行數學運算求解。這樣的運算是非常複雜的,特別是對一個龐大的程序項目,幾乎不可能得到。用實際測試法不現實,這裡舉兩個原因。第一,如果一個程序要運行幾年,怎麼測試?誰能等得住?另外一點,輸入值不同,程序運行的時間會相差很多,在不同性能電腦上也差別很大 不具有比較性。


* 當然應該考慮係數

* 不同的指令在不同的CPU架構上效率不同, 因此不能一概而論, 需要通過實際測試來決定.


@邱增帥


推薦閱讀:

計算機的隨機數是怎麼產生的?有演算法嗎?如果有演算法,那麼產生的數字還是真真意義的隨機數嗎?
王垠有實力拿圖靈獎嗎?
怎樣計算/證明/目測 出解決一個問題的最低時間複雜度?

TAG:演算法 | 計算機科學 | 搜索演算法 | 演算法設計 | 計算機原理 | 排序演算法 |