題主已經想到一個，A演算法的常數可能過大，相反B演算法就會變得更可行，還有其他的理由麼？

  • 空間複雜度過大，空間換時間但目標機器空間不足。
  • 數據量過小，效率更高的演算法耗用時間相對更長。如常數時間每次查詢都需要1毫秒，而平方複雜度在數據量低於某個值時只需幾十個納秒，那麼顯然後者為好。一個典型案例就是對quick sort演算法的優化：當數據分割到小於等於6個元素時改用複雜度高半級的冒泡排序，最終表現卻比純粹的quick sort更好。另一個案例是哈希表，當數據量較小時二分法查找只需十幾次訪問，哈希表本身的哈希演算法卻可能需要執行很多條指令（當然現在因為內存速率和CPU嚴重不匹配，cache miss本身消耗的額外時間可能就足夠執行哈希演算法了，具體哪個更好用需要先做測試才能確定）。
  • 時間消耗不穩定，如常數時間的哈希表在衝突發生時退化到鏈表，而對數複雜度的二分法穩定在對數複雜度。那麼對於實時系統，哈希表可能就是不可行的。
  • 數據準備/維護代價過大。比如一個對數查詢效率的數據結構，插入新數據的消耗可能是指數複雜度。
  • 精度不足。如布隆過濾器效率O（1），但只能確認數據不在集合中。而它報告數據存在時，數據卻可能不在，也就是存在誤判。類似的，有很多效率極高的近似演算法，在需要精確解時顯然是不能用的。
  • 無法滿足可靠性要求。比如如果某高效演算法無法做到事務級可靠性（ACID）、或者在多線程場合表現極差，那麼在可靠性不可忽略的場合自然不能使用。
  • 對數據性質有苛刻要求。比如基數排序效率可達O（N），但要求數據必須是有限位的數字、每位符號數目有限且每個數字位滿足進位值類似的權值約束。

好像一不小心說了七條，但似乎並沒能涵蓋所有情況...

常數這種就不說了。

一般這個時間複雜度都是指最壞複雜度。但很多問題的數據並不是最差的，相反很可能會適合演算法 B，一個比較經典的理論案例是是樹的隨機深度為 log n。一個實際案例是維護有序的拍賣定價序列，理論最好是 treap 這種，但是實際中插入的位置分佈是個 power-law ，暴力的均攤複雜度會更快（嗯其實理論複雜度是一樣的，不過差不多這個意思）

從工程角度來說，演算法 B 的實現簡單、易正確。實際情況下很多時候你需要解決的問題是一次性的，你就需要考慮實現演算法 A 中 debug、寫測試的代價是不是會過高。另外很多時候在一個系統下，B 的時間複雜度已經是一個可忽略的低階項，那麼應當做的是先實現更簡單的方法 B，穩定後再考慮是否需要用 A 替代。

Matlab裏當年自帶的（可能是csparse或者SuiteSparse的）sparse QR/LU的矩陣分解都不是最優解的，我自己上課作業里根據Tim Davis的指令（實際完全是他給標準答案，我們下去手改）擼過一個比當時Matlab自己link的那個版本複雜度低一些，速度快一些的。

具體細節已經忘得一乾二淨了，但是總之改之前50行，改之後也不超過70行，工作量非常小，總共修改不超過30行，但收益很大。

他自己當時也沒把這部分工作merge到最新版本的csparse和suitesparse裏，於是就給我們先當個作業練練手。問題是這種工作也沒啥人關心，因此哪怕地球上有70億人，可能除了Tim Davis自己和上課的幾個人以外，沒人知道這30行應該在哪裡寫、怎麼寫……

  1. 實際可能輸入的數據太小導致A和B由於常數因子的影響實際運行時間差別不大
  2. 演算法A空間複雜度太高導致實際運行的時候有不切實際的內存消耗
  3. 實際輸入的數據大小在最終運行時間的體現上對AB演算法差別很小（比如說只差個1-2秒）在應用中不重要，但是演算法A實現起來比B複雜很多導致不易維護，所以選擇比較簡單的演算法B
  4. 演算法A難以並行，演算法B可以幾乎不需要太大改動直接並行，實際應用中並行跑演算法的總時間小於單線程運行A
  5. 程序員考慮問題不全面，AB的時間複雜度分析沒有和實際場景結合，只是初始場景的時間複雜度，比如A雖然是N^2但是應用中接下來大量的使用場景都是N^2複雜度，但是B雖然一開始需要N^3，在實際應用中大量後續操作可以在線性複雜度下完成

A是個樹套樹套樹套樹套樹套樹

B是個三重循環

鬼才去寫A呢。。

推薦閱讀：
相關文章