1. 从翻完就忘到能讲给别人听我读算法图解的真实路径第一次翻开《算法图解》的时候我犯了一个很多人都会犯的错误——把它当小说看。两天翻完合上书脑子里只剩下几个模糊的卡通小人什么二分查找、快速排序、广度优先搜索全搅成了一锅粥。后来有个朋友问我二分查找到底比普通查找快多少我支支吾吾半天只憋出一句快很多。那一刻我才意识到看懂和真正理解之间隔着一条很宽的河。这本书的定位其实非常明确它不是给科班出身、要啃《算法导论》的人准备的而是给那些被算法吓过、觉得算法高不可攀、但又确实需要用它来解决实际问题的人准备的。它用大量图示把抽象概念具象化把递归画成一层层套娃把链表画成一列手拉手的小人。但问题也恰恰出在这里——图看得爽概念却没真正长进脑子里。因为图示是作者的理解不是你的理解。所以这篇读后感我不想写成这本书讲了什么的复述。我想做的是另一件事把书里那几个核心概念用我自己踩过坑、反复琢磨之后的方式重新讲一遍。包括简单查找和二分查找到底差在哪、数组和链表为什么一个快一个慢、递归为什么让人又爱又恨、快速排序凭什么叫快速、散列表为什么能做到近乎瞬间查找、广度优先搜索解决的是什么类型的问题、迪杰斯特拉算法又在什么场景下才派得上用场。如果你也是那种书看完了但感觉没学到东西的人或者你正准备读这本书但担心读完就忘那这篇内容应该能帮到你。我会尽量用生活化的类比、具体的数字、能动手验证的例子把每个概念讲到你能转述给别人听的程度。因为检验一个人是否真正理解一个概念最好的标准就是——你能不能不用书上的原话把它讲给一个完全不懂的人听。下面进入正题。我会按照概念是什么→为什么这样设计→实际怎么用→我踩过的坑这个节奏来展开每个部分都尽量给出可以自己动手验证的例子。2. 简单查找与二分查找差距不在快一点而在数量级2.1 用猜数字游戏理解两种查找的本质区别先从一个最简单的场景说起。假设我心里想了一个1到100之间的整数你来猜我每次只告诉你大了或小了。你会怎么猜大多数人的第一反应是从1开始一个一个猜1、2、3、4……这就是简单查找也叫线性查找。最坏的情况下如果我想的是100你要猜100次。平均下来也要50次。但如果你稍微动点脑子第一猜就会猜50。我说大了你就知道答案在1到49之间我说小了答案就在51到100之间。无论哪种情况你都一次性排除了一半的可能性。接着猜25或75再排除一半。这就是二分查找。100个数二分查找最多只需要7次。为什么是7因为2的7次方是128大于100。换句话说每次把搜索范围砍一半砍到只剩1个数需要的次数就是2的多少次方等于总数。用数学表达就是log₂(n)。100的log₂大约是6.64向上取整就是7。这个差距在小数据量下不明显但数据量一大就恐怖了。我列个表你就明白了数据量简单查找最多次数二分查找最多次数10010071,0001,0001010,00010,000141,000,0001,000,000201,000,000,00010亿30看到最后一行了吗10亿个数据二分查找最多30次就能找到。这就是数量级的差距不是快一点而是根本不在一个维度上。2.2 二分查找的致命前提数据必须是有序的这里有一个很多人初学时容易忽略的关键点二分查找只能用在有序数据上。如果你手里的数据是乱序的你没法判断大了还是小了二分查找就无从谈起。这就引出一个很实际的问题如果数据是乱序的我要先排序再二分查找吗排序本身也是要花时间的。如果我只查一次那排序的时间可能比直接线性查找还长。但如果我要查很多次那先花时间排好序后面每次查找都享受log₂(n)的速度就非常划算了。我在实际项目里就遇到过这个决策。当时有一个大约5万条记录的配置表程序启动时需要频繁根据某个字段查找配置。一开始我用的是线性查找每次查找平均要遍历2.5万条虽然单次也就几毫秒但架不住调用频繁累积起来启动时间就到了好几秒。后来我改成启动时先按字段排序之后全部用二分查找单次查找最多16次比较启动时间直接降到了几百毫秒。这个优化的核心不是代码写得多巧妙而是选对了数据结构的使用方式。2.3 自己动手写一个二分查找边界条件是最大的坑二分查找的思路简单到可以用一句话概括每次取中间值比较根据结果缩小一半范围。但真正动手写的时候边界条件能把人逼疯。我自己第一次写的时候就写出了死循环。def binary_search(sorted_list, target): low 0 high len(sorted_list) - 1 while low high: mid (low high) // 2 guess sorted_list[mid] if guess target: return mid elif guess target: high mid - 1 else: low mid 1 return None这段代码看起来简单但有几个地方特别容易出错。第一while low high这里到底是还是如果是当范围缩小到只剩一个元素时循环就退出了那个元素永远不会被检查。第二high mid - 1和low mid 1这里的加减1能不能省省了就会死循环因为当low和high相邻时mid永远等于low范围永远不会缩小。我个人的经验是写二分查找的时候先把边界条件想清楚——我当前要搜索的范围是[low, high]这个范围是闭区间。然后每一步操作都要保证范围确实在缩小。如果某一步操作后范围没变那就是死循环的根源。还有一个隐藏的坑mid (low high) // 2在极端情况下可能溢出。虽然在Python里整数不会溢出但在C或Java里如果low和high都很大相加可能超过整数上限。更安全的写法是mid low (high - low) // 2。这个细节在面试里经常被问到但实际写业务代码时很多人不在意。3. 数组与链表为什么随机访问和插入删除不能兼得3.1 用电影院座位和寻宝游戏理解两种结构数组和链表的区别用两个生活场景就能讲清楚。数组就像电影院里连排的座位。每个座位有编号你知道第5排第3座在哪可以直接走过去坐下不需要从第1排开始数。这就是数组的随机访问能力——只要知道下标就能在O(1)时间内拿到元素。但问题也来了如果中间突然要加一个人你得让后面所有人都往后挪一个位置腾出空位。如果队伍很长这个挪动就很费劲。删除也是同理删掉中间一个后面的人都要往前补。链表则像一场寻宝游戏。每个线索纸条上写着下一个线索在某某地方你只能顺着线索一个一个找。你想直接跳到第5个线索不行你必须从第1个开始沿着线索一路走过去。这就是链表的顺序访问——找第n个元素需要O(n)时间。但链表的好处是插入和删除特别方便你只需要把前一个线索的下一个位置改一下指向新的线索再把新线索指向原来的下一个就完成了。不需要移动任何其他元素。我用一个表格把核心差异列出来操作数组链表随机访问第n个元素O(1)O(n)在头部插入O(n)O(1)在头部删除O(n)O(1)在中间插入O(n)O(n)找位置 O(1)插入在中间删除O(n)O(n)找位置 O(1)删除内存占用连续可能浪费分散额外存指针3.2 选择困难症的解法看你的操作模式那实际开发中到底该用哪个我的判断标准很简单看你的操作模式是读多写少还是写多读少。如果你的场景是频繁按位置读取很少插入删除那数组在很多语言里对应的是列表或动态数组是更好的选择。比如一个游戏里的排行榜每帧都要读取前10名显示但排名更新可能每秒才一次那用数组就很合适。如果你的场景是频繁在中间插入删除而且不需要按位置随机访问那链表更合适。比如一个文本编辑器的撤销操作栈你总是在一端添加和移除链表尤其是双向链表就很自然。但现实往往更复杂。很多时候我们既需要快速查找又需要频繁插入删除。这时候单纯用数组或链表都不够需要更高级的数据结构比如平衡树或者跳表。不过那是另一个话题了这里先不展开。我在实际项目中有一个教训曾经为了插入方便选了一个链表结构来存配置项结果后来发现代码里90%的操作都是按名字查找配置。链表查找是O(n)导致每次查找都要遍历整个链表。后来改成用散列表字典存储查找变成O(1)代码还更简洁了。选数据结构之前一定要先统计一下各种操作的频率不要凭直觉。3.3 一个容易被忽略的细节数组的动态扩容代价很多语言里的数组其实是动态数组比如Python的list、Java的ArrayList。它们支持自动扩容用起来像数组一样方便。但扩容是有代价的当数组满了需要申请一块更大的内存把原来的元素全部复制过去。这个操作是O(n)的。如果你知道大概要存多少元素最好在创建时就指定容量避免频繁扩容。比如Python里可以用[None] * 10000预分配Java里可以new ArrayList(10000)。这个优化在数据量大时效果很明显。但链表就没有这个问题因为它的元素是分散存储的理论上只要有内存就能一直加。代价是每个元素都要额外存一个指针内存开销更大而且访问速度受缓存影响——因为元素在内存里不连续CPU缓存命中率低实际访问可能比理论值更慢。这也是为什么很多高性能场景下即使理论上链表插入更快实际还是用数组——缓存友好性有时候比理论复杂度更重要。4. 递归把套娃讲清楚顺便聊聊它为什么容易让人晕4.1 递归的本质函数自己调用自己但每次问题都变小递归这个概念书上一般会用一个例子引入计算阶乘。n的阶乘等于n乘以(n-1)的阶乘而(n-1)的阶乘又等于(n-1)乘以(n-2)的阶乘……一直到1的阶乘等于1。def factorial(n): if n 1: return 1 else: return n * factorial(n - 1)这段代码里factorial函数在自身内部又调用了factorial。这就是递归。但关键在于每次调用时问题的规模都变小了——从n变成了n-1。如果没有这个变小的过程递归就会无限进行下去直到程序崩溃。所以写递归有两个必须满足的条件第一有一个基准情况base case也就是问题小到可以直接给出答案的情况比如n等于1时直接返回1。第二每次递归调用都要向基准情况靠近比如n每次减1。这两个条件缺一不可。我见过很多初学者写递归时忘记写基准情况或者基准情况写错了导致栈溢出。栈溢出就是递归太深把调用栈撑爆了。Python默认的递归深度限制大约是1000层超过就会报RecursionError。4.2 用查字典理解递归的执行过程递归之所以让人晕是因为它的执行顺序不是线性的。函数调用会一层层压入调用栈等最内层返回后再一层层弹出。这个过程用查字典来类比特别形象。假设你在读一本英文书遇到一个生词A你去查字典。字典里解释A的时候又用到了生词B你又去查B。B的解释里又用了生词C你再查C。直到某个词D的解释你完全看得懂不需要再查了。然后你拿着D的解释回去理解C再拿着C的理解回去理解B最后理解A。这个进去的过程就是递归调用回来的过程就是递归返回。很多人晕在回来这一步因为脑子里要同时记住好几层的信息。我的建议是不要试图在脑子里模拟整个调用栈而是相信递归的定义——你只需要保证当前这一层的逻辑是对的并且它最终会到达基准情况剩下的交给计算机。4.3 递归和循环的取舍不是所有递归都该用递归理论上所有的递归都可以改写成循环。那什么时候用递归什么时候用循环我的经验是当问题本身是递归定义的用递归写出来更自然、更易读时就用递归。比如树的遍历、图的深度优先搜索、分治算法如快速排序、归并排序这些用递归写出来非常简洁。但如果递归的深度可能很大或者性能要求很高就要考虑改成循环或者用尾递归优化不过Python不支持尾递归优化。还有一个实际的问题递归的函数调用有开销。每次调用都要在栈上保存局部变量、返回地址等信息。如果递归层数很深这个开销会累积。我曾经写过一个递归处理嵌套JSON的函数数据嵌套了上千层结果直接栈溢出了。后来改成用显式的栈就是一个列表来模拟递归问题就解决了。一个实用的判断标准如果递归深度可能超过几百层或者你发现递归函数里有大量重复计算比如朴素的斐波那契数列递归那就该考虑改成循环或者加缓存了。5. 快速排序分而治之的经典但快速是有条件的5.1 快速排序的核心思想选一个基准把小的放左边大的放右边快速排序的思路可以用一句话概括选一个元素作为基准把比它小的放到左边比它大的放到右边然后对左右两边分别重复这个过程。这个过程是递归的。当左右两边的子数组都排好序了整个数组也就排好了。因为基准元素已经在它最终应该在的位置上了。def quicksort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quicksort(left) middle quicksort(right)这是快速排序最容易理解的写法但它不是原地排序会创建很多新列表空间复杂度较高。实际工程中的快速排序通常是原地排序通过交换元素来实现空间复杂度只有O(log n)递归调用栈的深度。5.2 为什么最坏情况是O(n²)基准选得不好就退化成冒泡排序快速排序的平均时间复杂度是O(n log n)但最坏情况是O(n²)。什么时候会最坏当每次选的基准都是当前子数组的最大值或最小值时。举个例子如果数组已经是有序的而你每次都选第一个元素作为基准那么每次划分后一边是空的另一边是剩下的所有元素。这样递归下去总共要递归n层每层处理n个元素总时间就是O(n²)。这时候快速排序就退化成了冒泡排序完全没有快速可言。所以基准的选择很关键。常见的策略有随机选一个元素作为基准、选第一个、选中间、选三个数的中位数。随机化是最简单的改进可以很大程度上避免最坏情况。我在实际使用中如果数据可能已经部分有序就会用随机基准或者三数取中。5.3 快速排序 vs 归并排序实际工程中怎么选快速排序和归并排序都是O(n log n)的分治算法但它们的特性不同。快速排序是原地排序空间复杂度低但最坏情况是O(n²)而且不稳定相同元素的相对顺序可能改变。归并排序是稳定排序最坏情况也是O(n log n)但需要额外的O(n)空间。在实际工程中很多语言的标准库排序算法是混合的。比如Python的sorted()用的是Timsort结合了归并排序和插入排序的优点。Java的Arrays.sort()对基本类型用双轴快速排序对对象类型用Timsort。所以大多数时候你不需要自己实现排序直接用标准库就好。但理解快速排序的原理对于理解分治思想、理解递归、理解算法复杂度分析都非常有帮助。我自己实现快速排序时踩过的一个坑在划分过程中如果基准元素有多个重复值处理不当会导致划分不平衡。比如数组里全是相同的元素如果划分时把所有等于基准的都放到一边就会退化成O(n²)。正确的做法是把等于基准的元素分散到两边或者用三路划分小于、等于、大于来处理。6. 散列表为什么它能做到近乎瞬间查找6.1 散列表的工作原理把键变成数组下标散列表也叫哈希表的核心思想非常巧妙通过一个哈希函数把键直接映射成数组的下标然后把值存在那个下标的位置。这样查找的时候只需要用同样的哈希函数算出下标直接去那个位置取值就行了不需要遍历。用生活类比来说散列表就像一个有编号的储物柜。你存东西的时候根据物品的名字算出一个柜子编号把东西放进去。取的时候用同样的方法算出编号直接打开那个柜子。不需要一个一个柜子找。# Python里的字典就是散列表 phone_book {} phone_book[张三] 13800000000 phone_book[李四] 13900000000 # 查找几乎是瞬间完成 print(phone_book[张三]) # 输出: 138000000006.2 哈希冲突不同键算出同一个下标怎么办散列表最大的问题就是哈希冲突两个不同的键经过哈希函数计算后得到了相同的下标。这就像两个不同名字的物品算出了同一个柜子编号怎么办常见的解决方案有两种。第一种是链地址法那个柜子里不放单个物品而是放一个链表所有映射到同一个下标的键值对都挂在这个链表上。查找的时候先找到柜子再在链表里逐个比较键。第二种是开放地址法如果目标位置已经被占了就按某种规则找下一个空位比如线性探测往后一个一个找、二次探测按平方数跳着找。Python的字典用的是开放地址法Java的HashMap用的是链地址法在链表过长时会转成红黑树。两种方法各有优劣链地址法在冲突多时性能下降较慢开放地址法在冲突少时缓存更友好。6.3 散列表的最坏情况为什么它不总是O(1)散列表的平均查找时间是O(1)但最坏情况是O(n)。什么时候会最坏当所有键都映射到同一个下标时散列表就退化成了一个链表查找需要遍历所有元素。要避免这种情况关键是设计一个好的哈希函数让键尽可能均匀地分布到各个下标上。同时当散列表里的元素太多时需要扩容——创建一个更大的数组把所有元素重新哈希放进去。扩容是O(n)的操作但因为它不经常发生平均下来每次插入的代价仍然是O(1)。我在实际使用散列表时的一个经验如果键是自定义对象一定要正确实现哈希函数和相等判断。在Python里就是__hash__和__eq__方法。如果只实现了其中一个或者实现得不一致就会导致散列表行为异常——明明两个对象相等却查不到或者明明不相等却被当成同一个键。这个坑我踩过不止一次。7. 广度优先搜索解决最短路径问题的利器7.1 从找朋友理解广度优先搜索的搜索顺序广度优先搜索BFS解决的问题是在一张图里从起点出发找到到达目标的最短路径。这里的最短通常指的是经过的边数最少。用社交网络来类比你想找到你和某个陌生人之间的最短人脉链。你先看你的直接朋友里有没有他如果没有再看你朋友的朋友里有没有他再看朋友的朋友的朋友……这就是广度优先搜索——一层一层地往外扩展先检查近的再检查远的。这种搜索顺序保证了当你第一次遇到目标节点时你走过的路径一定是最短的。因为如果存在更短的路径那个路径上的节点会在更早的层被检查到。7.2 队列广度优先搜索的关键数据结构广度优先搜索需要用到一个队列来管理待检查的节点。队列的特点是先进先出FIFO。你把起点的邻居加入队列然后从队列头部取出一个节点检查如果它不是目标就把它的邻居加入队列尾部。这样就能保证先加入的节点先被检查也就是先检查近的再检查远的。from collections import deque def bfs(graph, start, target): queue deque() queue.append(start) visited set() visited.add(start) while queue: node queue.popleft() if node target: return True for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return False这段代码里visited集合非常重要。如果没有它图里如果有环搜索就会无限循环。标记已访问的时机也很关键应该在节点加入队列时就标记而不是在从队列取出时才标记。否则同一个节点可能被多次加入队列导致重复处理。7.3 广度优先搜索的实际应用场景广度优先搜索在实际中应用很广。比如迷宫最短路径从起点开始一层层向外探索第一次到达终点时的路径就是最短的。社交网络的好友推荐找到二度、三度人脉。网络爬虫从种子页面开始一层层抓取链接。单词接龙从起始单词开始每次改变一个字母找到变换到目标单词的最短序列。我在做一个文件依赖分析工具时就用到了广度优先搜索。给定一个入口文件我需要找出它直接或间接依赖的所有文件。用BFS从入口开始一层层解析import语句就能得到完整的依赖树而且能保证先处理近的依赖逻辑很清晰。8. 迪杰斯特拉算法当边有了权重最短路径就不一样了8.1 从广度优先搜索到迪杰斯特拉加权图的挑战广度优先搜索找的是经过边数最少的路径它假设每条边的代价是一样的。但现实中很多场景下边的代价不同。比如地图导航从A到B可能有多条路每条路的距离或时间不同。这时候边数最少不等于总代价最小。迪杰斯特拉算法就是用来解决加权图中单源最短路径问题的。它的核心思想是每次从未确定最短路径的节点中选出当前距离起点最近的那个确定它的最短路径然后用它来更新邻居的距离。8.2 迪杰斯特拉算法的执行步骤用一个具体例子来说明。假设有四个节点A、B、C、D边和权重如下A到B是1A到C是4B到C是2B到D是5C到D是1。求A到D的最短路径。初始化A的距离为0其他节点距离为无穷大。从A开始A的邻居B距离更新为1C距离更新为4。选当前距离最小的未处理节点B距离1B的邻居C可以通过B到达距离为123比原来的4小更新C的距离为3。B的邻居D距离为156。选当前距离最小的未处理节点C距离3C的邻居D可以通过C到达距离为314比原来的6小更新D的距离为4。选DD的距离为4确定最短路径为A→B→C→D总代价4。这个过程中每次选距离最小的节点是关键。如果用简单的线性查找来选时间复杂度是O(n²)如果用优先队列最小堆来选可以优化到O((nm)log n)其中m是边数。8.3 迪杰斯特拉算法的局限不能处理负权边迪杰斯特拉算法有一个重要的限制它不能处理带负权边的图。为什么因为它的核心假设是一旦确定了一个节点的最短路径就不会再被更新。但如果存在负权边后面可能出现一条更短的路径这个假设就不成立了。比如A到B是1A到C是5B到C是-10。按照迪杰斯特拉先确定B的距离为1然后通过B更新C的距离为1(-10)-9这没问题。但如果边的顺序不同可能先确定了C的距离为5然后才发现通过B可以更短。所以负权边会破坏算法的正确性。处理负权边需要用Bellman-Ford算法它允许负权边但时间复杂度更高是O(nm)。如果图中存在负权环总权重为负的环最短路径可能不存在因为可以无限绕圈减小总权重。我在实际项目中用迪杰斯特拉算法做过一个任务调度优化。每个任务有执行时间任务之间有依赖关系需要找到关键路径。把任务看成节点依赖看成边边的权重是任务执行时间用迪杰斯特拉就能找到从起点到终点的最长路径把所有边取负就变成了最短路径问题。这个转换思路很实用但要注意不能有负权环否则就无解了。9. 把这些概念串起来我的学习方法和踩坑复盘9.1 为什么单独学每个概念都会合起来就懵我读这本书最大的体会是单个概念理解起来都不难难的是把它们串起来知道什么场景该用什么。二分查找、数组、链表、递归、快速排序、散列表、广度优先搜索、迪杰斯特拉算法这些概念单独看都很清晰但遇到一个实际问题时往往不知道该从哪个角度切入。我的解决方法是每学一个概念就强迫自己想三个实际场景。比如学了散列表我就想什么情况下用散列表比用数组好什么情况下用散列表反而更慢如果不用散列表有什么替代方案这种反向思考能帮助我把概念从知道变成会用。另一个方法是画图。不是画书上的图而是画自己的图。比如学快速排序时我拿一副扑克牌真的按照快速排序的步骤一张张摆把基准牌拿出来小的放左边大的放右边然后对左右两堆重复。摆了两三次之后我对快速排序的理解就完全不一样了——手上过一遍比眼睛看十遍都管用。9.2 我踩过的三个典型坑第一个坑是过度追求最优解。刚学完二分查找和散列表之后我看什么代码都觉得这里可以用二分查找优化那里可以用散列表加速。结果有一次在一个只有十几个元素的列表上用了二分查找代码复杂了一倍性能提升却微乎其微。后来我明白了一个道理算法优化要看数据规模小数据量下简单直接的代码往往更好。第二个坑是递归没有设置好终止条件。写一个递归处理树形结构的函数时我忘记处理节点为空的情况结果程序直接栈溢出。后来我养成了一个习惯写递归函数时第一件事就是把所有基准情况列出来确保每一种可能的输入都有对应的处理。第三个坑是散列表的键设计不当。我用一个包含多个字段的对象作为字典的键但没有正确实现哈希函数导致两个内容相同的对象被当成了不同的键。查了半天才发现问题。后来我记住了用自定义对象做散列表的键时一定要确保哈希函数和相等判断是一致的。9.3 给正在读这本书的人的一些建议如果你正在读《算法图解》或者类似的书我有几个建议。第一不要追求速度。这本书虽然薄但每个概念都值得花时间琢磨。我第一遍读只用了两天但真正理解这些概念花了几个月。第二动手写代码。书上的伪代码看起来简单但自己实现时会遇到各种边界问题。第三尝试给别人讲。如果你能把二分查找、快速排序、广度优先搜索讲给一个完全不懂的人听并且他能听懂那你就真的掌握了。最后不要害怕忘记。这些概念不是背下来的是用出来的。我在实际项目中用过散列表、用过递归、用过广度优先搜索之后对这些概念的理解才真正深刻起来。所以读完书之后找一些小项目练练手哪怕只是写一个简单的通讯录、一个迷宫求解器都会比单纯看书收获大得多。算法不是一门学完就扔的课程它是一种思维方式。当你习惯了用二分查找的思路去缩小问题范围用递归的思路去分解问题用广度优先搜索的思路去一层层探索可能性你会发现这种思维方式在很多领域都用得上。这大概就是读这本书最大的收获——它教的不只是算法更是一种解决问题的视角。