51天算法学习笔记：用“更弱智”的笨办法啃下排序、KMP与递归

说实话我翻了下自己这50多天的笔记有点意外。51天前我还是一个连“时间复杂度”都说不利索的人现在居然能在一堆排序算法、KMP、甚至一点强化学习的概念里打个滚虽然姿势依然笨拙但至少没再原地打转。这个系列叫“更弱智的算法学习”不是自嘲是真自嘲。因为我用的方法确实笨不背模板、不追求一天刷三道题而是每天只啃一个点用最直白的话把它讲清楚讲到我那个完全不懂编程的室友能听懂为止。今天正好第51天我打算把这几天踩过的坑、用过的方法、和一些突然开窍的瞬间整理一下给同样在这条路上挣扎的朋友一个参考。这篇东西适合谁看大概就是那种和我一样数据结构与算法基础不牢、看网课总在“马冬梅”阶段反复横跳、刷题刷到怀疑自己是不是智商有问题的人。也适合刚想系统接触算法、但被满屏术语劝退的新手。我可以很负责任地说如果能坚持用我这套“更弱智”的笨办法51天后你回头看一定会吓一跳。1. 先说实话为什么我敢把学习笔记叫“更弱智”1.1 承认自己笨反而学得进去大半年前我在职业路上遇到了一个尴尬的现状要做的事越来越依赖算法和数据结构可我在大学基本是混过来的。那时候刷题目标是“AC”做法是“背”。背了一堆模板换一道变体题立刻不认识。我一度以为是自己记忆差后来发现真正的问题是我压根没理解这些算法在做什么。后来我想通了——既然聪明人用的“举一反三”我学不来那我就用笨办法把自己当成一个确实理解力很差的人每遇到一个算法我必须完成三件事用一句话说清楚它解决什么问题画一张图或写一个例子走一遍完整过程把这个算法讲给一个完全不懂的人听讲到对方点头。这三件事做完才算“过”。这个标准不高但极花时间。刷一道归并排序聪明人可能5分钟看完就继续下一题我要折腾一天。可这51天坚持下来效果出乎意料以前背了就忘的KMP现在我能自己推导出next数组以前看到“递归”两个字就头皮发麻现在我能在纸上手动把递归栈画出来讲给别人听。这就是“更弱智”给我的第一个启发笨办法的本质其实是把“被动接收”改成“主动重建”。1.2 这个系列为什么能坚持到51天我能坚持下来靠的不是意志力而是把目标切碎了。我给自己定的规矩特别简单每天只认真搞懂一个算法或一个数据结构概念当天必须在笔记里写下一个“生活化类比”当天必须用口头讲述一遍录音讲不顺就说明没懂第二天重来。这样一天一个点没有“一天不看就落后”的焦虑。51天下来我积累了三四十个核心算法的“问题卡片”每一张都写得歪歪扭扭但都是我自己的话。相比那些“一天刷10题”的大佬我这个进度简直是龟速。可我清楚记得一个月前学的堆排序现在还能手写出来因为我真的把“建堆、调整”的过程像讲一个掰手腕的故事一样讲透了。如果你也在学算法我真心建议你试着把姿态放低一点“更弱智”不是一个丢人的词它意味着你愿意从最笨的地方开始把所有东西重建一遍。地基打牢了后面才能盖楼。2. 五十天的知识地图算法到底分哪几类2.1 排序与字符串绕不开的老朋友这51天里我最先啃的就是排序。因为排序算法太适合练手了数据规模小、过程直观、非常适合用来理解循环、递归、分治这些基础思想。先说冒泡排序算法C写起来最顺它就是个“胖子上岸”的过程一趟一趟地把最大数冒到最后交换次数多时间复杂度是 O(n²)。归并排序则完全是另一种思路它把数组一分为二、二分为四分到不能再分然后两两合并属于典型的分治。堆排序又不一样它借助完全二叉树这种结构用“建堆反复取堆顶”来完成排序时间复杂度稳定在 O(n log n)。这里贴一段我后来能默写的归并排序核心代码C算是我“笨办法”的一个成果void merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p 0; p k; p) arr[left p] temp[p]; }字符串算法我花了更长的时间尤其是KMP算法。它解决的核心问题是在一个主串里找一个模式串暴力法会不停回退主串指针KMP却能利用模式串自身的“重复信息”跳过一些比较。理解next数组最长公共前后缀长度花了我至少一周时间。2.2 图论与搜索名字吓人思路相通第20天左右我开始碰图论。Tarjan算法、匈牙利算法、弗洛伊德算法这三个名字放在一起像三座大山。但真啃下来发现思路并不复杂。弗洛伊德算法就是“城市中转查询”从i城到j城如果绕道k城比直达更近就更新距离。三层循环把每个城市当中转站试一遍最后得到任意两点间的最短路径。粒子群算法原理我是在学完贪心之后看的它更像一群鸟在找食物每只鸟不仅跟着自己的经验飞也参考群体的最优位置这属于启发式搜索的一种。A*算法原理图我画过好多遍它相当于在Dijkstra最短路径的基础上用一个估算函数启发函数告诉搜索“哪个方向更可能近”搜索时优先走向目标方向的分支再配合剪枝算法提前排除不合适的路径性能一下子就不一样了。我的体会是图论和搜索这块名字唬人但底层都可以用“地图”或“排队”的心理模型套进去。Tarjan算法求强连通分量像在迷宫里做记号遇到重复记号就说明绕回来了可以收网。2.3 控制、信号与机器学习算法其实很“出圈”学到后面我发现算法不只是面试题。PID算法程序代码实现用来控制电机转速烟雾传感器里的滑动平均滤波算法是拿连续几次读数的平均值去抖md5算法是哈希函数做完整性校验。这些算法虽然在在线题库里不常见但它们在工业界和嵌入式领域每天都在跑。机器学习相关的算法我也在day51这天做了个简要梳理——聚类算法像整理衣柜把相似的衣物挂到一起随机森林回归算法像是开专家会诊一群水平一般的决策树投票反而比单个专家的判断更稳定强化学习算法像训小狗做对了给零食做错了不给奖励慢慢就能学到一个好的策略。这么一看算法地图其实很广阔用“更弱智”的心态去学核心就是抓住每个算法的“应用场景”而不是尽快把代码背下来。因为场景记住了自己慢慢推导就能把整个流程走通。3. 用生活比喻把最难的算法讲成人话3.1 归并排序新生报到分宿舍归并排序为什么好懂因为它太像大学新生报到的“分宿舍”了。你有一整个年级的新生随机站在操场上现在要求按身高排队。最笨的办法就是让他们两两比、不断交换冒泡效率很低。归并排序的思路是把这个年级分成两半再分成两半一直分到每个宿舍只有一个人——一个人肯定是排好序的。然后相邻宿舍开始合并两个有序的宿舍按身高挑人合成一个更大的有序队列一路合回去最后整个年级就排好了。这个类比的好处是能直接把“分治”和“合并”两个核心概念讲清楚。合并的那一步才是归并排序真正干活的地方两个有序数组用双指针比大小小的先放入结果数组类似两堆扑克牌比大小往中间放。论复杂度归并排序每一层都要访问完所有元素每层 O(n)拆分的层数是 log2(n)所以时间复杂度是 O(n log n)。每次合并都要额外空间空间复杂度是 O(n)。这个推导配合“分宿舍”画面我一遍就记住了。3.2 KMP算法错题本与书签KMP算法我用了最长时间因为next数组太抽象了。后来我换了一个比喻错题本。假设你是一个正在背单词的学生你手头有一本“单词表”。查单词时你可以从第一个字母开始往后翻翻到要找的那个词为止但如果上次查“abandon”翻到了第10页这次查另一个以“ab”开头的词你肯定直接翻到第10页附近而不是从头开始——这就是KMP干的事它把模式串自身的“重复结构”记录下来一旦匹配失败主串指针不用回退到开头而是根据next数组跳到下一个可能匹配的位置。next数组的本质就是模式串每个位置之前的子串的“最长公共前后缀长度”。比如模式串是“ABABC”算next[4]对应的子串“ABAB”前缀“AB”和后缀“AB”相同长度2所以下次失配就可以利用这个信息跳到2。我做了几十遍手动推导把每一步都写成“书签”的比喻才算真正理解它。3.3 贪心 剪枝相亲和摘菜贪心算法永远选眼前最好的一条路不看后面。用相亲来类比最合适见一个觉得还行就定了绝不回头比较。问题在于“眼前好”不等于“全局好”所以贪心算法必须证明局部最优能推出全局最优。比如找零钱问题用面额20、10、5的币值给顾客找35元先拿20、再拿10、再拿5恰好最优这是贪心可以解决的场景。剪枝算法更简单——摘菜。烂叶子在篮边直接扔掉不用拿回家再挑。搜索算法里如果某个分支已经比当前最优解还差就提前掐掉。配合A*算法的启发函数能有效避免在不可能的路径上浪费计算。这种思路我在这几天优化一个“最小步数走迷宫”类似的搜索题时反复用到实测下来效果立竿见影。4. 实操记录day51 我是怎么啃下归并排序的4.1 从“背代码失败”到“画图成功”day51这天我其实没学新东西而是把之前学的归并排序“重做”了一遍。原因是我发现自己虽然能默写代码了但隔了几天再看还是不能立刻在脑海里复现“整个过程”。这明显是没懂透。所以我把以前背的代码扔到一边拿出一张A4纸写了一个长度为8的数组[38, 27, 43, 3, 9, 82, 10, 1]然后开始手工追踪归并排序的每一步。我先画拆分把数组从中间切开切到只剩单元素。再画合并两个单元素合并成有序双元素两个双元素合成有序四元素接着合成八元素。这么一画我发现以前一直模糊的“递归”突然具体了递归不是玄学它只是用一个函数处理子任务子任务和父任务做同样的事只是规模更小。我只要关心“合并两个有序数组”怎么写递归会自动把数组切成小块。这就像分宿舍你只管合并两个宿舍分到底的单人宿舍不用你操心递归栈会帮你处理。4.2 我的“弱智笔记”长什么样我在笔记里给归并排序写了一个“问题卡片”结构往往是这样的问题如何把无序数组排成有序最笨解法冒泡每次相邻比较一轮找最大。O(n²)。聪明解法分治。拆到最小再两两合并。复杂度O(n log n)每层O(n)共log n层。画面记忆新生报到分宿舍先拆后合。代码模板见上一节。易错点合并且一边先结束剩下全部接过去。这个卡片最上面我还会画一张“过程图”简陋但清晰。画图的过程其实是把抽象逻辑“视觉化”的过程大脑对这种信息记得非常牢。很多看起来复杂的算法一旦能画成图难度立刻降一半。4.3 把归并排序讲给完全不懂的人听现场模拟我室友是个学美术的完全不懂代码。day51这天我就拿他试刀。我说“有八个同学随机站在操场上要按身高排成一队。规则是先把人从中间分成两队再分再分直到八个人各站各的。然后相邻的两个人开始比身高矮的站左边高的站右边两个人排好了。接着两个两人梯队再合成四人梯队合成的时候两个梯队已经有序了只要从左往右比谁矮先站谁最后就合成一个四人有序列再往上合八个人就排好了。”他听完说“这不是分久必合合久必分吗”我说对。能用一个外行能理解的画面讲清一个算法那才叫真懂。我从这51天的经验里确认了一件事如果你给一个朋友讲算法讲着讲着自己先卡壳了那一定是有某个细节你还没理解透而那个细节就是你后续题目做不出来的根源。5. 踩坑实录算法学习路上的五个深坑5.1 递归边界写错直接栈溢出有一阵我写归并排序的递归拆分函数边界条件是if (left right) return;结果有一天我写成if (left right) return;——数组为空时递归不停直接死循环。排查了很久才发现原来当左边界大于右边界时也是一种空区间情况。这给我的教训是递归边界必须要涵盖所有可能的“不能再拆”情况。5.2 合并循环漏掉剩余元素写归并排序的合并那一段我多次忘记在while循环结束后把左右两边剩余的元素放入临时数组。效果就是排完序后数据变少或出现随机垃圾值。后来我养成一个习惯凡是循环结束立刻问自己“还有哪个列表没扫完”把剩余部分接上。这个习惯救了我好几次。5.3 KMP的next数组到底是前缀还是后缀KMP里有一个历史遗留的迷惑点next数组和PMT部分匹配表的区别。有一版教材next数组表示“失配后跳到哪”另一版表示“最长公共前后缀长度”。我一度把两份搞混导致代码里查表错位。解决办法非常简单粗暴彻底扔掉第二种定义只记一个版本——next[i] 表示“模式串[0..i]的最长相等前后缀长度”查表的时候j next[j-1]。先定义清楚再写代码就不会乱。5.4 时间复杂度估算错误学堆排序时我以为建堆的复杂度是 O(n log n)后来仔细推导发现建堆其实是 O(n)因为堆中较高层的节点少每次下调高度小。这个细节让我意识到复杂度不能靠感觉记要亲手算一遍。计算算法复杂度的关键就是看“操作数”和“规模”之间的关系循环嵌套乘起来分治用主定理或递归树。5.5 贪心永远第一个想到却常常是错的刚开始做优化类问题凡是看到“最X”就默认用贪心。结果经常在部分测试用例上翻车。长期踩坑后我总结了三条检查规则当前选择会不会影响后续选择不影响才能贪心能不能举出反例举不出才敢用有没有更简单的证明思路比如交换论证或归纳法。这三个问题不过关就不要硬套贪心老老实实回去看动规或搜索。6. 这套“弱智”学习法的完整模板可以直接抄6.1 每天30分钟的固定流程我很多朋友问一天一个点到底怎么操作我总结了一套完全可复制的流程每天大概30分钟到1小时第一步5分钟挑一个算法题目不急着看答案先拿笔把题目抄在笔记上用自己的话写“这是个什么问题”。第二步10分钟画图。不管是数组、树、图把输入画出来笨办法走一遍。第三步10分钟看答案或参考代码找到“聪明解法”到底聪明在哪把那个关键点用一句话写在卡片上。第四步5分钟把整个思路讲给假想的“外行”听。口头讲一遍讲不下去就回去看图。第五步5分钟合上答案默写核心代码或写一遍主要步骤。这套流程听上去很笨但它把一个知识点从“听到”变成了“输出”别人是灌进去你是自己造一遍。造一遍的东西才是你的。6.2 复习节奏与防遗忘策略遗忘是正常的我不追求过目不忘但我会用“间隔复习”来对付它。具体的节奏是学完某个算法后的第1天、第3天、第7天、第15天各花5分钟重看问题卡片在心里复述过程。第15天如果还能讲清楚这个点基本就永久沉淀了。我用这个方法把堆排序、KMP、Tarjan这些难度不一的知识都稳定保留下来了。6.3 方法论背后的心态建设最后想说的是心态。我用“更弱智”当系列名也有给自己松绑的意思我不是天才学得慢很正常。学术圈总觉得“聪明人”才配搞算法可现实里大部分程序员都和我一样是普通人需要慢慢磨。如果你也想开始或者正在挣扎我送一句话别嫌自己慢别怕丢脸每天把一个小点真正嚼碎咽下去。一个月后你会发现自己像换了个人。这51天里我最受益的并不是记住了几个算法而是学会了一种“重建知识”的方法。后面的第52天、第100天我还会继续写下去。哪天你路过发现我有讲错的地方欢迎来骂醒我。算法这条路一个人走有点冷几个人一起“更弱智”地走反而热闹。