計(jì)算機(jī)出現(xiàn)之前，就有了算法。隨著計(jì)算機(jī)的誕生，需要更多的算法來(lái)釋放計(jì)算機(jī)強(qiáng)大的計(jì)算能力，算法是計(jì)算的核心，算法決定了計(jì)算機(jī)在解決問(wèn)題時(shí)所采用的具體方式。

如果將計(jì)算機(jī)的存儲(chǔ)器理解為一種空間上的有限資源，那么算法消耗的計(jì)算時(shí)間則應(yīng)該理解為一種時(shí)間上的有限資源。有限資源意味著它們存在各自的上界，即不可能存在無(wú)限快的計(jì)算機(jī)，也不可能存在完全免費(fèi)的存儲(chǔ)器。

隨著摩爾定律走向瓶頸，在面對(duì)大型問(wèn)題時(shí)，僅依靠硬件迭代可能愈發(fā)難以滿足海量的計(jì)算需求，選擇在時(shí)間和空間方面有效的算法，或許是有效提升實(shí)際收益的明智之舉。

那么，算法改進(jìn)和硬件迭代相比，誰(shuí)的收益更大？

[[431743]]

（來(lái)源：Pixabay）

算法改進(jìn)與硬件迭代，究竟哪一種方式收益更高？一直以來(lái)都是學(xué)術(shù)界和工業(yè)界關(guān)注的熱點(diǎn)問(wèn)題。來(lái)自麻省理工學(xué)院的相關(guān)人員前不久對(duì)這個(gè)問(wèn)題作出了較為全面的回答。

為保證研究過(guò)程的嚴(yán)謹(jǐn)性，MIT 的研究人員全面分析了來(lái)自 57 部教科書(shū)和 1137 篇研究論文的相關(guān)數(shù)據(jù)，并撰文《How Fast Do Algorithms Improve?》，論文發(fā)表在 IEEE Proceedings 上，這是有史以來(lái)第一次對(duì)算法進(jìn)展研究的綜合分析。

圖 | 相關(guān)論文（來(lái)源：IEEE Proceedings）

作者采用算法步驟分析的方式對(duì)算法展開(kāi)研究，即在分析時(shí)間復(fù)雜度時(shí)保留常數(shù)項(xiàng)。對(duì)于給出明確算法步驟的參考論文，直接使用其結(jié)論。對(duì)于沒(méi)有給出明確算法步驟的參考論文，使用 “偽代碼” 進(jìn)行重構(gòu)。

研究?jī)?nèi)容主要包含以下幾方面工作：首先，作者系統(tǒng)地回顧了各算法的提出時(shí)間、改進(jìn)時(shí)間，以及算法改進(jìn)的總體趨勢(shì)；然后，作者針對(duì)不同的問(wèn)題規(guī)模，對(duì)算法和硬件的改進(jìn)率進(jìn)行了對(duì)比分析；最后，作者利用算法和硬件改進(jìn)率的對(duì)比分析結(jié)果，給出了問(wèn)題規(guī)模及算法族跟改進(jìn)率之間的相互關(guān)系。

算法回顧

依據(jù)待解決問(wèn)題的類(lèi)型進(jìn)行劃分，作者將算法劃分為 113 個(gè)不同的算法族，對(duì)這些算法族的發(fā)展歷程進(jìn)行了回顧，對(duì)改進(jìn)算法進(jìn)行了跟蹤分析，并重點(diǎn)關(guān)注那些有效提升性能的新算法。

這 113 個(gè)算法族包含了從 1940 年至今的大部分算法，每個(gè)算法族平均包含 8 種算法。判斷一個(gè)算法是否為有效的改進(jìn)算法，其主要依據(jù)為判斷算法是否有效降低了所屬算法族在最壞情況下的漸進(jìn)時(shí)間復(fù)雜度。

基于這一標(biāo)準(zhǔn)，作者得到 276 種初始算法和后續(xù)改進(jìn)算法，并且每一個(gè)初始算法平均有 1.44 個(gè)后續(xù)的改進(jìn)算法。上述研究成果可在作者團(tuán)隊(duì)所創(chuàng)建的 “算法維基百科” 頁(yè)面（ http:// Algorithm-Wiki.org ）獲取更為詳細(xì)的信息。

如圖所示，作者將算法族作為基本單元，對(duì)算法的提出和改進(jìn)歷程進(jìn)行了歸納總結(jié)。其中，a）依據(jù)各算法族首次提出的時(shí)間，以十年為間隔，對(duì)算法族數(shù)目進(jìn)行了統(tǒng)計(jì)；b）依據(jù)各算法族得到改進(jìn)的時(shí)間，以十年為間隔，對(duì)算法族數(shù)目進(jìn)行了統(tǒng)計(jì)；c）統(tǒng)計(jì)了所有算法族首次提出時(shí)間的漸進(jìn)時(shí)間復(fù)雜度分布；d）表明通過(guò)算法改進(jìn)，算法族的漸進(jìn)時(shí)間復(fù)雜度在一年間得到降低的平均概率。

