“零基础小白算法学习日记”写到第六天了。今天这篇笔记想重点聊聊我这两天在啃的东西归并排序、分治思想以及一个特别容易把人绕晕的问题——算复杂度的时候到底什么时候用 O什么时候用 Θ。老读者都知道我前五天把数组、链表、栈、队列的基础过了一遍也写了最朴素的冒泡、选择、插入排序直到今天才第一次觉得“嗯这个确实有点算法的意思了”。如果你也是刚开始刷数据结构与算法、准备找实习或者应付面试笔试那这篇应该能帮你省掉不少自己踩坑的时间。今天的内容不算多但信息密度比较大。我会把归并排序从“为什么分治”讲到“代码怎么写”再讲到“怎么推导 O(nlogn)”最后用逆序对这个经典扩展题收尾。中间还会穿插几个自己真实踩过的坑以及我当时是怎么排查的。1. Day6 之前这五天我都学了什么1.1 前五天内容清单简单复盘一下前几天的进度方便新朋友定位自己的水平。Day1环境准备选了 Python 做演示因为好写也顺手用 C 跑过同样的例子。学了数组和链表搞清楚了数组的随机访问和链表的插入删除各自贵在哪。Day2栈、队列、哈希表。重点理解“后进先出”“先进先出”这两种约束以及哈希表为什么能把查找变成 O(1)。Day3三种基础排序冒泡、选择、插入。当时我特别喜欢拿扑克牌类比插入排序——你整理手里牌的时候就是一张一张往前插的。Day4二分查找和递归。递归是我第一次觉得头疼的地方当时花了一晚上画调用栈最后才算真正理解了“函数自己调用自己”到底是怎么回事。Day5时间复杂度的入门概念分析了前三天的排序为什么是 O(n²)也第一次看到了二分查找的 O(logn)。如果让我重新规划Day5 的复杂度内容其实可以和今天的内容合并着学因为归并排序正好是理解复杂度的最佳样本。但先学完基础再回头看复杂度也别有一番清晰感。1.2 为什么第六天要选归并排序我之前刷题的时候看到很多人直接跳去学二叉树、动态规划结果越学越迷糊。我个人体会是零基础阶段应该抓住一个既能练递归、又能练复杂度分析的经典题目归并排序就是最合适的那个。原因有三个。第一归并排序是最容易“手撕”的高级排序算法。它不像快速排序那样有 partition 的边界细节也不像堆排序那样要先理解堆结构。你只需要写两件事把一个数组从中间切开以及把两个已经有序的数组合并成一个有序数组。第二它是第一个让你真正体会到“分治”的算法。之前写的冒泡、选择、插入本质上都是一层一层扫描靠比较和交换解决问题。归并排序换了一种思路我不一次性处理 n 个数而是把 n 个数拆成两个 n/2 的数组递归地让每个子数组有序最后再合并。第三它第一次把 O(nlogn) 这个复杂度摆在了你面前。如果不学归并排序你可能永远只是“听说过 nlogn”但不知道它是怎么来的。今天我会手把手用递归树推一遍推完你就发现它其实非常自然。2. 核心内容拆解分治思想与归并排序2.1 分治三步走分治拆开讲就是“分而治之”。遇到一个规模比较大的问题先把它切成几个结构相同的小问题小问题解决了再把结果合并起来。归并排序就是最标准的分治模板。我在日记里习惯把它记成三步分解把数组从中间切成左右两半左半边和右半边继续再切直到每个子数组只剩一个元素。解决只剩下一个元素的数组天然有序所以递归在这里就可以返回了。这个“最小子问题”也叫递归基。合并把两个有序数组合并成一个更大的有序数组一层一层向上返回最终整个数组有序。这个思路可以用一个生活化的场景来理解。假设你要把整层楼的工位按工号整理成一条有序名单一个人从上到下扫一遍当然也可以但效率不高。分治的做法是把楼层分成几个区域每个区域一个人负责把工号排好最后再由一个人把几个有序区域合并起来。区域内部怎么排你不用管只要相信每个人都能搞定自己的区域就行——这就是递归里“信任子问题”的感觉。这里最需要注意的是递归基。很多人写归并排序会漏掉空数组的情况用len(arr) 1而不是len(arr) 1就是这个原因。数组为空时不应该继续切分否则就会陷入下标越界或者无限递归。2.2 归并排序代码实现用 Python 实现归并排序核心代码非常短。我第一次写完的时候甚至有点不敢相信整个逻辑就那么几行。def merge_sort(arr): # 递归基空数组或只有一个元素时已经有序 if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i j 0 result [] # 双指针遍历两个有序数组把较小元素依次放入结果 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 # 其中一个数组剩余的元素直接拼到后面 result.extend(left[i:]) result.extend(right[j:]) return result我拆开讲几个关键点。mid len(arr) // 2这里用整数除法取中间位置。切片arr[:mid]和arr[mid:]分别对应左半部分和右半部分。这里需要想清楚左边是 0 到 mid-1右边是 mid 到末尾两边没有重叠也没有遗漏。merge函数是合并的核心。两个有序数组各自维护一个指针 i 和 j每次比较left[i]和right[j]谁小谁先入结果。当一个数组被取完另一个数组剩下的元素全部直接追加到 result 后面因为剩下的元素都已经有序直接拼上去就行。比较的时候我用的是而不是这个细节很关键。你想想当 left[i] 等于 right[j] 时left 里的元素先入结果这意味着原数组中靠前的相同元素在排序后仍然靠前所以归并排序是稳定排序。如果写成相等时 right 的元素先入结果稳定性就没了。我之前学习的时候在这里还踩过一个坑合并忘了处理剩余元素。写完 while 循环之后如果没有result.extend(...)那两行你会发现当一边指针走完时另一边的元素全部丢了。这种 bug 不是必现的长度很凑巧的数组可能测不出来一定得补上。2.3 时间复杂度推导递归树与主定理这一节是今天的重头戏。归并排序的时间复杂度怎么写先说结论在任何情况下归并排序的时间复杂度都是 Θ(nlogn)。追问一句为什么我们假设规模为 n 的问题耗时是 T(n)。归并排序把数组切成两半所以可以得到一个递推式T(n) 2T(n/2) O(n)2T(n/2) 表示递归处理左右两个子数组所需的时间O(n) 表示合并左右数组需要扫描一遍所有元素。把 O(n) 当作一次线性操作。怎么从这个递推式算出结果最直观的方法是画递归树。第一层数组大小为 n在这一层要合并 n 个元素耗时 n。第二层拆成两个大小为 n/2 的子数组两个子数组各自合并每个合并耗时 n/2两层加起来还是 n。第三层四个大小为 n/4 的子数组四个合并加起来也是 n。一直往下每一层的合并总耗时都是 n。一共切了多少层每层规模减半从 n 减到 1需要 log2n 层。所以总耗时 每层耗时 × 层数 n × log2n O(nlogn)。这里可以做个生活类比。二分查找为什么是 logn你查电话本的时候每次翻一半翻多少次能找到一个人名大约就是 logn 次。而归并排序相当于你每一层都要把整个电话本的每个人过一遍所以要在 logn 的基础上再乘一个 n。这就是“每层都扫一遍”带来的代价。如果不习惯递归树也可以用主定理的简化版。形如 T(n) aT(n/b) O(n^d) 的递推式当 a b^d 时T(n) O(n^d logn)。代入归并排序a2b2d1正好满足 2 2^1所以结果是 O(n¹logn) O(nlogn)。主定理不用背能理解递归树推导就够了。空间复杂度顺带提一句归并排序需要一个临时数组来合并结果所以额外空间是 O(n)。这是它比快速排序“吃亏”的主要地方。3. 关于算法复杂度的 O 和 Θ 之争3.1 什么是上界什么是紧界我那天刷题看到一个热搜问题“计算算法复杂度时什么时候用 o 什么时候用 θ?” 这个问题本身问得有点含糊因为平时我们最爱用的是大 O而题目里可能想问的是大 O 和大 Θ 的区别。先理清这三个符号各自的意思。O(f(n))表示算法运行时间的上界。意思是“最坏情况下不会超过这个量级”。Ω(f(n))表示运行时间的下界。意思是“最好情况下至少也要这么多”。Θ(f(n))表示运行时间被上界和下界夹住了上下界是同一个量级。如果算法的时间复杂度是 Θ(nlogn)说明它既是 O(nlogn)又是 Ω(nlogn)随输入规模增长运行时间始终卡在 nlogn 这个级别上。打个比方。你点外卖商家说“30 分钟内一定送到”这是上界 O但你知道路况好时最快也要 20 分钟这是下界 Ω如果你根据多次经验发现基本都是 25 分钟左右误差很小那说明配送时间有个紧界 Θ。如果商家说 30 分钟内一定送到但有时候 15 分钟就到了、有时候 29 分钟才到你只能说上界是 30没有紧界。这里还有个容易混淆的点大 O 和大 Θ 的区别在于“信息量”。大 O 只告诉你“不会超过多少”大 Θ 告诉你“大概是多少”。一个 O(n²) 的算法实际可能运行时间是 n² 到 2n²也可能是 n 到 n²——只要是上界不超过 n²都叫 O(n²)。而如果要写 Θ就必须确定上下界都在同一个级别。小写的 o 记号在实际刷题里基本用不到它表示“严格小于”的上界。比如 n o(n²)因为 n 比 n² 低一个量级但 n O(n²) 也成立。正式分析算法时偶尔会用到但面试和考试几乎不会考到这么细。3.2 归并排序该写 O(nlogn) 还是 Θ(nlogn)这个问题我觉得特别适合零基础阶段想明白因为它背后是对“最好/最坏/平均复杂度”的完整理解。归并排序不管输入数组原来是有序、逆序还是乱序都会执行同样的拆分和合并流程。你想想代码它没有提前终止的机制不像插入排序那样如果已经有序只需要走一遍。所以最好情况Θ(nlogn)最坏情况Θ(nlogn)平均情况Θ(nlogn)三个情况都一样。那为什么很多教材和博客上都写“归并排序是 O(nlogn)”因为 O(nlogn) 也是对的只是信息量少一点。Θ(nlogn) 本身就蕴含了 O(nlogn)它表示“既是上界也是下界”。当时间复杂度不受输入顺序影响时写 Θ(nlogn) 更严谨。反过来看插入排序就非常有意思了。插入排序最好情况输入已经有序只需 O(n) 次扫描比较时间复杂度 O(n)。最坏情况输入完全逆序每次都要搬到最后时间复杂度 O(n²)。平均情况O(n²)。三个情况完全不一样所以你不能写“插入排序的时间复杂度是 Θ(n²)”你只能说“最坏情况下是 Θ(n²)”或者说“总体复杂度是 O(n²)”。如果只说 O(n)容易让别人以为它真的那么快只说 O(n²)又没体现它最好情况的优势。所以“什么时候用 O什么时候用 Θ”的答案就是当分析的是某个确定情况比如最坏情况且你能证明上下界一致时用 Θ 更精确当你不确定准确量级、只是想给一个上限时用 O。面试中被问到归并排序复杂度说“Θ(nlogn)”最能体现你的严谨程度。3.3 常用复杂度速查表我整理了一张前端时间和空间复杂度速查表刷题时经常用到。注意这里列的是常见实现的平均或最坏情况细节还得看具体写法。算法/操作时间复杂度空间复杂度备注普通数组访问O(1)-通过下标直接取链表查找O(n)-需要从头遍历二分查找O(logn)O(1)要求数据有序冒泡/选择/插入排序O(n²)O(1)最坏/平均都是平方级归并排序Θ(nlogn)O(n)性能稳定需额外空间快速排序平均 O(nlogn)最坏 O(n²)O(logn)递归栈原地排序工程常用堆排序O(nlogn)O(1)原地排序不稳定遍历连通图DFS/BFSO(VE)O(V)V 是顶点数E 是边数动态规划常见 DP视状态和转移而定可优化如背包 O(n×W)有一个问题我一开始经常疑惑为什么快速排序最坏是 O(n²)但它还是比归并排序常用因为“最坏”出现的概率低而且快排在常数因子、缓存友好度上都比归并好。这个我们放到第 4 节展开聊。4. 从归并排序延伸出去4.1 用归并排序解决逆序对问题归并排序不只是排序它还能顺手解决一个经典面试题求数组中的逆序对数量。所谓逆序对就是一对下标 i 和 j满足 i j 且 arr[i] arr[j]。比如 [5, 3, 2, 4] 中逆序对有 (5,3)、(5,2)、(5,4)、(3,2)一共 4 个。暴力办法是两层循环把每一对都检查一遍复杂度 O(n²)。数据量小的时候无所谓到 10 万级别就彻底卡住了。归并排序能在合并阶段顺手统计。核心观察是在merge比较两个有序数组时如果left[i] right[j]那么 left 中从 i 开始到末尾的所有元素都比 right[j] 大因为 left 本来就是有序递增的。也就是说right[j] 会和 left[i:] 里每一个元素组成逆序对一次就能累加len(left) - i个。代码改造如下注意计数变量的位置。count 0 def merge(left, right): global count i j 0 result [] while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: # left[i] 比 right[j] 大说明 left[i:] 都比 right[j] 大 count len(left) - i result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result这里很容易写错的是 i 和 j 的移动方向。当left[i] right[j]时累积的是 left 中从 i 到末尾的数量然后 j 前进一位。你不能把 i 也往前挪因为 i 这个位置后面还会和下一个 right 元素比较。当初我用一个长度 6 的数组手推了一遍合并过程才算彻底理顺。这个扩展题给我最大的启发是算法题很少是孤立的知识点很多都能从最基础的排序代码上长出分支。你理解了归并的“合并阶段”在做什么逆序对其实就是一次顺手统计。4.2 归并与快排的选择工程上到底用归并还是快排这是个老生常谈的问题我列几个关键对比。对比项归并排序快速排序稳定性稳定不稳定空间复杂度O(n) 额外空间原地排序额外空间小最坏复杂度Θ(nlogn)O(n²)选好 pivot 可避免是否适合外部排序适合磁盘数据不适合常数因子较大频繁分配数组较小缓存友好工程上默认排序用快速排序的变种因为它在内存操作、缓存局部性方面都更好。但归并排序在“需要稳定性”和“数据不能一次全装入内存”的场景下几乎是不可替代的。比如数据库对大量数据做外部排序就是典型的归并思想。很多语言内置排序的实现也是“快排 插入排序”等混合策略而不是简单选一个。零基础阶段不用纠结哪个更好先把归并代码写熟再去写快排的 partition然后对比着理解两个都能吃透。4.3 分治思想在更多热门算法中的体现分治并不止归并排序一个孩子。今天学完归并后我在刷题时看很多热门算法都有“拆子问题”的影子。快速排序是分治只是它的合并阶段几乎不用额外工作难点全在 partition 这个切分函数上二分查找是分治的退化版本它只拆一个分支不合并所以复杂度只有 logn最近点对问题把平面上的点按 x 坐标分成左右两半递归找左右最近点对再检查中间条带里的点大整数乘法用 Karatsuba 算法减少乘法次数也是分治。再往后学你会遇到动态规划和贪心。动态规划的核心是定义状态和推导转移方程本质上也像在“拆子问题”但它更强调子问题的重叠和状态复用而不是简单分叉贪心算法则是每一步都选当前看起来最优的决策希望最终得到全局最优。这些概念现在接触可能有点早但脑子里先有一个“算法知识地图”是有好处的。今天学会归并排序后再回头看之前学过的二分查找你会觉得“原来二分也是一种分治”。触类旁通的感觉是学习算法最有成就感的时刻。5. 实操中的坑与后续路线5.1 今天踩过的三个坑第一递归基写成了len(arr) 1。第一次跑归并排序时输入数组长度是偶数还没暴露问题一旦输入了空数组直接报下标越界。后来改成len(arr) 1一次性解决问题。记住递归函数里边界情况要用 或 明确想清楚。第二合并时漏了剩余元素追加。这个问题发生在 while 循环结束后左右两边长度不一致时。我的第一次实现少写了result.extend(right[j:])结果排序结果总是断续少几个数。排查方法很简单找一个长度为 7 的数组在 merge 函数开头打印 left 和 right就能看到每次合并输出的结果不对。第三我曾试图第一天就写“原地归并排序”不借助额外数组然后陷入各种下标混乱的泥潭。后来我放弃了老老实实用临时数组。实话讲原地归并的实现方式非常绕属于进阶内容零基础阶段没必要花这个时间。先把非原地版本写到流畅过段时间再来看“手摇算法”或自底向上的迭代写法会轻松很多。调试这类递归算法我自己的经验是不要拿很大的数组测试用一个长度 5 或 6 的小数组手动模拟每一步。还有就是多用打印特别是在每次 merge 前后打印数组状态比盲猜更快定位。5.2 第六天之后的算法学习路线我一直觉得零基础学算法最怕的不是学不会而是没有节奏。第六天之后我给自己排了下半个月的路线你可以参考一下。排序收官快速排序、堆排序、希尔排序。重点理解快排的 partition 为什么能把数组分成小于等于和大于两部分。双指针与滑动窗口很多数组和字符串题都能靠这两个技巧把 O(n²) 降成 O(n)。二分答案在“解空间”里二分搜索最优答案最经典的例子是求最大值最小化问题。贪心入门区间调度、跳跃游戏、找零钱这些经典题。贪心不一定总是正确学会证明“为什么局部最优能达到全局最优”。动态规划基础先做斐波那契、爬楼梯、最长递增子序列。关键是理解状态定义和转移方程而不是背模板。字符串专题KMP、Trie 字典树。KMP 的核心是 next 数组如果今天分治思想理解得好KMP 你会觉得更加亲切。图论搜索DFS/BFS、拓扑排序、最短路径。这是面试里的高频模块但从现在开始准备完全来得及。每个专题我不建议贪多能认真做 3 到 5 道题再横向对比解法进步会非常明显。5.3 今天的作业和自测今天的内容建议搭配三个小练习一起做。第一手写归并排序然后测试这个乱序数组[3, 1, 4, 1, 5, 9, 2, 6]。注意里面有两个 1排序后要保持稳定。第二用归并排序改造求解逆序对自己生成一个长度为 1000 的随机数组验证暴力方法和归并方法结果一致。这个对照能非常有效地帮助你确认排序合并逻辑没写错。第三写一个快速排序和归并排序跑同一个 10000 元素的随机数组用time模块比较两者的运行时间体会一下常数因子的差异。自测题可以快速在脑子里过一遍为什么切分时mid要取len(arr) // 2而不是len(arr) / 2归并排序的稳定性和有什么关系用一句话解释为什么T(n) 2T(n/2) O(n)的解是O(nlogn)如果三分钟之内都能有思路说明今天的内容算是真正吸收了。最后分享一个小体会。写归并排序的时候我第一次感受到“递归其实是可以信任的”你不需要跟踪每一层递归的细节只要保证“拆分正确 合并正确 边界正确”整个算法就会正确。这个体验比背十个排序模板都重要。第六天结束整个人的感觉是以前觉得“算法”是玄学现在终于觉得它是一门可以拆解的工程学。