ocgOpen Cognitive Graph · CDC v2.1

方法与书籍/书籍/algorithm-instinct

算法的本能:你本来就会的计算直觉

数据结构是约束的形状,算法是代价逼出来的路:从便签、排队、查字典里认出你早已会的东西。

语言 · 中文The Instinct of Algorithms: The Computational Intuition You Already Have

-- 人工智能素养数据结构与算法篇

数据结构,是约束的形状。
算法,是代价逼出来的路。

数据结构部分大纲(生活直觉版)

定位:算法是“你怎么做”。数据结构是“你把它放在哪?”。你不是在学计算机怎么存东西。你是在学——当你面对一堆东西,要快速找到、放进去、取出来的时候,你其实已经发明了这些结构。只是你自己不知道。

贯穿原则:每一章从一个你每天都在做的动作开始。那个动作背后,就是一个数据结构。我们只是把它拆开,让你看见形状。

第一章 纸带与便签:栈的必然

场景:你在读一本书。看到一个陌生的词,你去翻词典。翻词典的时候,又看到一个更陌生的词,你又去翻另一本词典。你需要记住:我原来读到哪一页了?

你拿了一张便签,写上“第37页”。后来你又拿了一张便签,写上“第82页”。你把第二张便签贴在第一张上面。查完第二个词,你拿走最上面的便签,回到第82页。查完第一个词,你拿走下一张,回到第37页。

你已经做的:后进先出。最后贴的那张便签,最先拿走。

形状:栈,就是那条进去了必须原路返回的窄巷。进去的顺序和出来的顺序,是反的。

为什么必须是这个形状:因为你每次只能把便签贴在最上面。下一次要拿,也只能从最上面拿。这是物理世界给你的约束。栈不是谁设计的,是这个约束下面唯一能工作的办法。

你在哪里见过:函数调用(一个函数调另一个函数,返回地址叠在一起)、撤销操作(Ctrl+Z 往回退,最后一次操作最先撤销)、括号匹配(最里面的括号最先闭合)。

样章:

栈:纸带上的返回问题


一、纸带

1940年代。

计算机没有屏幕,没有键盘,没有内存条。只有一条长长的纸带。

纸带上打着一排一排的孔。每一排孔是一个指令。计算机读一排,执行一排,然后纸带往前滚一排。

计算机只知道“当前这一排”。它没有“回去”的能力。

就像一个人走在一条只有前进方向的路上,只能看见脚下这一步。他看不见身后,也看不见远处。


二、一个子程序

纸带上有一段代码,是用来做乘法的。乘法很复杂,需要很多步。

每次需要乘法的时候,你不想把这段代码重新打一遍。你只想“跳到”那段乘法代码,执行完,再“回来”继续往下走。

纸带确实有“跳转”指令。跳转指令的作用是:把纸带直接移动到某个位置。

比如你现在在第8排,需要乘法。乘法代码从第52排开始。

你执行一条指令:JMP 52

纸带开始往前滚动,滚到第52排。然后继续执行。

问题解决了前半部分:跳过去。


三、回来

乘法代码执行完了。现在你必须回来。

回来哪里?回到刚才离开的那个位置——第8排——的下一排,第9排。

因为如果你回到第8排,你会再次执行跳转,然后无限循环。

所以你要回的,是第9排。

问题是:计算机怎么知道要回第9排?

纸带不会自动记住。第52排的乘法代码,也不知道是谁调用它的——它可能被很多地方调用,每次回来的位置都不同。

你必须在跳转之前,把9这个数字记下来。


四、记在哪里

你可以把9写在纸上。但计算机没有纸和笔。

计算机能写的,只有纸带本身。

你可以在纸带上找一个空白区域,专门用来记返回位置。

每次跳转前,把返回位置写进去。

每次返回时,去那个区域读出来,跳过去。

这已经可以工作了。但有一个新问题。


五、嵌套

乘法是一个子程序。

现在,除法也是一个子程序,从第80排开始。

乘法的代码里,有时也需要用除法。

所以:

  • 主程序在第8排,调用乘法(跳到52,记下返回位置9)
  • 乘法在第57排,调用除法(跳到80,记下返回位置58)

现在,纸带上的那个“记录返回位置的区域”里,写的是什么?

