上一课我们造好了尺子——Big-O 的定义。可是拿到一个具体命题,比如 3n+5 = O(n−3),那对常数 (c, n₀) 到底怎么找?这一课是纯实战:三个例题,每个都藏着一个新机关;最后再把方向掉个头——第一次证明"不是 O"。
先把尺子请回来。这节课从头到尾只用这一件武器——定义本身,没有任何新定理。
热身一下,把上一课的老朋友 LinearSearch 办了:它的 T(n) = 10n + 7(常数还是瞎编的那两个),证 T(n) = O(n):
十秒钟搞定。可惜考试和作业里的题不会都这么客气。这节课的三个例子难度逐级上升,每个都专门训练一种"找证书"的手法;最后一节反过来:如果命题是假的,你要怎么把它锤死?
| 战役 | 命题 | 机关 · The twist | |
|---|---|---|---|
| 例一 | 3n+5 = O(n−3) | g 在每个点都更小,居然还能当上界?c 与 n₀ 必须联动求解 | §02 ↓ |
| 例二 | 2n+1 = O(2n) | 指数上加 1,到底是"大一点"还是"大一档"? | §05 ↓ |
| 例三 | (n+10)³ = O(n³) | 放缩 (bounding) 的艺术:把小零件放大成主项 | §06 ↓ |
| 反证 | 0.01n² ≠ O(n) | 量词翻转:这次要打赢所有证书 | §08 ↓ |
整节课的地图。四场战役共用一把武器:定义。打完你会发现,"会用定义"比"背下定义"值钱得多。
f(n) = 3n+5,g(n) = n−3。第一眼看上去这题就不对劲:g 不但更小,小 n 时还是负的。
随便代几个数:n=10 时 f=35、g=7;n=100 时 f=305、g=97。f 在每一个 n 上都比 g 大四倍有余,凭什么说 g 是 f 的"上界"?更过分的是 g(1)=−2、g(2)=−1、g(3)=0——在 n ≤ 3 这段,g 连正数都不是(定义里 ℝ⁺ 的要求都没满足,这正是 n₀ 要出场清理的烂摊子,和上一课 n²−100 的"负数区"一模一样)。
蓝线 f(n)=3n+5,紫虚线 c·(n−3)。切换 c,看紫线从"永远垫底"到"越过蓝线"的瞬间:
好,直觉上能成。但证明需要白纸黑字。目标不等式是 3n+5 ≤ c(n−3)——把它当成普通的不等式来解,看看 c 和 n 各要满足什么:
c > 3 只是"有资格竞争";具体挑哪个 c、配哪个 n₀,下一节揭晓。
既然 c > 3 都行,那就挑个顺手的。讲义选了 c = 4——代回去,n 的门槛自己浮出来。
到这一步,草稿完成:证书是 (c, n₀) = (4, 17)。但草稿是"反着解"出来的,正式证明要"正着写"——从 f(n) 出发,一路 ≤ 下去,落到 c·g(n)。讲义的链条只有一行,却有一步神来之笔。一步步长出来:
讲义还顺手给了第二张证书:挑 c = 5,门槛变成 5 + 15 ≤ 2n,即 n ≥ 10——证书 (5, 10) 同样有效:
c 抠门一点,就得多等几步——n₀ 被迫推到 17。验证链:3n+5 ≤ 3n+5+(n−17) = 4(n−3)。
c 大方一点,门槛立刻提前:3n+5 ≤ 3n+5+2(n−10) = 5n−15 = 5(n−3),对 n ≥ 10 成立。
两张证书摆在一起,规律已经露头:c 越大,n₀ 可以越小。这不是巧合,是一条能精确算出来的曲线。
刚才解出的门槛是 n ≥ (5+3c)/(c−3)。也就是说,每个 c > 3 都自带一个"最小可行 n₀"。拖动滑杆,找出整条跷跷板:
蓝线 f(n)=3n+5,紫虚线 c·(n−3),阴影区是 n ≥ n₀。目标:让紫线在阴影区里全程压住蓝线。
| c | 门槛 (5+3c)/(c−3) | 最小可行 n₀ |
|---|---|---|
| 3 | —(除以 0) | 无解 ✗ |
| 4 | 17 / 1 = 17 | 17 |
| 5 | 20 / 2 = 10 | 10 |
| 6 | 23 / 3 ≈ 7.7 | 8 |
| 10 | 35 / 7 = 5 | 5 |
| 17 | 56 / 14 = 4 | 4 |
| 1000 | 3005 / 997 ≈ 3.01 | 4(还是 4!) |
f(n) = 2n+1,g(n) = 2n。上一课的陷阱言犹在耳:"指数的底数不能丢,O(2ⁿ) ≠ O(3ⁿ)"。那指数上加个 1 呢?是"大一点"还是"大一档"?
一行代数就见分晓。指数法则:2n+1 = 2 · 2n——指数上的 +1,拆下来只是乘 2。目标不等式立刻变得毫无悬念:
不等式里的 n 直接消失了——对 n 没有任何要求,所以 n₀ 随便选,取最小的 n₀ = 1 即可。这是三个例子里唯一一个"n₀ 完全不用干活"的。
真正值钱的是把这个例子推而广之:指数上动手脚,什么动作是无害的、什么动作是致命的?点下面每个函数,看它能不能塞进 O(2ⁿ):
f(n) = (n+10)³,g(n) = n³。目标:(n+10)³ ≤ c·n³。这次不解不等式了——展开三次方太脏。讲义用了一记更漂亮的手法。
证书到手:(c, n₀) = (1331, 1)。c 大得吓人?无所谓——定义只要"存在常数",1331 和 2 一样都是常数。这就是"放缩" bounding 的精神:不求紧,只求快、只求对。
当然,讲义也演示了跷跷板的另一头:先把 n₀ 抬到 10,小零件就能放缩得更凶——此时 10 ≤ n,于是 n + 10 ≤ n + n = 2n,立方得 (n+10)³ ≤ 8n³:
用 10 ≤ 10n(对所有 n ≥ 1 成立)。门槛最低,常数最丑。
用 10 ≤ n(要求 n ≥ 10)。多等九步,常数从 1331 掉到 8——跷跷板再次现身。
三场胜仗打完,讲义停下来把"语感"钉死。f(n) = O(g(n)) 这行符号,你应该在脑子里自动翻译成三句话:
既然 O 是"≤",一个自然的问题立刻冒出来:如果 f 的增长率真的比 g 高,会发生什么?讲义的原话(标红的那句):
这句话给了我们全新的武器:证明"不是 O"。方向一掉头,量词全体翻转——下一节,课程里第一次反证。
f(n) = 0.01n²,g(n) = n。系数 0.01 小得可怜——但你已经被这节课训练过了:系数救不了增长率。二次就是二次。
先想清楚"要证的到底是什么"。证 O 时,定义是"存在 c、存在 n₀":你交一张证书就赢。反证 O 是把整句话否定——"存在"翻转成"任意":
角色对调了:证 O 时你挑常数、全世界的 n 来检验;反证 O 时别人随便给常数,你负责造出一个翻车的 n。所以反证的核心是一台"反例生成器":输入任意 c,输出一个必然翻车的 n。对本题,生成器一行就写出来了:
就这么直白:只要 n 超过 100c,不等式必翻。讲义的验证(注意每一步都是严格的):
把两个方向做成一个游戏,亲手感受"真命题打得赢、假命题必输"。你扮演证明者:挑一对 (c, n₀) 递交;机器扮演对手 (adversary):专职在 n ≥ n₀ 里找翻车点。
上一课的配方只有"挑 c → 挑 n₀ → 验证"三步。打完这四仗,配方升级,反证也有了自己的流水线。
把 f ≤ c·g 整理成 "(…)·n ≥ 常数" 的形状,看 c 多大才能让 n 的系数为正。(例一:c > 3,底线来自两边斜率之比)
代入顺手的 c,n 的门槛自动浮现。(c=4 → n₀=17;c=5 → n₀=10——跷跷板上任选一点)
用 n ≥ 1 或 n ≥ n₀ 把小零件放大成主项:10 ≤ 10n、100n ≤ n²(n≥100)……不求紧,只求对。(例三:c=1331 丑吗?丑。有效吗?有效。)
草稿是反着解的,证明要正着写:f(n) ≤ … ≤ c·g(n),每个 ≤ 标明理由,最后 ∎。("凭空加 (n−17)"这类妙步全都来自草稿。)
假想别人递来任意的 c 和 n₀——你一个都不能放过。
解 f(n) > c·g(n),把反例区写成 c 的函数。(0.01n² > cn ⟺ n > 100c)
取 n* = max(n₀, …)+1 之类,写清严格不等式,∎。(n 无上界,所以"够大的 n"永远取得到。)
Big-O 从不比逐点大小——c 可以把 g 整体撑大。同档直线之间互为 O,哪怕一条永远压着另一条。
换了 c,门槛就变:(4,17) 有效、(5,10) 有效,但 (4,10) 无效——n=10 时 35 > 28。证书必须整对验证。
证 O 要求"从 n₀ 起全体 n";反证 O 要求"打赢全体 (c, n₀)"——反例必须是 c 的公式(n > 100c),孤零零一个数字谁也打不死。
2ⁿ⁺¹ = 2·2ⁿ 同档;2²ⁿ = 4ⁿ 换了底数,比值 2ⁿ → ∞,跨档。指数上"+k"是乘 2ᵏ,"×k"是换底 (2ᵏ)ⁿ。
四道加练,难度递增,全部只用本课武器(定义 + 反解 + 放缩 + 反例生成器)。先在纸上写出自己的 (c, n₀) 或反例公式,再点开题解对答案——直接看解等于没做。
提示:g 有负数区(n ≤ 50),先想 n₀ 至少要多大;再用"n ≥ 某数时 100n ≤ n²、50n ≤ n²/2"两次放缩。
提示:先把比值 4ⁿ/2ⁿ 化简,再造反例生成器 n(c)。
提示:(n+10)³ = n³ + 30n² + 300n + 1000,然后对每个低次项各放缩一次(n ≥ 1)。系数们加起来是多少?
提示:反解不等式解不动(n³ ≤ c·2ⁿ 没有初等解),放缩也不好直接放。试试数学归纳法:先找一个 n₀ 使 n₀³ ≤ 2^{n₀},再证"每往前走一步,右边翻倍,而左边翻不到倍"。关键比值:(n+1)³/n³ = (1 + 1/n)³。
无限次尝试,零压力。七道题,专打这节课的要害。