（c）大O记号

官官方信息技术老师·10 页·深入（追求细节与边界）·0 次浏览·3 天前
✦ （c）大O记号信息技术（c）大O记号: 难解
算法分析渐近记号复杂度严格证明

（c）大O记号

看清大O的形式化定义，区分五种渐近记号的边界，识破直觉中的常见陷阱

按 空格/→ 演示下一步

1 / 10 页

全部页面点击任意一页，跳回舞台从这页播放

算法分析渐近记号复杂度严格证明

（c）大O记号

看清大O的形式化定义，区分五种渐近记号的边界，识破直觉中的常见陷阱

1第 1 页 · （c）大O记号

: 主流长远

两份代码跑了1000次都是几毫秒，看起来差不多。但当数据量从1000涨到100万、1亿，谁先扛不住？大O记号回答的就是这个长远问题。

看 n→∞ 的增长
n 很大时高阶项压过低阶项，常数因子也微不足道
抓主导扔细节
n²+100n+999≈n²；系数 1/2 或 50 都消失
上界视角
O(f(n)) 说存在常数 c 使 T(n)≤c·f(n) 终将成立
边界：标增长不标耗时
O 不给实际秒数，只标增长率；n=10 时 O(n³) 可能比 O(n²) 还快
远眺城市天际线对应 →大O看主导项

摩天楼决定轮廓，小楼再多也看不清；n→∞ 时主导项决定增长形状

T(n)=O(f(n))  ⟺  ∃ c>0, n0>0, ∀n≥n0:  T(n)≤c⋅f(n)T(n)=O(f(n))\iff\exists\,c>0,\,n_0>0,\,\forall n\ge n_0:\;T(n)\le c\cdot f(n)
2第 2 页 · : 主流长远

: 大O记号

算法世界里，比起"小数据谁更快"，我们更关心"数据规模暴涨时，谁会失控"。大O记号就是用来回答这件事的语言工具。

上界记号
描述函数增长的最高上限，关注最坏情况下的趋势
忽略常数与系数
5n、100n、1000n 都记作 O(n)，常数不参与阶的判定
保留最高阶项
n²+100n+1000 化简为 O(n²)，低阶项被高阶项吸收
渐近视角
考察 n→∞ 时的增长趋势，对小输入的常数差异不敏感
仅是上界
O(n) 只承诺不超过线性增长；想说上下界一致，需用 Θ 记号
集装箱载重上限对应 →大O的上界

载重上限≠实际装载，Big O承诺的是增长上限，不代表真实阶

f(n)=O(g(n))  ⟺  ∃ c>0, n0>0: f(n)≤c⋅g(n), ∀n≥n0f(n) = O(g(n)) \iff \exists\, c>0,\ n_0>0:\ f(n) \leq c\cdot g(n),\ \forall n \geq n_0
3第 3 页 · : 大O记号

: 高效解

大O记号回答了'多快'的问题，但要追问：多快才算'够快'？高效解在算法理论中有明确边界。

多项式时间
存在常数k使复杂度为O(n^k)，是高效解的核心定义
可处理性
即tractable，多项式=可处理，指数=不可处理
典型高效阶
O(1)、O(log n)、O(n)、O(n log n)、O(n²)是实战常见
边界并非绝对
n^100虽多项式仍不实用；实战O(n²)已接近经验上限
地图导航对应 →高效解 vs 暴力枚举

Dijkstra按边松弛（多项式）；枚举所有路径是指数

O(nk), k∈NO(n^k),\ k \in \mathbb{N}
4第 4 页 · : 高效解

: 有效解

前面我们看到大O把'高效'区分出来，但'高效'随硬件变。今天给一个更稳的概念：能在多项式时间内求出的解，称为'有效解'——这是计算机理论里最常用来划线的标准。

形式定义
存在常数 k，使得算法的时间复杂度为 O(n^k)
闭包性质
多项式的加、乘、复合仍是多项式，便于组合分析
机器无关
图灵机、RAM 机之间的多项式时间只差一个多项式因子
实践边界
n=60 时 2^n 已超宇宙粒子数，多项式仍秒级完成
P 类集合
所有多项式时间可解问题的集合，即'易解'问题
盖高楼对应 →多项式时间复杂度

楼层多 1 层，工时多固定倍数，总能盖完；指数是每高 1 层要重盖所有楼

5第 5 页 · : 有效解

: 难解

