时间复杂度怎么算：拿冒泡排序、二分查找、归并排序逐步数出来

先把“时间”变成能看见的操作

时间复杂度可以先理解成：输入规模变大后，某种基本操作会增长多快。它不依赖某台电脑跑得快还是慢，所以不必比较毫秒数，而应数比较、交换和写回。

在演示台里点击“前进”，观察高亮伪代码、数组、lo/hi/mid 等变量以及计数器；点击“后退”还能逐帧复核。计数时先固定输入和口径：冒泡要分清“比较”和“交换”，二分不能把一轮循环直接当成一次比较，归并则只统计元素写入合并结果的次数。

在本演示的默认输入 38, 12, 71, 5, 44, 26, 90, 17 上，每次执行 if a[j] > a[j+1] 时记一次比较；条件成立，再把交换计数器加一。更新循环下标、设置 swapped 都不另算交换。本演示的这份输入实测为比较 27 次、交换 13 次。

交换次数为什么恰好等于逆序对数，可以直接用这串数检查。逐个左端元素看：

合计正好是 13 个。冒泡只交换“前大后小”的相邻元素。一次这样的交换会让逆序对数减少一个，不交换则保持不变；排好序后不再有逆序对，所以交换总数必然等于初始逆序对数。

这也是为什么不能把某次输入的 13 次交换推广到所有输入。若换成本来有序的输入，第一轮没有交换，swapped 为假，算法立即结束，只比较 n−1 次。

二分查找的前提是数组有序。在本演示的有序数组 [5,12,17,26,38,44,71,90] 中，不要只记数组中间位置变了多少。先在每帧记下 lo、hi 和 mid，再观察条件分支何时让页面的比较计数器增加；数组区间如何收缩，是用来检查查找路径的，不应直接代替比较计数。

本演示的这份输入得到：

规模翻倍实验采用“找最左端”的最坏情况记录：n=8、16、32、64 时，比较次数依次为 5、7、9、11。因此，在这个实测记录中，规模每翻一倍，比较次数增加 2，不能据此声称所有目标都固定如此。

还要区分“比较次数”和“循环轮数”。每轮可能检查等号、大小关系，页面伪代码给出的轮数上界是 ⌊log₂n⌋+1；例如 1,000,000 个数最多 20 轮。比较计数器应按条件判断记录，不能把每轮硬记成一次。

仍在本演示的默认输入上，归并排序实测比较 17 次、写回 24 次。手工统计写回时，只关注元素被写入合并结果的时刻，不把指针移动或大小比较算成写回。

这串输入共有 3 层合并，每层中每个元素都恰好被选中并写回一次，所以每层写回 8 次，合计为 8×3=24。这就是“每层都是 O(n)”的来源：层数增加时，每一层仍只把整批元素处理一遍。

拆分深度是 ⌈log₂n⌉，因此全部合并的写回次数随规模按 O(n log n) 增长。比较次数和写回次数是两条不同曲线，不要混成同一个“时间”。

曲线的横轴是规模 n，纵轴选定的操作计数。页面规模翻倍实验中的比较次数如下：

规模	冒泡排序	归并排序	二分查找最坏情况
`8`	`25`	`17`	`5`
`16`	`117`	`48`	`7`
`32`	`493`	`128`	`9`
`64`	—	—	`11`

这里的冒泡排序 n=8 记录是 25，不是默认输入表中的 27；两张表必须按各自运行记录读取，不能互换。

这些点先形成实测曲线，再结合循环结构解释增长。冒泡排序的轮数增加，每轮又要检查一段剩余区间，因此比较计数按平方规模拉开；归并排序虽然也要处理整批元素，但层数只按对数增加；二分查找每轮把待查区间缩小，轮数按对数增长。规模翻倍后，三条曲线的斜率差异会越来越明显。

保留同一输入逐帧前进：冒泡在高亮条件处记比较、在交换处记次数；二分同时记录 lo、hi、mid 和比较计数器；归并按合并层级累计写回。然后修改输入再跑一次，观察交换次数如何随逆序对改变。输入一变，原来的计数就不能直接套用到新输入。