是58。9被覆盖了,丢掉了。

除法执行完,需要返回58。这没问题。

但乘法执行完,需要返回9。9已经没了。


六、一串位置

问题很清楚:

返回位置不是一个,是一串。

而且,需要的顺序是:最后记下来的,最先用到。

除法是最后调用的,所以它最先返回。乘法是先调用的,所以它后返回。

如果你有一个地方可以写一串数字,并且总是从最后写的那一个开始读——

这个问题就解决了。


七、栈

这就是栈。

栈不是一个复杂的数据结构。它是一个按顺序写、按相反顺序读的位置记录器。

想象一堆便签纸:

  • 主程序调用乘法:写一张“9”,贴在最上面
  • 乘法调用除法:写一张“58”,贴在“9”的上面
  • 除法结束:拿走最上面的“58”,跳过去
  • 乘法结束:拿走现在最上面的“9”,跳过去

后进先出。后来放上去的,最先拿走。

不是谁发明的规则。是你只能这样——你只能从最上面拿,因为下面的被压住了。


八、为什么必须是栈

现在你可以问:为什么一定要用栈?不能用别的吗?

可以。你可以给每个子程序分配一个固定的格子,专门记它的返回位置。

但这里有一个更深的约束:

同一个子程序可以被多个地方调用。

乘法可以被第8排调用,也可以被第20排调用,还可以被第57排调用。

如果给乘法分配一个固定格子,它只能记住一个返回位置。后调用的会覆盖先调用的。

你需要的不是“每个子程序有一个格子”,而是“每次调用有一个格子”。

而且这些格子必须按调用顺序组织,按相反顺序使用。

栈不是唯一解。但它是最简解。

在纸带资源极其有限的1940年代,最简解就是唯一解。


九、纸带变成CPU

七十多年后。

纸带消失了。取而代之的是内存——一条长长的、线性的地址空间。

0x0000, 0x0001, 0x0002, 0x0003... 一直排下去。

CPU有一个寄存器叫PC(Program Counter,程序计数器),指向当前指令的地址。

它和纸带上的“当前第几排”是一模一样的。

调用子程序:CALL 0x5200

  • CPU把返回地址(PC+1)压入栈
  • PC变成0x5200

子程序结束:RET

  • CPU从栈顶弹出返回地址
  • PC变成那个地址

纸带上的“第9排”,变成了内存里的“0x0009”。

逻辑一丝没变。


十、栈是什么

栈不是一种“数据结构”。

栈是线性执行序列上,嵌套返回问题的必然形状。

只要满足三个条件:

  1. 执行是线性的(纸带、内存地址、指令序列)
  2. 可以跳转到别处执行,之后必须返回
  3. 跳转可以嵌套

你就必然需要一个后进先出的位置记录装置。

你可以叫它栈,可以叫它返回堆栈,可以叫它调用栈。

名字不重要。形状是必然的。


十一、画面

现在闭上眼睛。

一条米黄色的纸带,从左往右缓缓移动。上面有一排一排的小孔。阳光从孔里透过来。

纸带停在第8排。这一排的孔,形状是JMP 52。

纸带开始快速滚动。52排。

继续执行。57排。又是一条JMP 80。

纸带再次快速滚动。80排。

执行。执行。结束。

纸带往回滚动。不是真的往回滚——是有一个地方,记着“58”。计算机把纸带直接拉到第58排。

继续执行。结束。

纸带再次被拉回到“9”。第9排。

继续执行。

纸带始终只往前滚。但那个记录位置的东西,让计算机随时知道:我刚才在哪里,我现在该回哪里。

那个东西,就是栈。


十二、你学栈的时候

你学栈的时候,老师可能说:栈是一种数据结构,后进先出,有push和pop操作。

你可能写过栈的代码。你可能用栈做过括号匹配。

但括号匹配为什么用栈?

因为括号是嵌套的。嵌套的返回问题,就是栈。

函数调用为什么用栈?

因为函数调用是嵌套的。嵌套的返回问题,就是栈。

递归为什么用栈?

因为递归是嵌套的。嵌套的返回问题,就是栈。

栈的素养,是看见嵌套,就看见栈。

不是记住定义。是看见结构,就知道数学形状。知道数学形状,就知道为什么必须是这样。

