1. 項(xiàng)目概述為什么算法分析是程序員的“內(nèi)功心法”剛?cè)胄袑?xiě)代碼那會(huì)兒我總覺(jué)得能把功能跑通就是勝利。一個(gè)排序功能管它是冒泡還是快排能排出來(lái)就行。直到有一次我寫(xiě)了個(gè)處理幾萬(wàn)條數(shù)據(jù)的循環(huán)在本地測(cè)試時(shí)一切安好一上線(xiàn)服務(wù)器就直接卡死CPU占用率飆升。排查了半天才發(fā)現(xiàn)是算法的時(shí)間復(fù)雜度太高數(shù)據(jù)量稍大就扛不住了。那次教訓(xùn)讓我深刻明白算法分析絕不是課本上枯燥的數(shù)學(xué)推導(dǎo)而是決定你寫(xiě)的代碼是“玩具”還是“工業(yè)級(jí)產(chǎn)品”的關(guān)鍵。它就像武俠小說(shuō)里的內(nèi)功心法招式具體代碼再花哨沒(méi)有深厚的內(nèi)力高效的算法設(shè)計(jì)實(shí)戰(zhàn)中一碰就倒。今天我們就來(lái)聊聊《數(shù)據(jù)結(jié)構(gòu)》學(xué)習(xí)中這個(gè)至關(guān)重要的環(huán)節(jié)——算法分析。很多人覺(jué)得它抽象、難懂甚至想跳過(guò)。但我的經(jīng)驗(yàn)是恰恰是這部分內(nèi)容能幫你建立起對(duì)程序性能的直覺(jué)。所謂算法分析核心就是回答兩個(gè)問(wèn)題這個(gè)算法跑得快不快時(shí)間復(fù)雜度以及這個(gè)算法占用的內(nèi)存多不多空間復(fù)雜度我們不是為了分析而分析最終目的是為了在眾多解決方案中為特定場(chǎng)景選擇一個(gè)最“經(jīng)濟(jì)實(shí)惠”的。比如給你一個(gè)只有10個(gè)數(shù)字的列表排序你用最慢的算法可能用戶(hù)都感知不到差別但如果是一個(gè)擁有百萬(wàn)用戶(hù)的App要在瞬間為每個(gè)人推薦內(nèi)容算法效率差一點(diǎn)點(diǎn)帶來(lái)的服務(wù)器成本和用戶(hù)體驗(yàn)下滑都是災(zāi)難性的。接下來(lái)的內(nèi)容我會(huì)拋開(kāi)教科書(shū)上復(fù)雜的數(shù)學(xué)證明用一個(gè)從業(yè)者的視角帶你重新理解算法分析。我們會(huì)從最樸素的想法出發(fā)一步步拆解時(shí)間復(fù)雜度和空間復(fù)雜度的概念并通過(guò)大量你未來(lái)工作中一定會(huì)遇到的真實(shí)場(chǎng)景比如數(shù)組查找、數(shù)據(jù)排序、緩存設(shè)計(jì)來(lái)鞏固理解。無(wú)論你是正在啃《數(shù)據(jù)結(jié)構(gòu)》的學(xué)生還是想補(bǔ)足基礎(chǔ)的在職開(kāi)發(fā)者相信這篇結(jié)合了理論、實(shí)操和踩坑經(jīng)驗(yàn)的總結(jié)都能讓你對(duì)“代碼性能”這件事有一個(gè)脫胎換骨的認(rèn)識(shí)。2. 核心概念拆解時(shí)間與空間程序的兩大“硬成本”在開(kāi)始分析之前我們必須統(tǒng)一“度量衡”。你不能說(shuō)“我這個(gè)算法感覺(jué)挺快的”我需要知道它具體有多快以及這種“快”的代價(jià)是什么。這就引出了算法分析的兩大核心維度時(shí)間復(fù)雜度和空間復(fù)雜度。它們共同構(gòu)成了評(píng)估算法優(yōu)劣的基石。2.1 時(shí)間復(fù)雜度你的代碼要“等”多久時(shí)間復(fù)雜度描述的并不是代碼運(yùn)行的具體秒數(shù)因?yàn)槟侨Q于你的電腦CPU是i5還是i9是本地測(cè)試還是云端服務(wù)器。它描述的是算法的執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)。這是一種抽象的、與機(jī)器無(wú)關(guān)的性能描述。我們用一個(gè)最簡(jiǎn)單的例子來(lái)感受一下。假設(shè)你要在一個(gè)包含n個(gè)元素的數(shù)組里查找某個(gè)特定的值。場(chǎng)景一順序查找你從第一個(gè)元素開(kāi)始一個(gè)一個(gè)往后看直到找到目標(biāo)或看完所有元素。最壞的情況是目標(biāo)在最后一個(gè)或者根本不存在這時(shí)你需要查看整個(gè)數(shù)組也就是進(jìn)行n次操作。我們說(shuō)這個(gè)算法的時(shí)間復(fù)雜度是O(n)。這里的“O”讀作“大O”是一種表示漸進(jìn)趨勢(shì)的符號(hào)。O(n)意味著當(dāng)數(shù)據(jù)量n翻倍時(shí)最壞情況下所需的操作次數(shù)也大致翻倍。這是一種線(xiàn)性增長(zhǎng)關(guān)系。場(chǎng)景二二分查找假設(shè)數(shù)組已排序你不需要傻傻地一個(gè)個(gè)找。你可以先看中間的元素如果目標(biāo)比中間值大你就知道目標(biāo)只可能在后半部分于是直接拋棄前半部分反之亦然。然后你在剩下的一半里重復(fù)這個(gè)過(guò)程。每次比較都能排除掉一半的數(shù)據(jù)。在最壞情況下你需要將數(shù)據(jù)規(guī)模除以2直到只剩下1個(gè)元素。這個(gè)“除以2”的過(guò)程能進(jìn)行多少次呢?cái)?shù)學(xué)上就是 log?n 次。所以它的時(shí)間復(fù)雜度是O(log n)。當(dāng)數(shù)據(jù)量n從1000增長(zhǎng)到100萬(wàn)翻了1000倍O(n)算法的工作量也翻了1000倍而O(log n)算法的工作量大約只增加了 log?(1000000) - log?(1000) ≈ 20 - 10 10倍優(yōu)勢(shì)是碾壓性的。注意大O表示法關(guān)注的是最壞情況或平均情況下的增長(zhǎng)趨勢(shì)它會(huì)忽略常數(shù)因子和低階項(xiàng)。比如一個(gè)算法需要3n 100次操作另一個(gè)需要5n 20次操作雖然具體數(shù)值不同但它們的增長(zhǎng)趨勢(shì)都是由n決定的所以我們都記作 O(n)。當(dāng)n非常大時(shí)常數(shù)和低階項(xiàng)的影響就微乎其微了。2.2 空間復(fù)雜度你的代碼要“占”多大地方空間復(fù)雜度衡量的是算法在運(yùn)行過(guò)程中為了解決問(wèn)題而臨時(shí)占用的存儲(chǔ)空間大小不包括原始輸入數(shù)據(jù)占用的空間同樣隨著數(shù)據(jù)規(guī)模n的變化趨勢(shì)。它主要關(guān)注兩個(gè)方面算法本身占用的空間主要是代碼和常量。算法運(yùn)行過(guò)程中產(chǎn)生的額外空間這是分析的重點(diǎn)比如你聲明的變量、數(shù)組、遞歸調(diào)用棧等。繼續(xù)用上面的例子順序查找除了那個(gè)遍歷用的索引變量i它幾乎不需要任何額外空間。無(wú)論數(shù)組有多大我只需要一個(gè)固定大小的變量。所以它的空間復(fù)雜度是O(1)我們稱(chēng)之為“常數(shù)空間”。二分查找遞歸實(shí)現(xiàn)雖然每次查找范圍減半但遞歸函數(shù)調(diào)用會(huì)在內(nèi)存棧中保存每一層的信息如參數(shù)、返回地址。在最壞情況下這個(gè)棧的深度大約是 log?n。所以它的空間復(fù)雜度是O(log n)。如果使用循環(huán)而非遞歸來(lái)實(shí)現(xiàn)二分查找則可以做到 O(1) 的空間復(fù)雜度。這里有一個(gè)非常經(jīng)典的權(quán)衡空間換時(shí)間。有時(shí)我們可以通過(guò)使用更多的內(nèi)存來(lái)顯著降低運(yùn)行時(shí)間。實(shí)操心得在我早期的一個(gè)項(xiàng)目中需要頻繁檢查一個(gè)用戶(hù)ID是否存在于一個(gè)巨大的列表中。最初我使用數(shù)組順序查找O(n)的時(shí)間復(fù)雜度讓接口響應(yīng)慢得無(wú)法接受。后來(lái)我將其改為使用哈希表Hash Table。雖然哈希表本身需要 O(n) 的額外空間來(lái)存儲(chǔ)數(shù)據(jù)但查詢(xún)一個(gè)ID是否存在的時(shí)間復(fù)雜度平均可以降到 O(1)。這就是一個(gè)典型的“用空間換時(shí)間”的策略用多一點(diǎn)的內(nèi)存換來(lái)了響應(yīng)速度質(zhì)的飛躍對(duì)于高并發(fā)服務(wù)來(lái)說(shuō)是絕對(duì)值得的。3. 常見(jiàn)時(shí)間復(fù)雜度深度解析與實(shí)戰(zhàn)場(chǎng)景理解了基本概念后我們來(lái)看看在實(shí)戰(zhàn)中那些常見(jiàn)的時(shí)間復(fù)雜度等級(jí)到底意味著什么以及它們對(duì)應(yīng)的典型算法。我會(huì)用一個(gè)簡(jiǎn)單的任務(wù)來(lái)貫穿始終“我有一個(gè)包含n個(gè)元素的數(shù)組請(qǐng)?jiān)O(shè)計(jì)算法處理它?！?.1 O(1) - 常數(shù)時(shí)間與數(shù)據(jù)量無(wú)關(guān)的操作這是效率的極致。無(wú)論你的數(shù)組有10個(gè)元素還是10億個(gè)元素O(1)的操作都只花費(fèi)固定的時(shí)間。典型操作訪(fǎng)問(wèn)數(shù)組的某個(gè)索引的元素arr[5]在哈希表中插入或查找一個(gè)鍵值對(duì)平均情況執(zhí)行一次算術(shù)運(yùn)算或邏輯比較實(shí)戰(zhàn)場(chǎng)景 假設(shè)你設(shè)計(jì)了一個(gè)用戶(hù)系統(tǒng)每個(gè)用戶(hù)有一個(gè)唯一的數(shù)字ID。你將用戶(hù)對(duì)象存儲(chǔ)在一個(gè)數(shù)組中但用戶(hù)ID非常稀疏比如有用戶(hù)ID為1, 10005, 300002。如果你直接用ID作為數(shù)組索引來(lái)存取用戶(hù)userArray[10005]那么這就是O(1)的訪(fǎng)問(wèn)。但代價(jià)是數(shù)組中間會(huì)有大量空位浪費(fèi)了巨大空間。這又是一個(gè)極端的“空間換時(shí)間”案例在實(shí)際中需要謹(jǐn)慎權(quán)衡。3.2 O(log n) - 對(duì)數(shù)時(shí)間效率的“魔法”就像二分查找這是處理大規(guī)模數(shù)據(jù)時(shí)夢(mèng)寐以求的效率。每次操作都能將問(wèn)題規(guī)模削減一個(gè)比例通常是減半。典型算法二分查找在有序數(shù)組中平衡二叉搜索樹(shù)如AVL樹(shù)、紅黑樹(shù)的查找、插入、刪除操作實(shí)戰(zhàn)場(chǎng)景 現(xiàn)代數(shù)據(jù)庫(kù)的索引如B樹(shù)索引核心原理就是基于O(log n)的查找效率。當(dāng)你的數(shù)據(jù)表有上億行記錄時(shí)如果沒(méi)有索引一個(gè)SELECT * FROM users WHERE id 123456的查詢(xún)可能需要全表掃描O(n)耗時(shí)無(wú)法想象。而通過(guò)在id字段建立B樹(shù)索引數(shù)據(jù)庫(kù)能快速將查找路徑收斂到少數(shù)幾個(gè)磁盤(pán)頁(yè)效率提升成千上萬(wàn)倍。注意O(log n)算法通常要求數(shù)據(jù)是有序的或者本身具有某種結(jié)構(gòu)如樹(shù)。構(gòu)建這種結(jié)構(gòu)本身可能需要成本如排序的O(n log n)但對(duì)于需要頻繁查詢(xún)的場(chǎng)景前期的一次性投入是完全值得的。3.3 O(n) - 線(xiàn)性時(shí)間最直觀(guān)的“一分耕耘一分收獲”操作次數(shù)與數(shù)據(jù)量成正比。這是許多基礎(chǔ)算法和簡(jiǎn)單任務(wù)的復(fù)雜度。典型算法遍歷數(shù)組、鏈表在無(wú)序數(shù)組中查找最大值/最小值計(jì)數(shù)排序、桶排序特定條件下實(shí)戰(zhàn)場(chǎng)景 你的后端接收到一個(gè)請(qǐng)求需要將用戶(hù)提交的訂單列表包含n個(gè)商品依次進(jìn)行庫(kù)存檢查、價(jià)格計(jì)算。這個(gè)過(guò)程你必須處理每一個(gè)商品無(wú)法跳過(guò)任何一個(gè)。那么這個(gè)處理流程的時(shí)間復(fù)雜度就是O(n)。優(yōu)化思路不在于改變O(n)本身而在于降低處理每個(gè)商品的單位時(shí)間成本比如使用更高效的數(shù)據(jù)庫(kù)查詢(xún)、引入緩存等。3.4 O(n log n) - 線(xiàn)性對(duì)數(shù)時(shí)間高效排序的“黃金標(biāo)準(zhǔn)”這是目前基于比較的排序算法所能達(dá)到的理論最優(yōu)平均時(shí)間復(fù)雜度。它比O(n2)好得多又比O(n)稍差是處理大規(guī)模數(shù)據(jù)排序時(shí)最常用的復(fù)雜度等級(jí)。典型算法快速排序平均情況歸并排序堆排序?yàn)槭裁词桥判虻摹疤旎ò濉笨梢灾庇^(guān)理解排序的本質(zhì)是確定n個(gè)元素的唯一正確順序。每次比較兩個(gè)元素只能得到“大于”或“小于”一個(gè)比特的信息。要完全確定n個(gè)元素的排列所需的信息量大約是 log?(n!) 比特。根據(jù)斯特林公式log?(n!) 的增長(zhǎng)速度與 n log n 同階。因此基于比較的排序算法其時(shí)間復(fù)雜度下界就是 Ω(n log n)。實(shí)戰(zhàn)場(chǎng)景 幾乎任何需要處理有序數(shù)據(jù)的場(chǎng)景都離不開(kāi)它。例如你的App有一個(gè)“按價(jià)格從低到高”展示商品列表的功能。當(dāng)后臺(tái)商品數(shù)據(jù)更新時(shí)你需要對(duì)它們按價(jià)格排序。如果使用冒泡排序O(n2)一萬(wàn)件商品可能就會(huì)讓服務(wù)響應(yīng)遲緩。而換成快速排序O(n log n)十萬(wàn)件商品也能輕松應(yīng)對(duì)。在JavaScript中數(shù)組的.sort()方法現(xiàn)代瀏覽器引擎如V8內(nèi)部就采用了TimSort一種混合了歸并和插入排序的算法來(lái)保證O(n log n)的效率。3.5 O(n2) - 平方時(shí)間小數(shù)據(jù)可行大數(shù)據(jù)“災(zāi)難”當(dāng)數(shù)據(jù)量n翻倍時(shí)操作次數(shù)會(huì)變?yōu)樵瓉?lái)的4倍。這是一個(gè)需要警惕的信號(hào)意味著算法可能無(wú)法很好地?cái)U(kuò)展到大數(shù)據(jù)集。典型算法冒泡排序、選擇排序、插入排序最壞或平均情況用兩層嵌套循環(huán)遍歷二維數(shù)組的所有元素實(shí)戰(zhàn)場(chǎng)景與避坑 我見(jiàn)過(guò)一個(gè)經(jīng)典的性能問(wèn)題在循環(huán)內(nèi)部進(jìn)行重復(fù)的數(shù)組查找。// 低效的 O(n2) 示例 function findPairsWithSum(arr, targetSum) { let pairs []; for (let i 0; i arr.length; i) { for (let j i 1; j arr.length; j) { // 嵌套循環(huán) if (arr[i] arr[j] targetSum) { pairs.push([arr[i], arr[j]]); } } } return pairs; }這段代碼尋找數(shù)組中所有和為特定值的數(shù)對(duì)。兩層嵌套循環(huán)導(dǎo)致了O(n2)的復(fù)雜度。當(dāng)數(shù)組有1000個(gè)元素時(shí)最內(nèi)層的if判斷要執(zhí)行大約50萬(wàn)次當(dāng)元素達(dá)到1萬(wàn)個(gè)時(shí)執(zhí)行次數(shù)激增到約5000萬(wàn)次對(duì)于前端或?qū)憫?yīng)時(shí)間敏感的服務(wù)這幾乎是不可接受的。優(yōu)化方案通?？梢允褂谩翱臻g換時(shí)間”將其優(yōu)化到O(n)。對(duì)于上面的找數(shù)對(duì)問(wèn)題我們可以只遍歷一次數(shù)組并用一個(gè)哈希集合Set來(lái)記錄已經(jīng)遍歷過(guò)的數(shù)。// 優(yōu)化的 O(n) 示例 function findPairsWithSumOptimized(arr, targetSum) { let seen new Set(); let pairs []; for (let num of arr) { let complement targetSum - num; if (seen.has(complement)) { // Set的has操作平均是O(1) pairs.push([complement, num]); } seen.add(num); } return pairs; }這樣我們只需要一次遍歷O(n)每次查詢(xún)seen集合是近似O(1)的操作整體復(fù)雜度就降為了O(n)。代價(jià)是多使用了一個(gè)最多包含n個(gè)元素的Set空間復(fù)雜度從O(1)升到了O(n)。4. 空間復(fù)雜度實(shí)戰(zhàn)分析與內(nèi)存管理技巧理解了時(shí)間復(fù)雜度空間復(fù)雜度的分析就相對(duì)直觀(guān)但它同樣重要尤其是在內(nèi)存受限的環(huán)境如嵌入式設(shè)備、移動(dòng)端App或處理超大規(guī)模數(shù)據(jù)時(shí)。4.1 常見(jiàn)空間復(fù)雜度等級(jí)O(1) - 原地算法算法運(yùn)行所需的額外空間是固定的與輸入數(shù)據(jù)規(guī)模n無(wú)關(guān)。例如冒泡排序、選擇排序只需要幾個(gè)臨時(shí)變量是典型的原地排序算法。O(n)算法需要額外空間與輸入規(guī)模成線(xiàn)性關(guān)系。例如歸并排序在合并時(shí)需要一個(gè)新的數(shù)組來(lái)存放中間結(jié)果將鏈表轉(zhuǎn)換為數(shù)組存儲(chǔ)也屬于此類(lèi)。O(n2)比較少見(jiàn)通常出現(xiàn)在生成一個(gè)二維結(jié)構(gòu)如n*n的矩陣時(shí)。4.2 遞歸算法的空間開(kāi)銷(xiāo)陷阱遞歸代碼簡(jiǎn)潔優(yōu)雅但其空間開(kāi)銷(xiāo)常被忽略。每次遞歸調(diào)用都會(huì)在內(nèi)存的調(diào)用棧中壓入一幀用于保存參數(shù)、局部變量和返回地址。因此遞歸算法的空間復(fù)雜度至少是O(遞歸深度)。反面案例計(jì)算斐波那契數(shù)列def fib(n): if n 1: return n return fib(n-1) fib(n-2)這是一個(gè)經(jīng)典的、低效的遞歸實(shí)現(xiàn)。它的時(shí)間復(fù)雜度是指數(shù)級(jí)的O(2?)更糟糕的是由于遞歸樹(shù)的最大深度是n在最壞情況下雖然由于遞歸展開(kāi)方式實(shí)際棧深度是n空間復(fù)雜度是O(n)。計(jì)算fib(40)可能就需要數(shù)億次操作并且消耗可觀(guān)的棧空間。優(yōu)化方案動(dòng)態(tài)規(guī)劃迭代使用兩個(gè)變量從底向上計(jì)算空間復(fù)雜度O(1)。def fib_iterative(n): if n 1: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b帶備忘錄的遞歸記憶化搜索仍然用遞歸但用一個(gè)數(shù)組或字典緩存已計(jì)算的結(jié)果避免重復(fù)計(jì)算。時(shí)間復(fù)雜度降為O(n)空間復(fù)雜度為O(n)用于存儲(chǔ)緩存和遞歸棧。實(shí)操心得在Web開(kāi)發(fā)中過(guò)深的遞歸調(diào)用可能導(dǎo)致“棧溢出”錯(cuò)誤。特別是在處理像深度嵌套的樹(shù)形結(jié)構(gòu)數(shù)據(jù)如評(píng)論樓中樓、組織架構(gòu)樹(shù)進(jìn)行遞歸遍歷時(shí)一定要預(yù)估數(shù)據(jù)的最大深度。如果深度不可控考慮使用顯式的棧Stack數(shù)據(jù)結(jié)構(gòu)進(jìn)行迭代遍歷將遞歸轉(zhuǎn)化為循環(huán)這樣可以完全由你控制內(nèi)存的使用避免棧溢出風(fēng)險(xiǎn)。4.3 數(shù)據(jù)結(jié)構(gòu)的空間效率選擇選擇不同的數(shù)據(jù)結(jié)構(gòu)對(duì)空間復(fù)雜度的影響巨大。數(shù)組 vs 鏈表數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)除了數(shù)據(jù)本身幾乎無(wú)額外開(kāi)銷(xiāo)但大小固定或動(dòng)態(tài)擴(kuò)容有成本。鏈表的每個(gè)節(jié)點(diǎn)除了數(shù)據(jù)還需要至少一個(gè)指針8字節(jié)指向下一個(gè)節(jié)點(diǎn)存儲(chǔ)相同數(shù)量數(shù)據(jù)時(shí)鏈表的內(nèi)存開(kāi)銷(xiāo)更大。哈希表為了實(shí)現(xiàn)O(1)的平均訪(fǎng)問(wèn)哈希表通常不會(huì)裝滿(mǎn)會(huì)保持一定的“負(fù)載因子”比如75%。這意味著一個(gè)有n個(gè)元素的哈希表其底層數(shù)組容量可能是 4n/3有部分空間是閑置的這是一種用空間換時(shí)間的策略。5. 綜合案例分析從理論到實(shí)踐的性能優(yōu)化我們來(lái)看一個(gè)綜合性的問(wèn)題體驗(yàn)一下如何運(yùn)用算法分析的思想來(lái)指導(dǎo)和優(yōu)化實(shí)際代碼。問(wèn)題給定一個(gè)字符串找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。示例 輸入“abcabcbb”輸出3解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是“abc”其長(zhǎng)度為 3。5.1 暴力解法Brute Force分析與實(shí)現(xiàn)最直觀(guān)的想法是檢查所有可能的子串。枚舉所有子串的起始索引i(0 到 n-1) 和結(jié)束索引j(i 到 n-1)。對(duì)于每個(gè)子串s[i...j]檢查其中是否有重復(fù)字符。如果沒(méi)有重復(fù)更新記錄的最大長(zhǎng)度。代碼實(shí)現(xiàn)Pythondef lengthOfLongestSubstring_brute(s: str) - int: n len(s) max_len 0 for i in range(n): for j in range(i, n): # 檢查子串 s[i..j] 是否有重復(fù) char_set set() has_duplicate False for k in range(i, j 1): if s[k] in char_set: has_duplicate True break char_set.add(s[k]) # 如果沒(méi)有重復(fù)更新最大長(zhǎng)度 if not has_duplicate: max_len max(max_len, j - i 1) return max_len復(fù)雜度分析時(shí)間復(fù)雜度三層循環(huán)。枚舉所有子串是 O(n2)對(duì)每個(gè)子串檢查重復(fù)字符最壞需要 O(子串長(zhǎng)度) ≈ O(n)。所以總時(shí)間復(fù)雜度是O(n3)。這是一個(gè)非常高的復(fù)雜度當(dāng)字符串長(zhǎng)度達(dá)到幾百時(shí)運(yùn)行時(shí)間就會(huì)變得很長(zhǎng)?？臻g復(fù)雜度在檢查每個(gè)子串時(shí)我們使用了一個(gè)集合char_set其大小最多為當(dāng)前子串的長(zhǎng)度即 O(n)。但由于它在每次內(nèi)層循環(huán)中都會(huì)被創(chuàng)建和銷(xiāo)毀所以整體上可以認(rèn)為是 O(n)但更精確地說(shuō)在任意時(shí)刻額外空間占用是 O(字符集大小)對(duì)于A(yíng)SCII字符集是 O(128) 或 O(256)是常數(shù)。這個(gè)解法在面試或?qū)嶋H工程中是完全不可接受的我們需要優(yōu)化。5.2 滑動(dòng)窗口Sliding Window優(yōu)化方案我們注意到在暴力解法中我們重復(fù)檢查了很多重疊的子串。例如檢查完s[i...j]后檢查s[i...j1]時(shí)我們完全重新掃描了整個(gè)s[i...j]部分。這是巨大的浪費(fèi)。優(yōu)化思路使用“滑動(dòng)窗口”。維護(hù)一個(gè)窗口[left, right]代表當(dāng)前考察的無(wú)重復(fù)子串。用一個(gè)哈希集合window_set來(lái)存儲(chǔ)窗口內(nèi)的字符保證無(wú)重復(fù)。將右指針right不斷向右移動(dòng)并將字符加入集合。如果發(fā)現(xiàn)即將加入的字符s[right]已經(jīng)在集合中說(shuō)明出現(xiàn)了重復(fù)。此時(shí)我們移動(dòng)左指針left向右直到將那個(gè)重復(fù)的字符移出窗口同時(shí)從集合中刪除然后才能將s[right]加入。在每一步窗口[left, right]都是一個(gè)無(wú)重復(fù)字符的子串我們記錄其長(zhǎng)度right - left 1并更新最大值。代碼實(shí)現(xiàn)def lengthOfLongestSubstring_sliding_window(s: str) - int: n len(s) char_set set() max_len 0 left 0 # 窗口左邊界 for right in range(n): # right是窗口右邊界 # 當(dāng)遇到重復(fù)字符時(shí)移動(dòng)左邊界直到重復(fù)被移除 while s[right] in char_set: char_set.remove(s[left]) left 1 # 將當(dāng)前字符加入窗口 char_set.add(s[right]) # 更新最大長(zhǎng)度 max_len max(max_len, right - left 1) return max_len復(fù)雜度分析時(shí)間復(fù)雜度雖然有一個(gè)while循環(huán)嵌套在for循環(huán)里但請(qǐng)注意左指針left和右指針right都只從 0 移動(dòng)到 n-1每個(gè)字符最多被左指針和右指針各訪(fǎng)問(wèn)一次加入集合一次從集合移除一次。因此總操作次數(shù)是 2n 這個(gè)量級(jí)時(shí)間復(fù)雜度是O(n)。相比 O(n3)這是指數(shù)級(jí)的提升?？臻g復(fù)雜度我們使用了一個(gè)哈希集合來(lái)存儲(chǔ)窗口內(nèi)的字符。在最壞情況下整個(gè)字符串都沒(méi)有重復(fù)如“abcdef”集合會(huì)存儲(chǔ)所有n個(gè)字符所以空間復(fù)雜度是O(n)。但更常見(jiàn)的是空間復(fù)雜度取決于字符集的大小可以認(rèn)為是 O(min(n, 字符集大小))。進(jìn)一步優(yōu)化使用哈希映射記錄索引 上面的滑動(dòng)窗口版本在發(fā)現(xiàn)重復(fù)時(shí)左指針left需要一步一步向右移動(dòng)。我們可以用哈希映射字典來(lái)記錄每個(gè)字符最近一次出現(xiàn)的位置。這樣當(dāng)遇到重復(fù)字符時(shí)我們可以直接將左指針跳到重復(fù)字符上次出現(xiàn)位置的下一個(gè)實(shí)現(xiàn)“跳躍式”移動(dòng)。def lengthOfLongestSubstring_optimized(s: str) - int: char_index_map {} # 存儲(chǔ)字符 - 該字符最近一次出現(xiàn)的索引 max_len 0 left 0 # 窗口左邊界 for right in range(len(s)): if s[right] in char_index_map: # 如果字符重復(fù)且其上次出現(xiàn)的位置在窗口內(nèi)則快速移動(dòng)左指針 # 使用max是為了防止左指針回退例如abba這種情況 left max(left, char_index_map[s[right]] 1) # 更新字符的最新索引 char_index_map[s[right]] right # 計(jì)算當(dāng)前窗口長(zhǎng)度 max_len max(max_len, right - left 1) return max_len這個(gè)版本的時(shí)間復(fù)雜度依然是 O(n)但內(nèi)部操作更少常數(shù)時(shí)間更優(yōu)。空間復(fù)雜度同樣是 O(min(n, 字符集大小))。5.3 案例總結(jié)與思維提煉從這個(gè)案例中我們可以提煉出算法優(yōu)化的一般思路從暴力解法開(kāi)始先想出一個(gè)能解決問(wèn)題的、最直觀(guān)的方法不要怕它慢。這是你的思考起點(diǎn)和性能基準(zhǔn)。分析瓶頸使用大O分析法找出暴力解法中時(shí)間復(fù)雜度最高的部分。在上例中是三重循環(huán)導(dǎo)致的 O(n3)。尋找冗余計(jì)算觀(guān)察暴力解法中是否進(jìn)行了大量重復(fù)的、不必要的計(jì)算?；瑒?dòng)窗口的核心洞察就是“避免重復(fù)檢查重疊子串”。利用數(shù)據(jù)結(jié)構(gòu)優(yōu)化思考是否能使用更高效的數(shù)據(jù)結(jié)構(gòu)如哈希集合、哈希映射來(lái)將某些 O(n) 的操作降為 O(1) 或 O(log n)?；瑒?dòng)窗口用集合來(lái)保證字符唯一性?xún)?yōu)化版用映射來(lái)快速定位重復(fù)字符的位置。權(quán)衡時(shí)空優(yōu)化后的算法空間復(fù)雜度從 O(1) 升到了 O(n)。在絕大多數(shù)現(xiàn)代應(yīng)用場(chǎng)景中用一定的內(nèi)存換取計(jì)算時(shí)間的大幅減少是非常劃算的交易。6. 算法分析在工程實(shí)踐中的常見(jiàn)誤區(qū)與排查技巧學(xué)完了理論最后分享幾個(gè)我在工程實(shí)踐中關(guān)于算法性能問(wèn)題排查和避免誤區(qū)的心得。6.1 誤區(qū)一忽視常數(shù)因子和低階項(xiàng)大O表示法忽略了常數(shù)和低階項(xiàng)這并不意味著它們?cè)诂F(xiàn)實(shí)中不重要。當(dāng)數(shù)據(jù)規(guī)模n較小時(shí)O(n2)的算法可能比O(n log n)的算法跑得更快因?yàn)楹笳叩某?shù)因子可能更大。實(shí)操建議對(duì)于性能關(guān)鍵的模塊特別是會(huì)被頻繁調(diào)用的小規(guī)模函數(shù)不能只看大O。需要進(jìn)行基準(zhǔn)測(cè)試Benchmark。例如在排序少量數(shù)據(jù)如幾十個(gè)元素時(shí)簡(jiǎn)單的插入排序O(n2)可能比快速排序O(n log n)更快因?yàn)榭焖倥判虻倪f歸調(diào)用、分區(qū)操作有額外的開(kāi)銷(xiāo)。這就是為什么很多語(yǔ)言標(biāo)準(zhǔn)庫(kù)的排序算法如Python的list.sort() Java的Arrays.sort()對(duì)于小數(shù)組會(huì)切換到插入排序。6.2 誤區(qū)二錯(cuò)誤估算數(shù)據(jù)規(guī)模與復(fù)雜度“這個(gè)功能現(xiàn)在數(shù)據(jù)量小先這樣寫(xiě)以后再說(shuō)?！边@是導(dǎo)致后期性能災(zāi)難的常見(jiàn)說(shuō)辭。你必須對(duì)業(yè)務(wù)數(shù)據(jù)規(guī)模有一個(gè)預(yù)估。排查案例我曾接手一個(gè)后臺(tái)任務(wù)用于生成用戶(hù)關(guān)系圖譜。最初的實(shí)現(xiàn)是雙重循環(huán)遍歷所有用戶(hù)對(duì)檢查他們是否有關(guān)聯(lián)O(n2)。在只有幾千個(gè)用戶(hù)的測(cè)試環(huán)境運(yùn)行很快。上線(xiàn)后用戶(hù)量增長(zhǎng)到十萬(wàn)級(jí)這個(gè)任務(wù)運(yùn)行一次需要數(shù)小時(shí)完全不可用。優(yōu)化方案是預(yù)先建立索引如使用鄰接表或倒排索引將關(guān)聯(lián)查詢(xún)降到 O(1) 或 O(log n)最終將任務(wù)時(shí)間壓縮到分鐘級(jí)。技巧在設(shè)計(jì)和評(píng)審算法時(shí)養(yǎng)成習(xí)慣問(wèn)“如果數(shù)據(jù)量增長(zhǎng)10倍、100倍這個(gè)方案還可行嗎”6.3 誤區(qū)三過(guò)度優(yōu)化與可讀性犧牲這是另一個(gè)極端。為了追求極致的理論復(fù)雜度寫(xiě)出極其晦澀難懂的代碼導(dǎo)致后期維護(hù)成本激增。原則“過(guò)早優(yōu)化是萬(wàn)惡之源”Donald Knuth。在大多數(shù)業(yè)務(wù)代碼中清晰、正確、可維護(hù)比那一點(diǎn)微小的性能提升更重要。除非你通過(guò)性能分析工具Profiler明確找到了系統(tǒng)的瓶頸Hot Path否則不要輕易對(duì)可讀性良好的代碼進(jìn)行復(fù)雜的“優(yōu)化”。經(jīng)驗(yàn)我通常會(huì)遵循以下步驟首先寫(xiě)出正確、清晰的代碼。然后進(jìn)行集成測(cè)試和壓力測(cè)試。如果發(fā)現(xiàn)性能不達(dá)標(biāo)使用性能分析工具定位瓶頸函數(shù)。針對(duì)瓶頸函數(shù)分析其時(shí)間復(fù)雜度并嘗試用更優(yōu)的算法或數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。優(yōu)化后必須進(jìn)行回歸測(cè)試確保功能正確并且性能提升是顯著的。6.4 常用性能排查工具與思路當(dāng)線(xiàn)上服務(wù)出現(xiàn)性能問(wèn)題時(shí)如何快速定位是否是算法復(fù)雜度問(wèn)題監(jiān)控與日志觀(guān)察CPU、內(nèi)存、響應(yīng)時(shí)間等指標(biāo)。如果響應(yīng)時(shí)間隨著請(qǐng)求數(shù)據(jù)量的增大呈非線(xiàn)性尤其是平方或指數(shù)增長(zhǎng)很可能是算法問(wèn)題。代碼審查重點(diǎn)審查循環(huán)嵌套特別是那些在循環(huán)內(nèi)部進(jìn)行數(shù)據(jù)庫(kù)查詢(xún)、網(wǎng)絡(luò)請(qǐng)求或復(fù)雜計(jì)算的代碼。一個(gè)O(n)的外部循環(huán)內(nèi)部套一個(gè)O(n)的查詢(xún)整體就是O(n2)。簡(jiǎn)化與測(cè)試將可疑代碼片段剝離出來(lái)用不同規(guī)模如1k, 10k, 100k條數(shù)據(jù)的測(cè)試數(shù)據(jù)進(jìn)行本地基準(zhǔn)測(cè)試觀(guān)察運(yùn)行時(shí)間增長(zhǎng)趨勢(shì)可以直觀(guān)驗(yàn)證時(shí)間復(fù)雜度。算法分析不是一門(mén)束之高閣的理論而是每天寫(xiě)代碼時(shí)都應(yīng)該有的思維習(xí)慣。它幫助你做出更明智的技術(shù)選型寫(xiě)出更能經(jīng)受規(guī)?？简?yàn)的程序。下次當(dāng)你寫(xiě)下for循環(huán)時(shí)不妨多想一秒這個(gè)循環(huán)會(huì)執(zhí)行多少次當(dāng)數(shù)據(jù)量翻十倍時(shí)它還能撐得住嗎這份直覺(jué)就是算法分析帶給程序員最寶貴的財(cái)富。