做算法分析的人從面試到代碼評審幾乎都會碰上同一個追問“你這個算法的時間復(fù)雜度是多少”這句話我聽了十多年到現(xiàn)在依然覺得它是衡量算法效率時問得最準(zhǔn)的一句話。所謂黃金標(biāo)準(zhǔn)不是說它能直接測出幾毫秒、幾兆內(nèi)存而是它把不同寫法、不同語言、不同機器上的算法放進(jìn)同一套坐標(biāo)系讓大家能公平比較、快速排序。這篇內(nèi)容會把時間復(fù)雜度和空間復(fù)雜度徹底講透它們怎么來的、怎么算、有哪些翻車點以及落到工程決策時該怎么用。適合剛開始接觸算法分析的新手也適合寫了大量代碼但一直沒系統(tǒng)捋過復(fù)雜度概念的同學(xué)。先說一個觀點如果你只打算記住一個概念那就記這句話——復(fù)雜度衡量的不是“跑了多久”而是“隨著輸入變大成本怎么漲”。把這個搞明白后面所有計算規(guī)則都只是算術(shù)題。1. 這個“黃金標(biāo)準(zhǔn)”到底在衡量什么1.1 換臺機器結(jié)論就變?yōu)槭裁疵霐?shù)說明不了問題我早年在某團(tuán)隊做過一次排序邏輯替換數(shù)據(jù)量大概幾萬條把插入排序換成了歸并排序。換完一跑時間幾乎沒差有時候甚至比原來還慢一點。如果只看秒數(shù)這次優(yōu)化是徹底失敗的。但用復(fù)雜度分析看插入排序最壞是O(n2)歸并排序保證O(n log n)數(shù)據(jù)一旦漲到百萬、千萬級差距會被立刻拉開。秒數(shù)是“這一次運行”的結(jié)果它受機器主頻、語言運行時、系統(tǒng)負(fù)載、甚至散熱影響而復(fù)雜度描述的是“所有規(guī)模下”的增長規(guī)律跟具體機器無關(guān)。同樣一段雙層循環(huán)在某臺舊筆記本上要跑3秒換到另一臺新機器上可能只要0.3秒。但無論換到哪臺機器數(shù)據(jù)量翻四倍之后O(n2)算法的耗時在漸進(jìn)意義上都會逼近原來的十六倍O(n)算法只會變成原來的四倍。這個比例關(guān)系是結(jié)構(gòu)性的、穩(wěn)定的不隨硬件變化。這也是為什么復(fù)雜度分析能成為溝通算法效率的公共語言它過濾掉了機器差異、語言差異、編譯器優(yōu)化這些外部干擾直擊算法本身的成本結(jié)構(gòu)。所以把復(fù)雜度稱為算法效率的黃金標(biāo)準(zhǔn)名副其實。1.2 增長率才是唯一的裁判復(fù)雜度分析里最核心的數(shù)學(xué)工具是大O表示法它描述的是算法運行成本的上界增長趨勢。為了徒手估計你只需要記住一條基本思想只看增長最快的項丟掉常數(shù)因子和低階項。我做培訓(xùn)時喜歡讓大家看一張增長對比表把所有常見復(fù)雜度放在一起感受一下什么叫“量級碾壓”復(fù)雜度名稱n10n100n1000n10?O(1)常數(shù)1111O(log n)對數(shù)約3約7約10約20O(n)線性10100100010?O(n log n)線性對數(shù)約33約664約9970約2×10?O(n2)平方10010?10?1012O(2?)指數(shù)1024約1.3×103?遠(yuǎn)超可運行范圍完全不可行這張表給我最大的震撼是n1000時O(n2)不過百萬次操作還勉強能跑到n10?O(n2)就是1012級別單機基本跑不動。而O(n log n)在百萬數(shù)據(jù)下仍只有千萬級操作屬于工程里“實際可用”的范疇。這就是為什么排序算法普遍追求O(n log n)而不是O(n2)。順帶把大O、大Ω、大Θ三個符號一起解釋掉。大O是上界說“不會超過某個量級”大Ω是下界說“至少是某個量級”大Θ是緊界說“就是這個量級”。工程討論里說“復(fù)雜度是O(n)”大家默認(rèn)是嚴(yán)格的上界不會去摳符號細(xì)節(jié)但你心里要有數(shù)嚴(yán)謹(jǐn)?shù)膶W(xué)術(shù)場合這些概念不能混用。還有個小問題幾乎每個初學(xué)的人都會問對數(shù)復(fù)雜度為什么統(tǒng)一寫成log n不寫底數(shù)答案很簡單。log?n和log??n之間差一個常數(shù)因子而大O表示法會把常數(shù)因子吸收掉所以底數(shù)寫不寫都一樣。二分查找也好、平衡樹操作也好復(fù)雜度表里就統(tǒng)一寫O(log n)。2. 時間復(fù)雜度計算從一行代碼開始推演2.1 三條基礎(chǔ)記賬規(guī)則徒手算時間復(fù)雜度不需要什么高深數(shù)學(xué)只需要給代碼“記賬”。我總結(jié)了三條最基礎(chǔ)的規(guī)則覆蓋絕大多數(shù)情況第一條順序結(jié)構(gòu)相加。一段代碼里有多個連續(xù)步驟總復(fù)雜度等于各部分相加最后取量級最大的那個。比如先做O(1)的賦值再跑O(n)的循環(huán)總復(fù)雜度是O(1)O(n)結(jié)果就是O(n)。常數(shù)項再大也是常數(shù)n一旦漲起來那個O(1)根本不夠看。第二條循環(huán)結(jié)構(gòu)相乘。一個循環(huán)執(zhí)行m次循環(huán)體內(nèi)執(zhí)行f(n)總代價就是m×f(n)。雙層循環(huán)嵌套外層n次內(nèi)層n次內(nèi)層循環(huán)體O(1)總計n×n×O(1)O(n2)這是最常見也最典型的平方復(fù)雜度來源。第三條分支結(jié)構(gòu)取最壞。遇到if-else分別算各分支的復(fù)雜度答案取最壞的那個分支。為什么取最壞因為復(fù)雜度分析默認(rèn)口徑就是“最壞情況下的成本”除非你明確聲明討論平均情況。這個口徑在面試和評審里是默認(rèn)值不聲明就是看最壞。把這三條吃透你能算掉日常開發(fā)里八成以上代碼的時間復(fù)雜度。剩下的一成靠遞歸最后一成靠均攤分析后面會分別講到。2.2 兩個經(jīng)典案例從雙層循環(huán)到遞歸展開先看一個稍微變形的雙層循環(huán)for i in range(n): for j in range(i, n): print(i, j)內(nèi)層循環(huán)次數(shù)是n(n-1)...1也就是n(n1)/2。我們把它展開成n2/2n/2取量級最大的項去掉常數(shù)因子1/2得到O(n2)。很多人會疑惑明明比純雙循環(huán)少了一半次數(shù)還是O(n2)對因為n2/2和n2是同一個量級系數(shù)在大O表示法里不重要。在數(shù)據(jù)規(guī)模足夠大時少做一半操作和少做零個操作增長趨勢完全一樣。這個例子特別適合糾正“優(yōu)化了一半循環(huán)就能降低復(fù)雜度”的誤解。再看遞歸展開。斐波那契數(shù)列的樸素遞歸是最經(jīng)典的指數(shù)復(fù)雜度案例def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)設(shè)運行時間為T(n)則有遞推式T(n)T(n-1)T(n-2)O(1)。這個遞推式解出來是指數(shù)級的工程里經(jīng)常直接說O(2?)。更精確說法是約O(1.618?)但量級上是指數(shù)。為什么漲得這么快因為每次調(diào)用都會分裂成兩個子調(diào)用調(diào)用樹接近一棵滿二叉樹節(jié)點數(shù)隨樹高指數(shù)膨脹。更關(guān)鍵的是子問題大量重疊——fib(5)和fib(6)都會重復(fù)計算fib(4)及其子樹。這個重復(fù)計算是樸素遞歸的致命傷也是后面講記憶化時的重要動機。2.3 對數(shù)復(fù)雜度里的“底數(shù)去哪了”對數(shù)復(fù)雜度最常見的來源是“每次迭代后問題規(guī)模減半”。最典型的代碼是二分查找def binary_search(nums, target): low, high 0, len(nums) - 1 while low high: mid (low high) // 2 if nums[mid] target: return mid elif nums[mid] target: low mid 1 else: high mid - 1 return -1每執(zhí)行一次循環(huán)搜索區(qū)間縮小一半。從n縮到1需要的次數(shù)是log?n所以時間復(fù)雜度O(log n)。但如果你寫log??n也完全沒毛病因為log?n log??n / log??2兩者只差一個常數(shù)而常數(shù)在大O里被吃掉了。對數(shù)復(fù)雜度出現(xiàn)在各種二分策略里包括二叉查找樹查找、堆的上濾下濾、分治算法只要你看到“每次干掉一半”先往O(log n)想。還要注意對數(shù)復(fù)雜度比線性慢很多但它比常數(shù)級也就差那么三五倍到二十倍。這也是為什么二分查找、平衡樹在十萬、百萬級數(shù)據(jù)下仍然飛快根因就在這里。3. 空間復(fù)雜度容易被忽視的隱形開銷3.1 原地算法和額外空間的界限時間復(fù)雜度和空間復(fù)雜度是一對兄弟但大家往往更關(guān)注時間空間則經(jīng)常被一筆帶過。真到線上內(nèi)存告警的時候空間問題才會暴露出來?？臻g復(fù)雜度的第一件事是要分清楚“輸入本身占的空間”和“額外申請的空間”。復(fù)雜度分析里討論的通常是后者也就是為了運行算法、除了輸入以外臨時分配的內(nèi)存。原地算法意味著額外空間是O(1)。比如插入排序元素交換只用一個臨時變量無論數(shù)據(jù)多大額外空間都不變堆排序同樣O(1)額外空間。歸并排序則不同它要額外開一個和輸入等長的輔助數(shù)組空間O(n)。很多人在計算空間復(fù)雜度時習(xí)慣把輸入數(shù)組也算進(jìn)去這會造成誤判評審時最好說清楚你的口徑是額外空間還是總空間。用一個具體場景來說明差距內(nèi)存里有100萬個整數(shù)約8MB64位下其實是8字節(jié)每個。原地排序額外占用幾乎為零而歸并排序要額外8MB。8MB在單次運行里未必致命但同一服務(wù)同時處理100個這樣的任務(wù)差距就是800MB直接決定要不要擴(kuò)容。3.2 遞歸棧占用隱藏空間大頭遞歸是空間復(fù)雜度最容易被低估的地方。很多初學(xué)斐波那契的人會認(rèn)為時間都O(2?)了空間肯定也爆炸。實際上普通遞歸版本斐波那契的空間復(fù)雜度是O(n)不是O(2?)。原因在于空間復(fù)雜度衡量的是“同時活躍的調(diào)用棧幀數(shù)量”不是“累計創(chuàng)建的棧幀總數(shù)”。遞歸調(diào)用fib(n)時fib(n)會先調(diào)用fib(n-1)fib(n-1)再調(diào)用fib(n-2)一路到底棧深最大只有n層。等fib(n-1)整棵子樹算完棧才逐步回收然后才開始算fib(n-2)分支。因此同一時刻棧上最多同時存在n個幀空間O(n)。同理二叉樹遞歸DFS的空間復(fù)雜度是O(h)h為樹高不是O(節(jié)點總數(shù))。只有最壞情況下樹退化成鏈表h才等于n。理解“峰值同時占用”這一點是空間復(fù)雜度分析的分水嶺。3.3 用空間換時間的經(jīng)典權(quán)衡空間復(fù)雜度和時間復(fù)雜度的關(guān)系不是對立的“空間換時間”是工程里每天都在做的交易。最典型的就是緩存計算結(jié)果學(xué)名記憶化。斐波那契樸素遞歸是O(2?)時間加一個哈希表緩存已算過的值每個子問題只算一次時間降到O(n)空間付出O(n)。這個交易幾乎是穩(wěn)賺的因為指數(shù)級時間不可能接受而O(n)內(nèi)存通常還能扛。再看前綴和數(shù)組。給定一個數(shù)組要求大量區(qū)間和查詢。每次查詢直接遍歷區(qū)間長度是O(n)但預(yù)處理一個前綴和數(shù)組查詢變成O(1)——兩個前綴和相減即可代價是O(n)的預(yù)處理空間。在“讀多寫少”的場景這筆交易非常劃算。這種權(quán)衡沒有標(biāo)準(zhǔn)答案完全取決于數(shù)據(jù)規(guī)模、機器資源和訪問模式。讀者需要養(yǎng)成一個習(xí)慣任何優(yōu)化都會引入某種成本拿到一個新方案先別急著夸問一句“它多了什么成本值得嗎”。4. 復(fù)雜度分析中四個最陰的坑4.1 最好情況、最壞情況與平均情況的偷換快排的復(fù)雜度最常被說錯。很多人張口就是“快排O(n log n)”但嚴(yán)格說快排平均情況O(n log n)最壞情況O(n2)。當(dāng)分區(qū)每次選到極不均衡的pivot時遞歸退化成n層每層O(n)合計O(n2)。這句話不是摳字眼而是直接關(guān)系到生產(chǎn)系統(tǒng)的穩(wěn)定性——在一份幾乎有序的數(shù)據(jù)上做某基礎(chǔ)版快排可能真的跑出O(n2)。插入排序正好是反例最壞O(n2)但最好情況——數(shù)據(jù)幾乎有序時——是O(n)。面試?yán)飭栠@個問題通常就是想考察你能不能區(qū)分最好和最壞。我給出的固定建議是凡是報告復(fù)雜度一定標(biāo)明“最壞”“平均”還是“最好”不標(biāo)就是耍流氓。大多數(shù)業(yè)務(wù)場景關(guān)心的是最壞情況因為這決定系統(tǒng)的上限少數(shù)實時流式場景會關(guān)心平均但那是例外。4.2 輸入規(guī)模定義不清結(jié)論完全相反復(fù)雜度分析里最隱蔽的錯誤是沒定義清楚“n是什么”。同樣一個算法n的定義一變復(fù)雜度結(jié)論就可能完全不同。舉一個我們?nèi)粘Ｔu審里真實出現(xiàn)過的例子。有人寫了一個判斷字符串中所有字符是否唯一的函數(shù)用了哈希集合自認(rèn)為O(n)這里的n是字符串長度。這個結(jié)論沒錯。但如果n定義為“字符串的長度”而字符取值范圍是固定的256或Unicode碼點集合那哈希集合最多占用字符集大小K時間上界也可以寫成O(min(n, K))。嚴(yán)格分析甚至可以認(rèn)為哈希部分是O(K)因為你最多遇到K個不同字符。關(guān)鍵不在結(jié)論誰對而在于討論時必須先鎖定n指的是什么。圖算法里這個坑更明顯。圖的遍歷復(fù)雜度通常寫O(VE)V是頂點數(shù)E是邊數(shù)。如果只說O(n)別人根本不知道n是頂點還是邊稀疏圖和稠密圖的結(jié)論完全不同。我個人的習(xí)慣是代碼注釋里直接寫“這里的n指數(shù)組長度”或“這里V為頂點數(shù)、E為邊數(shù)”把變量定義釘死在代碼旁邊。4.3 均攤與平均兩個聽起來像卻不一樣的東西動態(tài)數(shù)組的append操作是個經(jīng)典案例。arr [] for i in range(n): arr.append(i)單個append操作最好情況O(1)——數(shù)組尾部還有空位直接寫入。但數(shù)組滿了再append時需要擴(kuò)容通常是申請一個兩倍大小的新數(shù)組把舊數(shù)據(jù)全部搬過去這次操作O(k)k是當(dāng)前長度。如果簡單取平均會以為每個append平均O(1)理由是“偶爾一次O(k)但k的間隔越來越長”這個直覺方向?qū)Φ珖?yán)格說法是均攤O(1)。均攤分析和平均分析是兩回事。平均分析討論的是操作序列在概率分布下的期望成本可能依賴輸入分布假設(shè)均攤分析是確定性結(jié)論它保證對任意n次操作序列總代價是O(n)所以單次均攤O(1)。這個區(qū)別不搞清楚在分析哈希表、動態(tài)數(shù)組、某些并發(fā)隊列時就會翻車。理解均攤需要按“還債”的視角看擴(kuò)容時每次搬遷的元素數(shù)量是O(k)但這些成本可以攤到前面k/2次便宜的append上所以每個append“欠”常數(shù)成本最終均攤O(1)。4.4 遞歸空間復(fù)雜度算錯最后一個坑也是我在代碼評審里見到頻率最高的遞歸版本的空間復(fù)雜度算錯。常見錯誤是把遞歸空間當(dāng)成“遞歸調(diào)用總數(shù)”或者“所有遞歸路徑上的臨時數(shù)據(jù)相加”。正確口徑是遞歸深度也就是調(diào)用棧最深的層數(shù)。舉個例子遞歸實現(xiàn)二叉樹后序遍歷空間復(fù)雜度O(h)h是樹高。如果每層遞歸都拷貝一份長度為n的數(shù)組作為參數(shù)傳遞那每層額外空間是O(n)恰好有h層總空間變成O(n×h)。當(dāng)樹接近滿二叉樹時hlog n乘積是O(n log n)這個開銷常被人忽視當(dāng)樹退化成鏈表hn空間直接O(n2)程序在數(shù)據(jù)稍大時就崩給你看。排查這類問題先看遞歸深度再看每層是否有額外分配兩層相乘才是遞歸空間。5. 工程里的復(fù)雜度怎么把紙面分析變成取舍決策5.1 數(shù)據(jù)規(guī)模沒到閾值時常數(shù)項才是老大復(fù)雜度只描述增長趨勢它會主動忽略常數(shù)因子。但工程里常數(shù)因子決定“當(dāng)下”跑得快不快。n很小的時候O(n2)可能比O(n log n)快得多因為前者常數(shù)小、實現(xiàn)簡單、分支少。比如經(jīng)典排序里的插入排序在n小于十幾二十的時候往往是最快的很多生產(chǎn)級快排實現(xiàn)會在遞歸到小區(qū)間時改用插入排序就是拿“漸近復(fù)雜度稍差但常數(shù)小”來換實際速度。所以我的經(jīng)驗是動手優(yōu)化之前先估n的量級。n是幾十O(n2)完全無所謂n是幾十萬O(n2)基本不可接受n是上千萬連O(n log n)都要仔細(xì)掂量常數(shù)。很多人一看到O(n2)就神經(jīng)緊張一看到O(1)就放心但真實世界還要問一句這個O(1)的常數(shù)是多少哈希函數(shù)本身的計算成本、內(nèi)存隨機訪問的成本都可能讓一個理論O(1)的操作在實際工程里不如線性掃描快。5.2 復(fù)雜度之外的三個隱性成本等你能熟練分析時間和空間復(fù)雜度之后真正決定算法選型的往往是三個復(fù)雜度“管不到”的東西。第一個是常數(shù)因子。哈希表查找是O(1)但一次哈希計算要做好幾次位運算和取模比較字符串的復(fù)雜度也不低而有序數(shù)組的二分查找O(log n)實際可能因為內(nèi)存順序訪問更快。常數(shù)差異在百萬級數(shù)據(jù)下可能就有幾倍差距。第二個是緩存局部性。數(shù)組是連續(xù)內(nèi)存遍歷時CPU緩存命中率高鏈表每個節(jié)點分散在堆里遍歷時頻繁換緩存行同樣O(n)的遍歷鏈表可能慢一個量級。復(fù)雜度分析看不見緩存工程性能卻嚴(yán)重依賴緩存。第三個是實現(xiàn)與維護(hù)成本。一個晦澀的O(1)結(jié)構(gòu)和一個清晰明了的O(log n)結(jié)構(gòu)放在團(tuán)隊代碼里后者的長期價值往往更高。算法效率的黃金標(biāo)準(zhǔn)是用來幫你決策的不是用來炫技的。我見過太多為省幾個毫秒寫出無人能維護(hù)的代碼最后重構(gòu)成本遠(yuǎn)遠(yuǎn)超過性能收益。在這三個隱性成本之上還有一個更根本的問題你連復(fù)雜度都沒分析清楚就去“優(yōu)化”是在浪費大家時間。所以我現(xiàn)在做評審要求匯報的人至少說清三件事——n是什么、最壞還是平均、常數(shù)大概什么水平。說清楚這三件事一個有經(jīng)驗的工程師基本就能判斷方案是否值得上了。最后說點實操體會我自己用這套方法久了最大的感受是復(fù)雜度分析不是用來背的是用來“估”的。拿到一個需求先在腦子里過一遍數(shù)據(jù)規(guī)模粗略估算幾種方案的復(fù)雜度優(yōu)化收益的上限就清楚了。很多時候做完這一步就已經(jīng)知道該不該動手寫代碼。另外養(yǎng)成了一個習(xí)慣每個關(guān)鍵函數(shù)的注釋里直接寫“時間O(x)、空間O(y)n指什么”。這行字看著簡單卻幫團(tuán)隊避免過大量因為“n定義不清”導(dǎo)致的爭論。也建議讀到這里的同學(xué)下次寫完一個有點繞的算法先別急著提交自己默算一遍時間復(fù)雜度和額外空間然后把口徑標(biāo)在注釋里。這個動作堅持三個月你對復(fù)雜度的直覺會準(zhǔn)很多。