纸带和CPU,没有本质区别。

1940年代和2020年代,没有本质区别。

计算,始终是一条线性的序列。嵌套返回,始终需要后进先出。

这就是栈。

第二章 排队与叫号:队列的公平

场景:你在银行排队。先来的人先办。后来的人后办。你拿了一个号,上面写着“第47号”。你等着,听到叫“第45号”“第46号”……然后是你。

你已经做的:先进先出。先拿到的号,先被叫到。

形状:队列,就是那条从一头进去、从另一头出来的管道。进去的顺序和出来的顺序,是一样的。

为什么不是栈:栈解决的是“嵌套”——你进入一个事情里面,再进入一个更深的事情,回来的时候先回最近的。队列解决的是“先后”——任务之间没有嵌套关系,只是按时间顺序到达。谁来约束你这件事的性质,就决定了你用什么结构。

你在哪里见过:打印队列(先提交的先打印)、消息队列(微信消息一条一条发,先发的先收)、BFS(一圈一圈往外扩散,先到的先处理)。

第三章 书架与抽屉:数组与链表的两种人格

场景一:你有一排书架,每一格是固定大小的。你知道第三格放着那本红皮书,你直接走过去,抽出来。但你想在第二格和第三格之间加一本新书?你得把第三格及以后所有的书都往后挪一格。

场景二:你有一堆散放的抽屉,每个抽屉上贴着纸条,写着“下一个抽屉在左边第三个”。你要找某样东西,得从第一个抽屉开始,顺着纸条一个一个翻。但你要加一个新抽屉?很简单,随便放哪,改一下隔壁抽屉的纸条就行。

你已经做的:场景一是数组——连续存放,查得快,插得慢。场景二是链表——分散存放,插得快,查得慢。

形状:两种互补的“放东西的形状”。一个是一整排固定格子,一个是一串用线串起来的散格。

为什么没有完美的:因为你不能同时要求“连续”和“灵活”。连续,就得预留整块空间,插入就得搬家。灵活,就得靠指针串起来,查找就得顺着走。这是物理约束,不是设计缺陷。

你在哪里见过:数组是CPU缓存的最爱(连续内存),链表是操作系统内核的常客(动态分配、无锁操作)。

第四章 药房与快递架:哈希表的直接到达

场景一:你去药房拿处方药。药师什么都不翻,直接走到某个抽屉前,拉开,拿出你的药。因为你的药名首字母对应一个固定的抽屉编号。

场景二:你去取快递。快递架按手机尾号分格,你的尾号是37。但37号格子里有三个包裹,你需要在这三个里再翻一下。

你已经做的:哈希表的核心逻辑——把东西的名字(键)直接算成它在哪里(位置)。中间省掉了“查找”的过程。

形状:哈希表,就是一张巨大的药房抽屉墙。每个东西的名字,经过一个换算(哈希函数),直接变成一个抽屉号。

那个“再翻一下”是什么:哈希冲突。两个不同的药名,偶尔会分到同一个抽屉。这是没法完全避免的。所以抽屉里有时候需要再翻一下。

为什么它这么快:因为算位置比找位置快。翻一千个格子需要一千步,算一个抽屉号只需要一步。空间换时间,是人类最古老也最聪明的交易。

你在哪里见过:数据库索引、缓存系统、Python字典、密码存储(哈希密码)。

第五章 文件夹与族谱:树的层级

场景一:你打开电脑的文件管理器。有一个根目录,里面有“工作”“学习”“娱乐”。点进“工作”,里面有“项目A”“项目B”。点进“项目A”,里面有“代码”“文档”“ppt”。你可以一层一层往里点,也可以一层一层往后退。

场景二:你画了一张家族树。爷爷在最上面,下面是爸爸和叔叔,爸爸下面是你和妹妹,叔叔下面是堂弟。

你已经做的:树,就是层级结构。一个根,往上分叉,再分叉。每个节点有上面(父节点)和下面(子节点)。

形状:文件系统的根目录是树根,每一层文件夹是树枝,每个文件是叶子。族谱是倒过来的树,祖宗是根,后代是叶子。

为什么需要它:因为东西有层级关系。你要找的东西在一个树枝下面,你顺着树枝走,就不用看其他树枝。每次分叉,你扔掉一大片。这是对数加速的直觉来源。

