MIT新研究：過去80年，演算法效率提升到底有多快？

新智元報道

編輯：David

【新智元導讀】

隨著摩爾定律走向終結，靠提升計算機硬體效能可能越發難以滿足海量計算的需要，未來的解決之道在於提升演算法的效率。MIT的這篇新論文總結了過去80年來，演算法效率的提升究竟有多快。

提起演算法，它有點像計算機的父母，它會告訴計算機如何理解資訊，而計算機反過來可以從演算法中獲得有用的東西。

演算法的效率越高，計算機要做的工作就越少。對於計算機硬體的所有技術進步，以及備受爭議的摩爾定律的壽命問題來說，

計算機硬體的效能只是問題的一方面。

而問題另一方面則在硬體之外：演算法的效率問題

。如果演算法的效率提升了，對同一計算任務需要的算力就會降低。

雖然演算法效率問題可能不太受關注，但你是否注意到，經常使用的搜尋引擎是否突然變快了十分之一，而在大型資料集中活動，就感覺就像在泥濘中跋涉一樣艱難緩慢。

這些都與演算法效率有關。

近日，麻省理工學院計算機科學與人工智慧實驗室（CSAIL）的科學家提出疑問：演算法效率的提升速度到底有多快？

關於這個問題，現有資料大部分是敘事性的，其中很大一部分是面向特定演算法的案例研究，再把這些研究結果加以推廣。

面對實證研究資料的不足，研究團隊主要利用了來自 57 部教科書和 1110 多篇研究論文的資料，以追溯演算法效率提升的歷史。

其中有些論文的結論中直接給出了新的演算法有多高效，有的論文則需要作者使用“虛擬碼”（對演算法基本細節的簡單描述）進行重構。

研究人員總共研究了 113 個“算法系”，即解決計算機科學教科書中最重要的同一問題的演算法集。他們對每個演算法族的歷史進行了回顧，跟蹤每次針對某一問題提出的新演算法，並特別注意更高效的演算法。

圖1 演算法發現和改進。（a）每十年發現的新算法系的數量。（b）已知算法系的比例每十年都有所提高。（c）首次發現時算法系的漸近時間複雜度分類。（d）同一時間複雜度的演算法轉換到另一個時間複雜度的每年平均機率（反應算法系複雜度提升的平均水平）。在（c）和（d）中“>n3”的時間複雜度表示超過多項式級，但不到指數級。

最早的算法系可追溯到上世紀40年代，每個算法系平均有 8 個演算法，按時間順序效率逐步提升。為了共享這一發現，團隊還建立了“演算法維基”頁面（Algorithm-Wiki。org）。

研究人員繪製了圖表，標識這些演算法族效率提升的速度，重點關注演算法分析最多的特徵——這些特徵往往決定了解決問題的速度有多快（用計算機術語說，就是“最壞情況下的時間複雜度”）。

圖 2 算法系的相對效率提升，使用漸近時間複雜度的變化計算。參考線是SPECInt 基準效能。（a）與該系列中的第一個演算法（n = 100 萬）相比，四個算法系的歷史改進。（b）演算法改進對“最近鄰搜尋”算法系列的輸入大小（n）的敏感度。為了便於比較演算法改進效果隨時間的變化，在圖（b）中將算法系和硬體基準的起始時間段對齊。

結果顯示，變數很大，但也發現了關於計算機科學變革性演算法效率提升的重要資訊。即：

對於大型計算問題，43% 的算法系的效率提升帶來的收益，不低於摩爾定律帶來的收益。

在 14% 的問題中，演算法效率提升的收益遠超硬體效能提升的收益。

對於大資料問題，演算法效率提升收益特別大，因此近年來，這一效果與摩爾定律相比越來越明顯。

當算法系從指數複雜度過渡到多項式複雜度時，情況出現了最大的變化。

所謂指數複雜度演算法，就像一個人猜密碼鎖的密碼一樣。如果密碼盤上只有一位數，那麼任務很簡單。如果像腳踏車鎖一樣，錶盤是4位數，估計你的腳踏車很難有人偷得走，但仍然可以一個個試。如果是錶盤是50位的，就幾乎不可能破解了，需要的步驟太多了。