算法复杂度实战与收尾
十篇走到最后。前面我们学了数组、链表、栈队列、树与平衡树、哈希、堆、图、并查集、排序——每一个都挂着一串 O(...)。可"复杂度"不是背结论，而是拿到一段代码或一道题，能亲手算出来、能选对数据结构。本篇把散落的工具收拢：怎么解递归式（主定理）、均摊分析回顾、以及一个"看到需求就选结构"的决策表。这是 CS61B 的收官，也是把前面九篇拧成肌肉记忆的一课。 一、实战：看到代码，算出复杂度1.1 循环套循环123for (int i = 0; i < n; i++) // n 次 for (int j = 0; j < n; j++) // 每次 n 次 sum += a[i] * b[j]; 外层 n、内层 n → O(n²)。 1.2 循环减半（二分、堆下沉）1for (int i = n; i > 0; i /= 2) process(i); // 每次规模 /2 i 走 n → n/2 → n/4 → … → 1，共 log₂ n 步 → O(log n)。 坑①：log...
并查集与排序（归并、快排、堆排）
前面几篇都在讲"怎么组织数据、怎么查找"。本篇补两个 CS61B 里极其常用、却容易被低估的工具：**并查集（Union-Find）**管"动态连通性"，三大 O(n log n) 排序管"把数据排好序"。它们一个藏在 Kruskal 最小生成树里，一个藏在 Arrays.sort 背后——看似简单，细节全是坑。 一、并查集：谁和谁是一伙的？一句话：并查集维护若干"不相交集合"，支持两个操作——find(x) 找 x 的祖先（代表），union(x,y) 把 x、y 所在集合合并。它回答的是"这两个元素连通吗"。 典型场景：逐步加边建网络，随时问"a 和 b 现在通不通"；或 Kruskal 算法里判断加一条边会不会成环。 1.1 朴素 vs 优化朴素实现 union 直接把一棵树挂到另一棵，最坏退化成链，find 变 O(n)。两个经典优化把它压到几乎 O(1)（反阿克曼函数 α(n)，实际常数级）： 按秩/大小合并（union by rank&...
图：表示、DFS、BFS 与 Dijkstra
数组管顺序，树管层次，哈希管查找——可现实里的关系常常既不是一条线、也不是一棵树：地铁线网、朋友关系、任务依赖、互联网路由，全都是"点连着点"的网络。这种结构叫图（Graph）。本篇我们解决三件事：图怎么存进计算机、怎么把整张图"走一遍"、以及怎么在带权图里找到两点间最短的路。 一、是什么：顶点、边、权一句话：图 = 顶点集合 V + 边集合 E；边可以有向/无向，可以带**权重（权）**表示距离/代价/时间。 无向图：边双向（朋友关系）。 有向图：边单向（关注关系、依赖）。 带权图：边上标数字（地图里程）。 二、怎么存：邻接表 vs 邻接矩阵这是图论里第一个关键取舍。 维度 邻接表（adjacency list） 邻接矩阵（adjacency matrix） 存储 O(V+E) O(V²) 遍历某点邻居 O(degree) 很快 O(V) 要扫整行 判断两点是否相邻 O(degree) O(1) 适合 稀疏图（大多数真实网络） 稠密图、需要频繁查边 ...
堆与优先队列（二叉堆）
队列我们都熟：先进先出，队头永远是来得最早的那一个。可现实往往不按先来后到——急诊室里重伤员优先，操作系统里短作业优先，Dijkstra 最短路里"当前距离最小"的节点优先。我们需要一种"按优先级出队，而不是按到达顺序"的结构，这就是优先队列（Priority Queue）；而它最高效的数组实现，叫二叉堆（binary heap）。 本篇讲清三件事：堆长什么样、插入/取最小怎么 O(log n) 完成、以及它和排序、图算法的关系。 一、是什么：堆不是"排好序的数组"一句话：二叉堆是一棵"完全二叉树"，满足堆序性质（heap property）——每个节点的值都不大于（最小堆）或不小于（最大堆）它的孩子。 完全二叉树：除最后一层外全满，最后一层从左往右填。这个形状让它能紧凑地存进数组，不需要指针。 堆序性质：最小堆里，父 ≤ 子，所以全局最小值一定在堆顶（下标 0）。最大堆反过来。 最小堆（树视图 = 数组视图） 2 5 7 9 11 ...
哈希表：散列函数、冲突解决与扩容
你有没有遇到过这种尴尬：数组按下标访问是 O(1)，可它要求"下标必须是整数"；而真实世界里的键往往是字符串（"apple"）、对象（一个 User）、甚至一段二进制。我们想问的是——能不能让任意类型的键，也拥有接近 O(1) 的查找速度？ 哈希表（Hash Table，也叫散列表）就是这个问题的答案，也是 Java HashMap、Python dict、C++ unordered_map 背后的真正引擎。它把"键"压缩成一个数组下标，于是插入、查找、删除都甩掉了"逐个比较"的包袱。但它不是免费的午餐：冲突（collision） 一定会发生，怎么设计散列函数、怎么消解冲突、什么时候扩容，正是本篇要讲清楚的三件事。 一、是什么：哈希表的三件套一句话：哈希表 = 一个数组（桶 buckets）+ 一个散列函数（hash function）+ 一套冲突解决机制。 散列函数 h(key) 把任意键映射到一个整数下标 0..m-1，我们就去数组的那个位置存取。理想情况下每次都 O(1)。 核心约...
树：BST、平衡树（AVL/红黑简介）与 B 树
你有没有想过一个尴尬的局面：有序数组查找快（二分 O(log n)），可一旦插入新元素，得把后面一半整体后挪，O(n)；链表插入是 O(1)，可查找又退化成 O(n)。有没有一种结构，能既要查找快、又要插入/删除也快？ 答案就是本篇的主角——树，更准确地说是**二叉搜索树（BST）**以及它的「打补丁」版本：平衡树（AVL / 红黑树）和多路平衡树（B 树）。它们把「有序」从「数组的连续内存」里解放出来，变成「节点之间的偏序关系」，于是插入、删除不再需要搬移整段数据。我们先从最朴素的 BST 讲起，再看它哪里会翻车，以及三个补丁分别怎么修。 一、二叉搜索树（BST）：定义与不变式BST = 一棵二叉树，且满足「左小右大」的递归不变式： 对树上任意一个节点 x：其左子树中所有 key 都 < x.key，其右子树中所有 key 都 > x.key。 注意是「严格」的偏序，通常不允许重复 key（要支持重复就改成「≤ 放左 / ≥ 放右」，本篇按不允许重复讲，逻辑最干净）。这条不变式是 BST 一切能力的根基——因为它意味着中...
栈与队列：LIFO 与 FIFO 的两种世界观
你有没有想过，为什么编辑器里按 Ctrl+Z 能一步步撤销，而打印机却老老实实按提交顺序一张张出？这两件事看似无关，底层却是同一对"基础设施"的两种相反用法：一个只许从同一端进出，一个必须从两端分工。 这就是本篇的主角——栈（Stack） 和 队列（Queue）。它们都属于上篇讲过的 ADT：只规定"能做什么"，不规定"怎么存"。但正是这两种最朴素的秩序观，撑起了从函数调用、表达式求值到任务调度、消息队列的半壁江山。我们先把"世界观"立住，再动手实现，最后看两个几乎人人都踩过的坑。 一、栈（Stack）：后进先出（LIFO）的世界观栈 = 只允许在同一端（栈顶）进行插入和删除的 ADT，语义是 LIFO（Last-In-First-Out，后进先出）。 想象一摞盘子：你只能在最上面放新盘子（push），也只从最上面拿走（pop），永远碰不到底下那个。最后放上去的，必然第一个被取走——这就是"后进先出"。 栈暴露给客户的契约只有四个操作： 操作 含义 异常 p...
链表（单/双）与哨兵
上篇动态数组最大的软肋是：在中间插入或删除一个元素，要搬移其后所有的元素，代价 O(n)。链表（linked list）号称能绕开这个软肋——它不靠"连续内存 + 下标"组织数据，而是让每个元素自己记住"下一个是谁"。 但"链表删除是 O(1)"这句话，九成初学者都记漏了前提。这篇就把单链表、双链表、以及那个能把一堆边界特判消灭干净的**哨兵节点（sentinel）**讲透，顺便留三道面试开胃题。 一、单链表：每个节点只认识"下一个"单链表由一串 节点（Node） 串成。每个节点干两件事：存自己的数据 val，再存一个指向下一个节点的引用 next。最后一个节点的 next 是 null，表示"到头了"。一个独立的 head 引用指向第一个节点，靠它才能摸到整条链。 1 val next 2 val next 3 val next null head 本质一句话：单链表用&...
数组与动态数组（ArrayList）及均摊分析
你每天写 ArrayList、vector、list.append()，从没操心过"容量"——它好像永远装得下。但每次"满了"，它其实偷偷把整片数据搬了一次家：分配更大的内存、把旧元素逐个复制过去、再扔掉旧的。这一篇把这件"看不见的搬家"讲透，并回答一个反直觉的问题：为什么扩容是 O(n)，尾部追加却是 O(1)？ 答案叫均摊分析（amortized analysis）。 一、静态数组：快，但僵数组是最原始的数据结构：N 个同类型元素连续摆在内存里，靠下标直接寻址。 优点：随机访问 a[i] 是 O(1)——CPU 算一下 基地址 + i × 元素大小 就能取到，不依赖数组长度。 死穴：容量在创建时就钉死了。想在第 0 位插一个？后面所有元素都得往后挪，O(n)。更糟的是，满了就彻底塞不下了。 数组这层"裸"结构，正是上一篇说的"只承诺怎么存、不约束怎么用"。动态数组要解决的，就是给它套一层自动扩容的抽象。 二、动态数组：在数组上套一层"自动扩容"动态数...
数据结构导论：从数组到抽象数据类型（ADT）
很多人学完数组、链表、栈、队列，仍有一个挥之不去的困惑：这些"数据结构"到底有没有区别？为什么教科书总说 Stack 是 ADT 而不是数据结构？ 如果你也含糊，这篇就是为你写的——我们不背定义，先把这层窗户纸捅破。 缘起很朴素：数组是最原始、最"诚实"的数据结构，它把 N 个同类型元素连续摆在内存里，你用下标直接取。但它太"裸"了——它既不阻止你越界访问，也不阻止你在第 0 位插一个元素（后面所有元素都得搬）。于是自然会想：能不能定义一种"只许从一端进出"的抽象，把数组这种杂乱用法管起来？ 这正是抽象数据类型（ADT）的动机：从"怎么存"里提炼出"能做什么"。 一、先别急着写代码：什么是抽象数据类型（ADT）ADT = 一组数据值 + 一组在这些值上可做的操作（契约），它只规定"你能对我做什么"，不规定内部怎么存。 最熟悉的例子其实天天在用：整数就是 ADT。你知道 +、-、* 怎么用，但从不在乎 CPU 里是用补码还是浮点表示...
