上一课我们确认了 LinearSearch 是对的。现在轮到第二问:它有多快? 你会发现"拿秒表跑一遍"这个直觉,竟然处处是坑——而绕开这些坑,正好逼出 T(n) 这个概念。
最自然的念头:用某种语言实现它,在机器上跑,拿秒表 (stopwatch) 掐时间。听起来无懈可击——直到你认真想想。
这个想法有三个致命问题。整节课其实就是逐个拆掉它们,每拆一个,就往"时间复杂度"这个概念上补一块拼图。
在规模 10 的数组里查找 vs 在规模一百万的数组里查找,耗时天差地别。
同样一百万个元素,key 恰好在第一个被检查的位置 vs key 根本不存在——差距巨大。
换语言、换机器、甚至同机器跑两次,秒表读数都不一样。根本问题。
这个最好办。既然时间随规模变,那就别指望用一个数字来描述它。
输入规模 n 指什么,取决于问题:数组的长度、图的顶点数、字符串的字符数…… 对 LinearSearch 来说,就是数组的元素个数 n。
同一个规模为 n 的输入,喂给同一个算法,耗时可以从"1 次比较"到"n 次比较"。先亲眼看看这个落差。
下面是一个规模固定 = 12 的数组,LinearSearch 从末尾往前扫。选一种输入,看看要比较几次:
同一个 n = 12,最好只要 1 次、最坏要 12 次。规模一样,命运不同——所以只报"一个时间"是不负责任的。
解法:分情况讨论 (case analysis)。 常见有四种,各有各的用途:
给出一个上界保证 (upper bound):"无论你喂什么,我保证 1 分钟内出结果。" 这种承诺最有价值,所以本课默认用它。
更贴近实际,但要假设输入的分布 (distribution)——哪种输入更常出现。分布一变,答案就变,难算。
某个操作大多数时候很便宜、偶尔很贵,那把总账摊到每次头上。经典例子是动态数组——下面就有得玩。
"我最好情况 1 秒完成!"——但最坏可能要一年。信息量极低,基本等于作弊 (cheating),现实里几乎不用。
动态数组 (dynamic array) 是一块预分配的连续内存。空间够时,插入只要放进去 = 1 次开销;一旦装满,就得申请两倍大的新数组、把旧元素全搬过去——很贵。不停点"插入",盯着底部的"摊还开销":
虽然偶尔冒出一根红色高柱,但因为每次都翻倍,贵操作越来越稀疏。把总开销摊平,每次插入趋近一个常数(≈3)——所以我们说动态数组插入的摊还复杂度是 O(1)。
这才是秒表大法的根本死穴。同一段逻辑,换 C 还是 Python、换你的笔记本还是超算、甚至同机器跑两次——数字都不一样,永远得不到一个"准确值"。
在这个模型里,我们不问"一次加法几纳秒",只问"输入翻倍,操作次数怎么变"。
下面三条线是同一个线性算法在三台机器上的耗时。切换机器,绝对数字变了,但都是直线——我们关心的正是这个"形状",而非某台机器上的具体值。
三个坑填完,"时间复杂度"这个概念也就成形了。
这套"逐行算账"的方法,我们全课只认真做这一次——目的是让你彻底看清 T(n) 是怎么被"数"出来的。方法:给每行代码配两列——Cost(执行一次的开销)和 Rounds(整个过程里跑几次)。两者相乘再全部相加,就是总开销。
LinearSearch(A[1..n], k) i ← n–– while i ≥ 1 do–– if A[i] == k then–– return i–– i ← i − 1–– return −1––为什么 Cost 用 c1、c2… 而不是具体数字? 讲义里第一行本来写的是"3 微秒"。可 3µs 是瞎编的——我们根本不知道一次赋值真正要多久(还记得坑三吗?它取决于机器)。既然拿不到普适的准确值,不如直接抽象成一个未知常数 c1:我们只知道它是常数,不知道也不关心它具体几何。
无限次尝试,只为检验理解。