你在哪里见过:文件系统、HTML网页的DOM树、公司组织架构、编译器解析代码时构建的抽象语法树。

第六章 急诊室与任务列表:堆的优先级

场景:你在急诊室。不是先来先看。是病重的先看。随时有新病人进来,随时有病人看完。护士需要一眼就能知道:现在,最严重的病人是谁?

你已经做的:堆的核心逻辑——在一堆不断变化的东西里,总是能最快地拿出最“重要”的那个。

形状:堆,不是一个真的“堆”。它是一棵隐藏的树。你把它铺成一条线,但它的逻辑是:每个节点都比它下面的节点重要。最重要的那个,永远在最顶上。

为什么不像队列那么简单:队列只有一个约束——时间先后。堆有两个约束——不断有新东西进来,每次要拿的是最重要的。多一个约束,形状就得变。

你在哪里见过:操作系统进程调度(最高优先级的进程先跑)、Dijkstra算法(每次选当前最近的节点)、事件驱动系统(处理最紧急的事件)。

第七章 朋友圈与地铁图:图的网络

场景一:你在微信里看朋友的朋友。你的朋友A认识B,B认识C。你问:我能不能通过朋友链,联系到一个完全不认识的人?最短的链条是什么样的?

场景二:你在地铁图前。每条线有不同的颜色,每个站是一个点,站和站之间连着铁轨。你想从A站到B站,在哪换乘,总站数最少?

你已经做的:图,就是把东西画成点,把关系画成线。你问朋友的朋友,是在做图的遍历。你找最短的地铁路线,是在做图上的最短路径。

形状:图和树不一样。树有层级,图没有固定的根。图的节点之间可以有任何连接,可以有环(绕回去)。

为什么需要它:因为有些关系不是层级的,是网的。朋友关系、道路网络、网页链接——这些是网的形状。你要处理网的问题,你就需要图的语言。

你在哪里见过:社交网络的好友推荐、GPS导航、网页链接的PageRank、网络路由。

第八章 结构的边界:每种形状都有自己失效的地方

核心问题:你已经看过了栈、队列、数组、链表、哈希表、树、堆、图。每一种,都是一个约束下逼出来的必然形状。那么,有没有一种结构,能解决所有问题?

答案:没有。

为什么:每种结构都有自己生效的约束。栈要求嵌套。队列要求无优先级。哈希表要求好的哈希函数、低负载。树要求数据能比较、最好平衡。堆只需要局部有序。图什么问题都能描述,但遍历和查找的代价比专用结构高。

失效条件:栈放不下(溢出)、队列有序反了(用错了问题)、哈希冲突太多(退化到链表)、树不平衡(退化到线性查找)、图的路径爆炸(回退太多次)。

素养的核心:不是记住所有结构的定义,而是认出每个结构在什么约束下成立,在什么约束下失效。认出失效条件的人,不会在需要公平的地方用栈,不会在嵌套的地方用队列。

尾声:结构之上

你从纸带上的便签走到急诊室的优先排队,从书架走到地铁图。每一种结构,都是你在面对一个真实的物理约束时,被逼出来的唯一形状。

这些形状不属于计算机。它们属于你。你每天在生活里已经用它们做了无数决定、排了无数顺序、找了无数东西。

这本书做的事,只是给你一盏灯,让你看见脚下那些你已经踩了无数遍的路径——

“那条路一直都在。现在,你看见了。”

算法部分大纲(生活直觉版)

全书定位:这不是一本“学算法”的书。这是一本重新发现你早已会的东西的书。算法不是计算机发明的。是你每天都在用的思考方式。只是你自己没发现。

核心原则:每一章,先给你一个你百分之百遇到过的真实生活场景。你在那个场景里,已经自然地用了那个算法。然后我们只是把它拆开,让你看见:你刚才到底做了什么,以及这个做法能走多远。

读者的角色:你不是在学新东西。你是在认出你早已会的东西。专业读者在此基础上,看到数学结构,深化为可迁移的框架。


第一部分 众里寻他:从一堆东西里找一个

主题:找东西,是最日常的计算。你每天都在找。你有各种找法——翻抽屉、排好再找、直接伸手拿。这些找法,就是算法的起点。


