簡(jiǎn)介本資源是一份面向計(jì)算機(jī)專業(yè)學(xué)生與考研備考者的《數(shù)據(jù)結(jié)構(gòu)》核心知識(shí)點(diǎn)精要總結(jié)聚焦課程基礎(chǔ)概念、邏輯與存儲(chǔ)結(jié)構(gòu)、典型運(yùn)算及算法復(fù)雜度分析等高頻考點(diǎn)。內(nèi)容覆蓋概論、線性表、棧與隊(duì)列三大核心章節(jié)系統(tǒng)梳理數(shù)據(jù)元素/數(shù)據(jù)項(xiàng)定義、ADT抽象思想、順序/鏈?zhǔn)?索引/散列四種存儲(chǔ)結(jié)構(gòu)對(duì)比、時(shí)間與空間復(fù)雜度階的判定方法以及順序表與各類鏈表單鏈表、雙鏈表、循環(huán)鏈表的操作原理與效率分析。資源為1個(gè)PDF文件體積僅205KB輕量便攜適合作為考前速記手冊(cè)或課堂筆記補(bǔ)充。目前已有438人學(xué)習(xí)下載內(nèi)容條理清晰、術(shù)語(yǔ)準(zhǔn)確、公式與偽代碼標(biāo)注規(guī)范可直接用于知識(shí)復(fù)盤、面試突擊與算法基礎(chǔ)夯實(shí)。1. 這不是“復(fù)習(xí)提綱”而是一份能直接塞進(jìn)考試前3小時(shí)、面試前15分鐘、debug卡殼時(shí)甩開IDE翻兩頁(yè)就醒腦的「數(shù)據(jù)結(jié)構(gòu)實(shí)戰(zhàn)速查手冊(cè)」你有沒有過(guò)這種時(shí)刻寫鏈表反轉(zhuǎn)時(shí)突然卡殼不確定prev curr; curr next;和curr.next prev誰(shuí)該在前調(diào)試哈夫曼編碼發(fā)現(xiàn)生成的碼字里有001和0010——這根本不是前綴碼但手算又看不出哪步錯(cuò)了看到“堆排序建堆從i (n-2)//2開始”這句話下意識(shí)點(diǎn)開編輯器想驗(yàn)證卻連n8時(shí)第一個(gè)非葉子節(jié)點(diǎn)到底是索引 3 還是 4 都要畫樹再數(shù)一遍或者更現(xiàn)實(shí)一點(diǎn)明天早八《數(shù)據(jù)結(jié)構(gòu)》期末考你剛合上王道單科打開這份 PDF發(fā)現(xiàn)它沒講紅黑樹沒貼 LeetCode 題號(hào)沒帶動(dòng)畫演示——但它把「順序表插入平均移動(dòng) n/2 個(gè)元素」寫成了LOCa(i) LOCa(1) (i-1)*d的推導(dǎo)起點(diǎn)把「循環(huán)隊(duì)列判空判滿的三種方法」并排列成表格把「Dijkstra 和 Prim 的偽代碼差異」用同一套變量名對(duì)齊排版……這就是《數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié).pdf》的真實(shí)定位它不教你怎么“理解”它逼你“記住動(dòng)作”。它不是給零基礎(chǔ)小白看的入門課件而是給已經(jīng)敲過(guò)鏈表、跑過(guò) DFS、被哈希沖突坑過(guò)的實(shí)操者準(zhǔn)備的「肌肉記憶校準(zhǔn)器」。它覆蓋全部 10 章核心內(nèi)容從概論到查找但每一頁(yè)都在回答一個(gè)具體問(wèn)題當(dāng)你的手指懸在鍵盤上該敲哪一行當(dāng)編譯器報(bào)錯(cuò)說(shuō)“segmentation fault”該先檢查指針還是邊界條件當(dāng)面試官問(wèn)“為什么快排不穩(wěn)定”你脫口而出的那句解釋能不能讓對(duì)方點(diǎn)頭說(shuō)“對(duì)就是這個(gè)點(diǎn)”它適合三類人考研黨對(duì)照王道/天勤刷題時(shí)遇到概念模糊比如“線索二叉樹為什么只優(yōu)化中序前驅(qū)后繼”立刻翻第三章末尾的對(duì)比表格轉(zhuǎn)碼新人寫完一個(gè) BST 插入函數(shù)不確定if (key root.val)該遞歸左子樹還是右子樹翻第六章二叉排序樹定義原文兩行字直接定乾坤老手救火員線上服務(wù)因ArrayList頻繁擴(kuò)容抖動(dòng)臨時(shí)查「順序表 vs 鏈表」章節(jié)里的空間密度與時(shí)間復(fù)雜度交叉分析表5 秒內(nèi)決定要不要切LinkedList。這不是知識(shí)的搬運(yùn)工它是你大腦緩存區(qū)里那個(gè)永遠(yuǎn)在線的「數(shù)據(jù)結(jié)構(gòu)協(xié)處理器」——不渲染圖形不講哲學(xué)只輸出可執(zhí)行的判斷依據(jù)?，F(xiàn)在我們把它從 PDF 里拆出來(lái)變成你能抄、能改、能 debug 的活體筆記。2. 把抽象定義落地為可驗(yàn)證的代碼動(dòng)作從邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)的四層映射2.1 邏輯結(jié)構(gòu) ≠ 存儲(chǔ)結(jié)構(gòu)為什么“線性結(jié)構(gòu)”在代碼里可能長(zhǎng)成一棵樹文檔第一章開篇就劃清一條生死線“邏輯結(jié)構(gòu)描述數(shù)據(jù)關(guān)系獨(dú)立于計(jì)算機(jī)存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)語(yǔ)言中的實(shí)現(xiàn)?！?這句話聽著像廢話但所有翻車都始于混淆它。舉個(gè)血淚例子你實(shí)現(xiàn)一個(gè)“?！边壿嬌纤仨殱M足 LIFO后進(jìn)先出但存儲(chǔ)上你可以用數(shù)組順序棧、單鏈表鏈棧、甚至用兩個(gè)隊(duì)列模擬雙隊(duì)列棧。這三種實(shí)現(xiàn)邏輯行為完全一致物理結(jié)構(gòu)天差地別。文檔里那句“線性結(jié)構(gòu)一對(duì)一關(guān)系”不是讓你背而是讓你在寫代碼前自問(wèn)我當(dāng)前操作的數(shù)據(jù)其元素間是否存在且僅存在一個(gè)前驅(qū)和一個(gè)后繼如果是如數(shù)組下標(biāo)i-1和i1那你就在處理線性邏輯如果否如圖中頂點(diǎn)可能有多個(gè)鄰接點(diǎn)那你必須切換到非線性思維。驗(yàn)證動(dòng)作打開你的 IDE新建一個(gè)Stack類強(qiáng)制只暴露push()、pop()、top()三個(gè)接口。然后分別用ArrayList和LinkedList實(shí)現(xiàn)它。運(yùn)行以下測(cè)試Stack s new Stack(); s.push(1); s.push(2); s.push(3); System.out.println(s.pop()); // 必須輸出 3 System.out.println(s.pop()); // 必須輸出 2你會(huì)發(fā)現(xiàn)無(wú)論底層用數(shù)組還是鏈表輸出序列永遠(yuǎn)是3,2,1。這就是邏輯結(jié)構(gòu)對(duì)存儲(chǔ)結(jié)構(gòu)的“屏蔽力”——它保證了行為契約不管你內(nèi)部怎么折騰。提示文檔中“順序存儲(chǔ)結(jié)構(gòu)如數(shù)組”和“鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如鏈表”的舉例本質(zhì)是在告訴你當(dāng)邏輯結(jié)構(gòu)確定后存儲(chǔ)結(jié)構(gòu)的選擇取決于操作頻次。比如若你的棧 90% 時(shí)間在push/pop10% 在隨機(jī)訪問(wèn)第i個(gè)元素那鏈棧比順序棧更優(yōu)避免數(shù)組擴(kuò)容和元素搬移。2.2 存儲(chǔ)結(jié)構(gòu)的物理細(xì)節(jié)決定性能天花板地址計(jì)算公式不是數(shù)學(xué)題是內(nèi)存布局說(shuō)明書文檔第二章給出順序表地址公式LOCa(i) LOCa(1) (i-1)*d。別把它當(dāng)公式背這是 C 語(yǔ)言里arr[i]能瞬間定位的底層原理。d是每個(gè)元素占的字節(jié)數(shù)如int是 4(i-1)是偏移量LOCa(1)是首地址。動(dòng)手驗(yàn)證用 C 寫一段代碼打印int arr[5]中每個(gè)元素的地址#include stdio.h int main() { int arr[5] {10, 20, 30, 40, 50}; for(int i 0; i 5; i) { printf(arr[%d] address: %p, value: %d\n, i, arr[i], arr[i]); } return 0; }輸出類似arr[0] address: 0x7ffeedb3a9a0, value: 10 arr[1] address: 0x7ffeedb3a9a4, value: 20 arr[2] address: 0x7ffeedb3a9a8, value: 30看到?jīng)]地址差正好是40x9a4 - 0x9a0 4這就是d4的鐵證。arr[i]的本質(zhì)就是arr[0] i * sizeof(int)。參數(shù)說(shuō)明LOCa(1)對(duì)應(yīng)arr[0]是編譯器分配的起始地址d由數(shù)據(jù)類型決定char是 1double是 8不可更改i必須是整數(shù)且0 ≤ i n越界即野指針Segmentation fault的根源。注意文檔里寫的是LOCa(i) LOCa(1) (i-1)*d這是按“首元素編號(hào)為 1”的數(shù)學(xué)習(xí)慣。但 C/Java 中數(shù)組下標(biāo)從 0 開始所以實(shí)際代碼中是arr[0] i * d。這個(gè)偏移量轉(zhuǎn)換是新手最容易栽跟頭的地方——你以為在算第 3 個(gè)元素其實(shí)代碼里i2。2.3 散列存儲(chǔ)的“沖突處理”不是理論是調(diào)試時(shí)必看的日志字段文檔第九章講散列表重點(diǎn)在“處理沖突的方法”。但現(xiàn)實(shí)中你不會(huì)去手寫開放定址法而是用HashMap。那文檔的價(jià)值在哪在幫你讀懂HashMap的源碼注釋和擴(kuò)容日志。比如 JDK 8 的HashMap默認(rèn)初始容量 16負(fù)載因子 0.75。當(dāng)你 put 第 13 個(gè)元素16*0.7512時(shí)它會(huì)觸發(fā)擴(kuò)容。此時(shí)若你看到日志里resize()被調(diào)用就要立刻反應(yīng)這不是 bug是散列表在用“拉鏈法”應(yīng)對(duì)沖突后的自然生長(zhǎng)。驗(yàn)證動(dòng)作寫一段 Java 代碼故意制造哈希沖突import java.util.*; public class HashCollisionTest { public static void main(String[] args) { // 自定義 key讓 hashcode 強(qiáng)制相同 MapKey, String map new HashMap(); map.put(new Key(A), value1); map.put(new Key(B), value2); // A 和 B 的 hashCode 都返回 1 System.out.println(Size: map.size()); // 輸出 2證明拉鏈法生效 System.out.println(Bucket 1 size: getBucketSize(map, 1)); // 需反射獲取此處示意 } static class Key { String s; Key(String s) { this.s s; } Override public int hashCode() { return 1; } // 強(qiáng)制沖突 Override public boolean equals(Object o) { return false; } } }這段代碼會(huì)證實(shí)即使hashCode()總返回 1HashMap仍能存兩個(gè)不同 key因?yàn)槔湻ò阉鼈儝煸谕粋€(gè)桶的鏈表上。而文檔里“拉鏈法的優(yōu)點(diǎn)刪除結(jié)點(diǎn)易實(shí)現(xiàn)”這句話就解釋了為什么map.remove(key)能快速定位并斷開鏈表節(jié)點(diǎn)——它不需要像開放定址法那樣找下一個(gè)空槽。參數(shù)說(shuō)明α裝填因子α 元素個(gè)數(shù) / 表長(zhǎng)。文檔說(shuō)“開放定址法要求 α≤1”意味著你不能往長(zhǎng)度為 10 的數(shù)組里塞 11 個(gè)元素會(huì)死循環(huán)但拉鏈法α可以遠(yuǎn)大于 1鏈表無(wú)限長(zhǎng)hash(x) % mm是表長(zhǎng)必須是質(zhì)數(shù)如 11, 13, 17否則x%m的分布會(huì)不均勻加劇沖突。JDK 里table.length永遠(yuǎn)是 2 的冪是為用位運(yùn)算 (n-1)替代%但代價(jià)是要求hash()方法自己做擾動(dòng)見HashMap.hash()源碼。2.4 邏輯結(jié)構(gòu)上的運(yùn)算必須映射到存儲(chǔ)結(jié)構(gòu)的物理操作插入/刪除的“移動(dòng)次數(shù)”是性能瓶頸的刻度尺文檔第二章直言“順序表插入平均移動(dòng)結(jié)點(diǎn)次數(shù)為 n/2”。這不是統(tǒng)計(jì)學(xué)結(jié)論是你每次ArrayList.add(index, element)時(shí) JVM 真實(shí)執(zhí)行的 memcpy 次數(shù)。動(dòng)手驗(yàn)證用 Java 的ArrayList做基準(zhǔn)測(cè)試import java.util.*; public class InsertCostTest { public static void main(String[] args) { ListInteger list new ArrayList(10000); // 預(yù)填充 10000 個(gè)元素 for(int i 0; i 10000; i) list.add(i); long start System.nanoTime(); list.add(0, -1); // 在頭部插入觸發(fā)移動(dòng) 10000 次 long cost System.nanoTime() - start; System.out.println(Insert at head: cost ns); start System.nanoTime(); list.add(list.size(), -1); // 在尾部插入移動(dòng) 0 次 cost System.nanoTime() - start; System.out.println(Insert at tail: cost ns); } }結(jié)果會(huì)顯示頭部插入耗時(shí)是尾部插入的數(shù)百倍。這就是n/2的物理體現(xiàn)——n10000時(shí)平均移動(dòng) 5000 個(gè)Integer對(duì)象。參數(shù)說(shuō)明n當(dāng)前表長(zhǎng)不是容量。ArrayList.size()返回nArrayList.capacity()返回底層數(shù)組長(zhǎng)度“平均移動(dòng) n/2 次”假設(shè)插入位置等概率分布在[0,n]則移動(dòng)次數(shù)期望值為(012...n)/(n1) n/2鏈表插入為何是O(1)因?yàn)橹恍栊薷?2 個(gè)指針prev.next newNode; newNode.next next與n無(wú)關(guān)。但文檔強(qiáng)調(diào)“平均時(shí)間復(fù)雜度均為 O(n)”指的是查找插入位置的時(shí)間如get(i)需遍歷i次這才是鏈表真正的瓶頸。3. 從偽代碼到可運(yùn)行代碼把文檔里的算法描述翻譯成機(jī)器能懂的指令3.1 直接插入排序文檔里的 while 循環(huán)就是你 IDE 里光標(biāo)閃爍的位置文檔第十章給出直接插入排序的 Java 代碼public static void insertSort(int[] a){ int i, j, temp; int n a.length; for(i 0; i n - 1; i ){ temp a[i 1]; j i; while(j -1 temp a[j]){ a[j 1] a[j]; j --; } a[j 1] temp; } }這段代碼的魔力在于它把“逐個(gè)向前插入到合適位置”這句人話精準(zhǔn)翻譯成了 CPU 的指令流。關(guān)鍵在while循環(huán)體a[j 1] a[j]把比temp大的元素往后挪一位j--繼續(xù)往前找更小的元素a[j 1] temp當(dāng)j停在第一個(gè)≤ temp的位置時(shí)temp就該插在j1。動(dòng)手驗(yàn)證用文檔例 1 的序列T(13,6,3,31,9,27,5,11)手動(dòng)執(zhí)行初始[13], 6,3,31,9,27,5,11i0:temp6,j0,613→a[1]a[0]13,j-1→a[0]6→[6,13],3,31,...i1:temp3,j1,313→a[2]13,j0,36→a[1]6,j-1→a[0]3→[3,6,13],31,...參數(shù)說(shuō)明i已排序區(qū)間的右邊界[0,i]已有序temp待插入的元素必須先取出否則挪動(dòng)時(shí)會(huì)被覆蓋j -1防止j減到-1后a[j]越界C 里會(huì)段錯(cuò)誤Java 會(huì)拋ArrayIndexOutOfBoundsException。3.2 希爾排序增量序列d不是魔法數(shù)字是控制“分組粒度”的旋鈕文檔給出希爾排序的 Java 實(shí)現(xiàn)并強(qiáng)調(diào)“小組的構(gòu)成不是簡(jiǎn)單地逐段分割而是將相隔某個(gè)增量 d 的記錄組成一個(gè)小組”。這句話直指核心d決定了你把原數(shù)組切成了幾塊。動(dòng)手驗(yàn)證對(duì)序列T(65,34,25,87,12,38,56,46,14,77,92,23)取d4分組 1索引 0,4,865,12,14→ 排序后12,14,65分組 2索引 1,5,934,38,77→ 已有序分組 3索引 2,6,1025,56,92→ 已有序分組 4索引 3,7,1187,46,23→ 排序后23,46,87合并后12,34,25,23,14,38,56,46,65,77,92,87即文檔答案P,A,C,S,Q,D,F,X,R,H,M,Y的數(shù)值版。參數(shù)說(shuō)明d序列文檔用d5,3,1但實(shí)際工程中常用 Knuth 序列h 3*h11,4,13,40...或 Sedgewick 序列for(k 0; k span; k)k是每組的起始偏移spand是組間距i k; i n-span; i i span確保ispan不越界這是新手常漏的邊界檢查。3.3 堆排序建堆的起始索引(n-2)//2是怎么算出來(lái)的畫一棵樹比背公式管用十倍文檔第八章說(shuō)“從第一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整”并給出i (n-1-1)/2。這公式讓很多人懵圈。真相很簡(jiǎn)單完全二叉樹中最后一個(gè)非葉子節(jié)點(diǎn)就是最后一個(gè)元素的父節(jié)點(diǎn)。動(dòng)手驗(yàn)證取n8畫一棵 8 個(gè)節(jié)點(diǎn)的完全二叉樹0 / \ 1 2 / \ / \ 3 4 5 6 / 7節(jié)點(diǎn) 7 的父節(jié)點(diǎn)是(7-1)/2 3整除。而節(jié)點(diǎn) 3 是第一個(gè)非葉子節(jié)點(diǎn)它有左孩子 7。所以建堆要從i3開始依次處理i3,2,1,0?？蛇\(yùn)行代碼修正文檔中的createHeap加入完整建堆邏輯public static void heapSort(int[] a) { int n a.length; // Step 1: Build max heap from bottom up for (int i (n - 2) / 2; i 0; i--) { heapify(a, n, i); } // Step 2: Extract elements from heap one by one for (int i n - 1; i 0; i--) { swap(a, 0, i); // Move current root to end heapify(a, i, 0); // Call heapify on reduced heap } } private static void heapify(int[] a, int n, int i) { int largest i; // Initialize largest as root int left 2 * i 1; int right 2 * i 2; if (left n a[left] a[largest]) largest left; if (right n a[right] a[largest]) largest right; if (largest ! i) { swap(a, i, largest); heapify(a, n, largest); // Recursively heapify the affected sub-tree } } private static void swap(int[] a, int i, int j) { int temp a[i]; a[i] a[j]; a[j] temp; }參數(shù)說(shuō)明(n-2)/2n-1是最后一個(gè)節(jié)點(diǎn)索引其父節(jié)點(diǎn)索引為(n-1-1)/2 (n-2)/2整除heapify(a, n, i)以i為根向下調(diào)整子樹保證a[i] ≥ a[2*i1]且a[i] ≥ a[2*i2]swap(a, 0, i)堆頂最大值與末尾交換把最大值“踢出”堆i即新堆長(zhǎng)度。3.4 Dijkstra 與 Prim一字之差卻是圖算法的“雙生子”文檔的對(duì)比表是防混淆的后悔藥文檔第七章把 Dijkstra最短路徑和 Prim最小生成樹并列但新手極易混淆。文檔雖未明說(shuō)但兩者的偽代碼結(jié)構(gòu)高度相似都維護(hù)一個(gè)dist[]數(shù)組Dijkstra 存起點(diǎn)到各點(diǎn)最短距離Prim 存各點(diǎn)到已選集合的最短邊權(quán)都用visited[]標(biāo)記已確定節(jié)點(diǎn)都在未訪問(wèn)節(jié)點(diǎn)中選dist最小者加入集合。核心區(qū)別文檔隱含需你提煉維度DijkstraPrimdist[v]含義起點(diǎn)s到v的最短路徑長(zhǎng)度v到已選頂點(diǎn)集S的最短邊權(quán)重更新邏輯dist[v] min(dist[v], dist[u] w(u,v))dist[v] min(dist[v], w(u,v))目標(biāo)找單源到所有點(diǎn)的最短路找連接所有點(diǎn)的最小權(quán)值樹動(dòng)手驗(yàn)證對(duì)同一張圖手動(dòng)跑一遍兩種算法記錄dist[]數(shù)組變化。你會(huì)發(fā)現(xiàn)Dijkstra 的dist值可能被多次更新因路徑可經(jīng)多跳而 Prim 的dist值一旦確定就不會(huì)再變因只關(guān)心到集合的直連邊。提示文檔中“Dijkstra 算法類似于 prim 算法”這句話是讓你警惕——它們共享數(shù)據(jù)結(jié)構(gòu)和框架但業(yè)務(wù)語(yǔ)義完全不同。面試時(shí)若被問(wèn)“Dijkstra 能不能求 MST”答“不能因?yàn)樗鼉?yōu)化的是路徑和而非邊權(quán)和”就能一擊致命。4. 避坑那些文檔里沒寫、但你調(diào)試時(shí)一定會(huì)撞上的 5 個(gè)真實(shí)陷阱4.1 現(xiàn)象循環(huán)隊(duì)列判空判滿時(shí)front rear既表示空也表示滿程序隨機(jī)崩潰原因文檔提到三種解決方法但新手常忽略“少用一個(gè)元素空間”方案的強(qiáng)制約束——你必須預(yù)留一個(gè)空位否則rear追上front時(shí)無(wú)法區(qū)分狀態(tài)。解決嚴(yán)格遵守(rear 1) % maxSize front作為滿的判定條件并在初始化時(shí)maxSize設(shè)為實(shí)際需要容量 1。例如要存 10 個(gè)元素maxSize必須設(shè)為 11。4.2 現(xiàn)象二叉樹中序遍歷遞歸版本棧溢出而迭代版本正常原因文檔第六章說(shuō)“時(shí)間復(fù)雜度為 O(n)”但沒提遞歸深度。對(duì)于退化成鏈表的二叉樹如只有右孩子的樹遞歸深度 n而 JVM 默認(rèn)棧大小有限通常 1MB。解決生產(chǎn)環(huán)境禁用深度遞歸改用迭代用顯式Stack或 Morris 遍歷O(1) 空間。4.3 現(xiàn)象哈希表put()后get()返回null但containsKey()返回true原因文檔第九章講“散列函數(shù)要均勻”但沒說(shuō)key的equals()和hashCode()必須一致。若你重寫了equals()卻忘了hashCode()或反之就會(huì)出現(xiàn)key能找到hashCode定位到桶但equals比較失敗get返回null。解決IDE 自動(dòng)生成equals()和hashCode()IntelliJ: AltInsert →equals()andhashCode()絕不手寫。4.4 現(xiàn)象快排partition后pivot位置不對(duì)數(shù)組未正確分割原因文檔第八章說(shuō)“以第一個(gè)元素為參考基準(zhǔn)”但未強(qiáng)調(diào)pivot的最終位置必須通過(guò)swap確保。常見錯(cuò)誤是只移動(dòng)元素卻不把pivot放到分界點(diǎn)。解決partition函數(shù)末尾必須有swap(arr, low, j)j是pivot最終位置否則pivot會(huì)留在原地導(dǎo)致左右子數(shù)組包含pivot無(wú)限遞歸。4.5 現(xiàn)象KMP 字符串匹配next數(shù)組構(gòu)建正確但主串匹配時(shí)漏掉一次成功原因文檔第四章說(shuō)“模式匹配”但未提 KMP 的next數(shù)組是“最長(zhǎng)真前綴后綴長(zhǎng)度”且匹配失敗時(shí)j next[j-1]。新手常寫成j next[j]導(dǎo)致跳過(guò)一個(gè)字符。解決牢記next[j]表示pattern[0..j]的最長(zhǎng)公共前后綴長(zhǎng)度匹配失敗時(shí)j應(yīng)回退到next[j-1]因j已失配要看j-1的前綴。5. 用文檔的“參數(shù)表”反向驅(qū)動(dòng)調(diào)試當(dāng)代碼不工作時(shí)先查這張表而不是重寫5.1 時(shí)間復(fù)雜度不是玄學(xué)是定位性能瓶頸的坐標(biāo)軸文檔第一章列出時(shí)間復(fù)雜度階O(1), O(log n), O(n), O(n log n), O(n2), ...。這不僅是考試考點(diǎn)更是你面對(duì)慢查詢時(shí)的第一反應(yīng)指南。場(chǎng)景你寫了一個(gè)處理 10 萬(wàn)條記錄的函數(shù)耗時(shí) 10 秒。若你用了嵌套循環(huán)外層i從 0 到 n內(nèi)層j從 0 到 n復(fù)雜度是O(n2)→10?2 101?次操作CPU 每秒10?次約 10 秒吻合解決方案立刻檢查能否降維——用哈希表把內(nèi)層O(n)查找降到O(1)整體變O(n)耗時(shí)降至 0.01 秒。文檔參數(shù)表實(shí)戰(zhàn)把文檔中所有算法的時(shí)間復(fù)雜度整理成速查表算法最好情況平均情況最壞情況關(guān)鍵約束直接插入排序O(n)O(n2)O(n2)數(shù)據(jù)越接近有序越快快速排序O(n log n)O(n log n)O(n2)極端不平衡時(shí)退化歸并排序O(n log n)O(n log n)O(n log n)穩(wěn)定但需 O(n) 額外空間二分查找O(1)O(log n)O(log n)要求數(shù)組已排序鏈表查找O(1)O(n)O(n)無(wú)法隨機(jī)訪問(wèn)只能遍歷從那以后我每次寫完一個(gè)算法第一件事不是 run而是打開這個(gè)表用筆圈出它的復(fù)雜度再估算n10?時(shí)的理論耗時(shí)。如果實(shí)測(cè)遠(yuǎn)超預(yù)期我就知道要么n比想象中大比如字符串長(zhǎng)度被誤當(dāng)n要么算法選錯(cuò)了該用O(n log n)卻寫了O(n2)。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取