高效解说的是多项式时间内能跑出来的问题。但现实中还有一类问题——目前找不到多项式算法，蛮力算到宇宙毁灭也算不完。这就是难解。

定义
目前不存在多项式时间算法的问题（默认P≠NP）
时间尺度
最优算法仍是指数级 2ⁿ 或阶乘级 n! 增长
典型例子
TSP精确解、Hamilton回路、SAT（n较大时）
条件性
「难」建立在P≠NP假设上，目前没人严格证明
退路
只能靠近似算法、启发式、概率算法求次优解
穷举所有路线找最短对应 →暴力解难解问题

n=50就有10⁶⁴种走法，远超宇宙原子总数，根本算不完

n!≈3×1064vs.250≈1015n!\approx 3\times10^{64}\quad\text{vs.}\quad 2^{50}\approx 10^{15}
6第 6 页 · : 难解

: 2−Subset

前一页说「难解」只是一个标签。这一页把标签贴到具体问题上：2−SUBSET——给你一组整数，问能不能挑出几个加起来正好等于 2。

问题定义
输入一组整数，问是否存在子集的元素之和恰好等于 2
证书可验
给一个候选子集，逐元素相加只需多项式时间
属于 NP
因证书短且可多项式验证，故属于有效可解类
NP−难
3−SAT 等经典难问题可在多项式时间内化归到它
化归工具
许多看似无关的问题借此被证明为 NP 完全
零钱凑整 2 元对应 →2−SUBSET

硬币堆就是输入，挑哪些硬币就是子集，凑齐 2 元就是目标

2-SUBSET={ ⟨S⟩∣S 是整数集，∃T⊆S:∑x∈Tx=2 }2\text{-SUBSET}=\{\,\langle S\rangle\mid S\text{ 是整数集，}\exists T\subseteq S:\sum_{x\in T}x=2\,\}
7第 7 页 · : 2−Subset

: 增长速度

上页说「难解」问题撑不住大输入——但这只是直觉。要把它说清楚，得回到一个更基础的概念：增长速度。

描述对象
f(n) 表示输入规模 n 下的资源消耗（时间、空间等）
极限视角
只关心 n→∞ 时 f(n) 的变化形态，不看某个 n 的具体值
抓主导项
增长最快的项决定增长量级，常数与低阶项可忽略
与 O 等价
大O记号就是给增长速度一个严格、简洁的数学写法
城市人口增长对应 →增长速度

绝对人口不重要，关键是每年新增多少、未来如何翻倍——这才是发展潜力的核心指标

lim⁡n→∞f(n)nk∈(0,∞)⇒增长速度为 nk\lim_{n\to\infty}\frac{f(n)}{n^k} \in (0,\infty) \Rightarrow \text{增长速度为 } n^k
8第 8 页 · : 增长速度

本节要点

  • ✓大O刻画增长率上界，刻意忽略常数与低阶项
  • ✓多项式时间=高效类，指数增长=难解类，分水岭清晰
  • ✓O/Ω/Θ三件套：上界/下界/紧界，混用会失之毫厘
  • ✓2-Subset等NP问题无已知多项式解，但未证不存在
  • ✓选型时先看增长曲线，再考虑常数与硬件实现
延伸主题：P、NP、PSPACE 复杂度谱平摊分析：摊还到均摊下界证明：决策树与对手论证
9第 9 页 · 本节要点

课后思考

每题先自己在脑中转一转，再对照参考答案；三问覆盖回顾、应用、延伸三层。

1大O记号忽略了什么？为什么这种忽略是合理的？

参考答案忽略常数因子和低阶项。理由：n足够大时，增长最快的那一项决定一切，其它影响被淹没——这反映了大O关心'可扩展性'的本质。

2若A是O(n log n)、B是O(n)，输入规模扩到10倍，两者的实际差距如何变化？

参考答案差距被'放大'。n增10倍时，B近似增10倍，A却要增约33倍（10·log10）。规模一大，原来的'常数倍'会被撕开成'量级差'。

3大O只刻画上界——想表达'下界'或'恰好'的增长，应该用什么记号？

参考答案用Ω记下界，用Θ记'恰好'的上下界一致。大O单独存在时容易'骗人'：O(n)算法未必最优，可能存在Ω(n²)的下界却无人企及——这也是难解问题的入口。

10第 10 页 · 课后思考
（c）大O记号 · 知识图解