第一章 翻抽屉:穷举的直觉

场景:你有一堆旧照片,想找一张“在公园拍的那张”。你怎么找?

你一张一张翻。翻到,就停。翻不到,就一直翻到底。

你已经做了:线性查找。

问题:1000张照片,最坏要翻1000张。为什么累?

认知:累的感觉,就是代价的感觉。东西翻倍,最坏翻倍。这是 O(n) 的身体感受。

转向下一步:你能不能少翻几张?要想少翻,需要什么条件?


第二章 字典的智慧:排序之后的魔法

场景:你在字典里查一个词。你怎么查?

你不会从第一页开始一页页翻。你翻到中间,看一眼,这个词在中间之前还是之后?如果是之前,你手里这本字典的后半本,瞬间不用再管。然后你对前半本,再做同样的事。每一次,你扔掉一半。

你已经做了:二分查找。

问题:1000页的字典,翻10次就够了(2^10=1024)。为什么?因为每翻一次,剩下一半。

条件:字典必须是排好序的。没排好的东西,不能这样找。

认知:查找的快慢,取决于数据是否有序。有序,是查找加速的第一个前提。


第三章 药房的抽屉:直接到达的满足

场景:你去药房拿处方药。药师什么都不翻,直接走到某个抽屉前,拉开,拿出你的药。

为什么这么快:因为你的药名(键)直接对应抽屉编号(位置)。中间没有查找过程。

你已经做了:哈希表的直觉。

问题:如果两种药恰好分配到了同一个抽屉怎么办?

场景延伸:你去取快递。快递架按手机尾号分格。你的尾号是37。但37号格子里有三个包裹。你需要在这三个里再翻一下。

你已经做了:哈希冲突的解决。

认知:哈希不是魔法。它的核心是:能算出来,就不需要找。但“算出来”有时候不完美,需要再处理一下。空间换时间,是最朴素也最深刻的交换。


第二部分 整整齐齐:让东西有序的代价

主题:有序是查找的前提。但有序不是免费的。把东西排好,本身就要花功夫。花多少功夫?怎么少花点?


第四章 打牌:每来一张插一张

场景:你在打牌。摸牌阶段,每摸一张牌,你就把它插到手里已排好的牌里。摸完了,整手牌也排好了。

你已经做了:插入排序。

问题:牌多了,插一张要往后挪一大片。为什么慢?因为每次插入,都可能要移一整段。

认知:这个做法,在牌少的时候很顺手,东西多了就明显累了。它的代价,是“搬家”的代价。


第五章 摊开来挑:反复找最值的代价

场景:你期末收了一摞试卷,要按分数排好。最自然的做法是什么?把试卷全摊在桌上,找最高分的那张,抽出来,放成一叠。再找次高分,再放上去。反复,直到抽完。

你已经做了:选择排序。

问题:50张试卷,你扫了多少遍?第一张扫50张,第二张扫49张……一共扫了1275遍。累吗?

认知:你不是不会更好的办法。你只是还没遇到更大的规模。累,是你发明更好办法的起点。


第六章 分开排,再合起来:分治的诞生

场景:1000张试卷,你一个人排不动。你怎么办?

你把它们分成两堆,叫两个人各自排。他们把排好的两堆给你。你只需要把两堆有序的合并成一堆。怎么合并?每次比较两堆最上面的那张,小的(或大的)抽出来。你不需要回头翻。

你已经做了:归并排序。

问题:排得挺快,但你需要一张空桌子来放结果。空间多用了。

认知:分治,是把大问题拆成小问题,用逻辑换速度。但速度有代价——这张空桌子是空间代价。时间空间的交换,又一次出现在你面前,不抽象。


第七章 原地分家:快排的直觉

场景:你和朋友在沙发上排照片。沙发不大,没有空桌子给你用。你怎么办?

你拿最上面一张当“基准”,把比它年轻的放左边,比它老的放右边。然后左边一堆自己排,右边一堆自己排。不需要额外地方。

你已经做了:快速排序。

问题:如果基准选不好(比如每次都选到最老的那张),左右分不匀,就会分很多层,又慢了。

认知:同一个分治思路,约束不同(这次是“没有额外空间”),形状就变了。快排,是被空间紧缺这个约束逼出来的归并排序的变体。


