怎麼評價一個演算法的效率？
* 假如兩個演算法的時間複雜度都是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萬人。但如果這個系統以後會用來統計全球所有人的該項數值，那麼後者演算法更合適。
評價一個演算法的效率，一般有兩種大致的思路：
- 看代碼，找出關鍵操作，推導出該操作執行次數關於輸入規模的變化函數，並且一般找出最大項作為其時間複雜度大O表示
- 迭代，使用「doubling ratio experiments」迭代出大致的增長率
Big-O notation旨在描述一個演算法執行步驟的一個增長曲線，而非具體的執行時間。事實上在數據規模一定小的情況下，更高複雜度的演算法，可能執行速度更快。 舉例來說，
如果我們把，數據擴大10倍再來看，
一般比較確定環境下的平均執行時間。
比如O(n)的基排一般都比O(n*log(n))的排序慢很多。
基排的單步操作可能要更耗時，但是終歸是複雜度以下的函數或者常數。當n的值達到某一個常數c後，O(n log (n)) 的效率總是會高於O(n)的，只是對數級函數增長的慢到，現實遇到的問題中都沒有超過這個常數而已。
Big O可以用來表示增長情況，演算法負責度。對於第一個問題，Big O 指的是當輸入的量非常大的時候複雜度的增加速度，所以如果是一個常數，當輸入趨向無窮時可以忽略。對於前面的係數，比如2n，3n或1000n，將他們和指數增長比，無論是幾，當n很大時指數將遠大於冪函數，所以n有一些影響，但是在Big O 中這是不予考慮的。第二個問題不可一概而論，一般可以將每一步近似看成一樣的。但計算機在調取的時候數據會分層存儲，實際會有差別。處理的方法是將每一步看成一樣，一步就算一。如果有一個循環結構，這種情況才值得注意，因為一個循環結構可能運行1000次比較，這樣的差距遠比比較或除法的差距大，這是我們需要考慮的。對於第三個問題，理論上我們可以比較平均值，但實際上我們更關心最壞值。要知道理論值，我們得知道這種情況的概率分布，然後進行數學運算求解。這樣的運算是非常複雜的，特別是對一個龐大的程序項目，幾乎不可能得到。用實際測試法不現實，這裡舉兩個原因。第一，如果一個程序要運行幾年，怎麼測試？誰能等得住？另外一點，輸入值不同，程序運行的時間會相差很多，在不同性能電腦上也差別很大 不具有比較性。
* 當然應該考慮係數* 不同的指令在不同的CPU架構上效率不同, 因此不能一概而論, 需要通過實際測試來決定.
@邱增帥
推薦閱讀：
※計算機的隨機數是怎麼產生的？有演算法嗎？如果有演算法，那麼產生的數字還是真真意義的隨機數嗎？
※王垠有實力拿圖靈獎嗎？
※怎樣計算/證明/目測 出解決一個問題的最低時間複雜度？