圖 | 算法回顧。（a）每個(gè)十年提出的新算法族數(shù)量；（b）已有算法族在每個(gè)十年間得到改進(jìn)的數(shù)量；（c）算法族首次被提出時(shí)的算法漸進(jìn)時(shí)間復(fù)雜度；（d）同一時(shí)間復(fù)雜度的算法提升至另一個(gè)時(shí)間復(fù)雜度的年平均概率。注：在（c）和（d）中”>n3”表示漸進(jìn)時(shí)間復(fù)雜度高于多項(xiàng)式時(shí)間復(fù)雜度，但低于指數(shù)級(jí)時(shí)間復(fù) 

如上圖所示，算法族的改進(jìn)速度在 1970’s 后有所放緩，作者認(rèn)為其原因可能包括：

1）某些算法已達(dá)到理論最優(yōu)，提升空間有限；

2）算法改進(jìn)的邊際收益正在減少，改進(jìn)成本提高；

3）近似算法更受研究者關(guān)注（不排除算法改進(jìn)困難迫使研究者探索近似解）。

如圖 c）可以看到，其中 31% 的算法為指數(shù)漸進(jìn)時(shí)間復(fù)雜度。而在圖 d）中正是將這些指數(shù)漸進(jìn)時(shí)間復(fù)雜度的算法族改進(jìn)到多項(xiàng)式時(shí)間復(fù)雜度更具深遠(yuǎn)的意義，這些改進(jìn)使得某些大型問(wèn)題得以求解。

對(duì)比分析

作者分析了算法族的性能隨新算法的發(fā)現(xiàn)，在時(shí)間上呈現(xiàn)出的發(fā)展趨勢(shì)。如圖所示，統(tǒng)計(jì)了四個(gè)算法族隨算法改進(jìn)隨時(shí)間呈現(xiàn)的性能變化，對(duì)于 n=100 萬(wàn)的問(wèn)題規(guī)模，一些算法的改進(jìn)效率已優(yōu)于硬件提升的效率。并且算法改進(jìn)和硬件迭代之間的一個(gè)明顯差別是：摩爾定律使得硬件性能呈現(xiàn)平穩(wěn)上升的趨勢(shì)，而算法改進(jìn)呈現(xiàn)明顯的不確定性。

圖 | 算法性能提升趨勢(shì)。（a）四個(gè)算法族隨算法改進(jìn)隨時(shí)間呈現(xiàn)的性能變化；（b）硬件迭代隨時(shí)間產(chǎn)生的性能變化（來(lái)源：IEEE Proceedings） 

如圖，當(dāng)擴(kuò)展對(duì) 110 個(gè)算法族的分析時(shí)（如圖（a）所示)，對(duì)于數(shù)千量級(jí)的問(wèn)題而言，只有 18% 的算法改進(jìn)相較于硬件迭代具有更強(qiáng)的性能提升。隨著問(wèn)題規(guī)模的不斷增加，算法改進(jìn)帶來(lái)的性能提升就超過(guò)了硬件迭代。甚至有 14% 的算法族的改進(jìn)率超過(guò)了 1000%，這部分性能的卓越提升大多受益于將指數(shù)漸進(jìn)時(shí)間復(fù)雜度的算法改進(jìn)至多項(xiàng)式漸進(jìn)時(shí)間復(fù)雜度。當(dāng)一個(gè)算法從指數(shù)漸進(jìn)時(shí)間復(fù)雜度改進(jìn)至多項(xiàng)式漸進(jìn)時(shí)間復(fù)雜度時(shí)，它以任何硬件迭代都無(wú)法達(dá)到的方式改變了問(wèn)題的可處理性。當(dāng)問(wèn)題增加至數(shù)十億乃至數(shù)萬(wàn)億的規(guī)模時(shí)，算法改進(jìn)比硬件迭代平均每年帶來(lái)的收益更高。

圖 | 基于漸近時(shí)間復(fù)雜度計(jì)算的 110 個(gè)算法族平均年改進(jìn)率分布。（a）n=1000；（b）n=100萬(wàn)；（c）n=10億（來(lái)源：IEEE Proceedings） 

這些發(fā)現(xiàn)表明，在大數(shù)據(jù)背景下，在對(duì)那些擁有海量數(shù)據(jù)的領(lǐng)域進(jìn)行數(shù)據(jù)分析、機(jī)器學(xué)習(xí)時(shí)，算法改進(jìn)顯得尤為重要。

作者發(fā)現(xiàn)不同算法族的改進(jìn)歷程有極強(qiáng)的差異性，部分算法族改進(jìn)進(jìn)展緩慢，而又存在 14% 的算法經(jīng)歷了比硬件迭代改進(jìn)大幾個(gè)數(shù)量級(jí)的改進(jìn)，極大地超越了摩爾定律。

總的來(lái)說(shuō)，在面對(duì)問(wèn)題規(guī)模較大時(shí)，算法改進(jìn)帶來(lái)的收益大于硬件迭代（摩爾定律）。