第八章 排序的天花板:你比了多少次?

场景:你排照片,不管是归并还是快排,好像都没能一次就排好。到底能不能更快?

推导:你每次比较,最多能排除一半的可能性(二分)。如果一开始有无数种顺序可能,你要用比较来找到唯一正确的那一种,需要比较的次数,至少要够你“二分”到只剩一种可能。这个次数是 log₂(所有可能数)。所有可能数是 n!。所以至少 log₂(n!) 次,大约是 n log n。

认知:这就是为什么所有基于“比大小”的排序,都停在 n log n。不是人类不够聪明,是数学说不可以。而你刚才亲手数了为什么。


第九章 不比较,能怎么样?基数排序的革命

场景:你要把一箱按日期分好的档案,放进按月份分格的架子上。

你不是一张张档案比先后。你把一月份的全部放到1号格,二月放2号格,然后1号格里的你就按天排。这个按月份“分类”的动作,不涉及“比大小”。

你已经做了:基数排序。

问题:为什么它比比较排序快(O(n))?因为它不是二选一,是一次就划成了12个组。它利用了“月份”这个天然的结构。

认知:算法的极限,建立在你对问题结构的理解深度上。如果你发现了潜在的天然结构(数字有位、日期有年月日),你就能绕过比较的天花板。这是知识转化为生产力的关键一跃。


第三部分 牵一发而动全身:图与关系的算法

主题:很多问题不是线性的,是网状的。朋友的朋友、最近的加油站、不换乘的地铁——这些是图上的问题。你在生活中也在做图的计算。


第十章 朋友圈的扩散:广度优先

场景:你想知道,你的一个消息,传到你所有朋友,再传到你朋友的朋友,多久能传完?第一层:所有直接朋友。第二层:朋友的朋友。第三层:再往外一圈。

你已经做了:广度优先搜索(BFS)。

工具:你把要通知的人写在一张纸上,按远近顺序,从上到下。先通知纸最上面的。

认知:BFS 就是“一圈一圈往外扩散”的顺序。你用纸记名字的那个本子,就是队列。


第十一章 走迷宫:深度优先与回溯

场景:你在玩密室逃脱或走迷宫。一条路走到黑,碰壁了,就往回退到上一个有岔路的地方,再试另一条。你手里拿根粉笔,走过的路你就划掉。

你已经做了:深度优先搜索(DFS)和回溯。

工具:你做的“回退到上一个岔路口,再选一条没走过的路继续试”——这就是回溯法的本质:穷举所有可能,但通过“划掉走不通的路”(剪枝)来避免无意义的重复。

认知:穷举不一定笨。当你能划掉确定没用的尝试(剪枝)时,搜索就变得聪明了。


第十二章 手机导航:最短路径的贪心

场景:你在陌生城市。你打开手机地图,从当前位置走到目的地。地图瞬间给出了路线,凭直觉,它似乎总是让你“走最短的”。

推导:每次你到达一个路口,都选“目前看来走最少步”的路口继续走。为什么对?因为你走的所有道路,长度都是正的——所以你确认了的最短,就不会再被更远的路刷新。一旦你走过的路口,那里的最短距离就定下来了。

你已经做了:Dijkstra算法的核心逻辑。

认知:你贪心地、每次走最短的,之所以能成功,是因为路上没有“负的捷径”。如果有,这种贪心就会失败。


尾声:认知之上

我们走完了从“翻抽屉找照片”到“贪心找最短路径”的完整旅程。

你发现了吗?整本书,你没有“学”一个全新的、和你生活毫无关系的概念。

你只是在命名你已经做过无数次的事:翻东西、插牌、合并试卷、分照片、走迷宫、记路径。

你过去不知道它们叫“算法”。但这并不妨碍你每天都在用它们思考。

算法的素养,不是让你重新学习一套外来的知识体系。它是让你认出:你本来就拥有解决问题的直觉框架,而且这种直觉,和计算机、和人工智能的底层逻辑,是相通的。

你只是需要有人告诉你:看,你做的这件事,就是这个名字。它还能用于更复杂的系统。

而对于专业的人,每一章的最后一节,我们把这种生活直觉精确地翻译成数学结构和工程实现,成为他们深化设计和优化系统的“照明灯”。