（d）算法分析

官官方信息技术老师·10 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ （d）算法分析信息技术（d）算法分析 : 级数

时间复杂度渐近分析下界证明大O记号

（d）算法分析

掌握大O与大Ω两端的分析工具，能为算法画出上下界，也能解释为何排序不可能更快。

按空格/→ 演示下一步

1 / 10 页

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

时间复杂度渐近分析下界证明大O记号

（d）算法分析

掌握大O与大Ω两端的分析工具，能为算法画出上下界，也能解释为何排序不可能更快。

1第 1 页 · （d）算法分析

: 算法分析

前面我们认识了算法的定义与表示，但要真正选对算法，还需要量化它的'开销'。算法分析就是这套量化工具——回答的不是'这次跑了多久'，而是'规模变大时会怎样'。

时间复杂度

执行步数随 n 增长的阶，如 O(n)、O(n log n)

空间复杂度

额外内存随 n 增长的阶，不含输入本身占的空间

渐近记号 O/Θ/Ω

分别表示上界、紧界、下界；常见误区是混用

最好/平均/最坏情况

同一算法差距可能巨大（快排平均 O(nlogn)，最坏 O(n²)）

分摊分析

单次贵但罕见的操作分摊到多次（动态数组 push 均摊 O(1)）

桥梁载荷测试对应 →算法分析

不是测一辆车过桥多久，而是看车流变密时桥的反应；最坏情况对应地震/超载

T(n) = O(f(n)) \iff \exists c>0, n_0, \forall n \geq n_0: T(n) \leq c \cdot f(n)

2第 2 页 · : 算法分析

: 级数

上一节用大 O 衡量代码增长，但很多循环要先把 1+2+…+n 算出来才能下结论。这套求和工具，就叫级数。

级数定义

把数列各项依次相加，符号 Σ 表示

等差级数

1+2+…+n = n(n+1)/2，线性循环最常见

等比级数

1+2+4+…+2^k = 2^(k+1)-1，分支递归常见

平方和

1²+…+n² = n(n+1)(2n+1)/6，嵌套循环常见

作用

把 Σ 求和化简为闭式，从而得到复杂度

楼梯侧面对应 →等差级数求和

阶梯轮廓是梯形，面积=(1+n)×n/2，正好是等差求和

\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \Theta(n^2)

3第 3 页 · : 级数

: 循环

上节我们用级数描述算法总工作量，本节回到源头：这些级数从哪来？答案是循环。代码里绝大部分工作量都来自循环，所以分析复杂度，本质就是数迭代了多少次、每次做了什么。

循环三要素

由初始化、终止判断、迭代步三部分组成，三要素缺一不可

复杂度拆解

总工作量 = 迭代次数 × 单次成本，次数看循环控制、成本看循环体

循环不变量

每轮迭代前后都成立的关键性质，是用归纳法证明正确性的核心工具

典型模式

累加求和、线性查找、滑动窗口、二分查找等都是循环的经典应用

边界陷阱

空循环不算工作、off-by-one 差一错一、无穷循环是分析失败的红线

工厂流水线对应 →循环结构

传送带每转一圈加工一批，迭代变量记圈数，达标即停线——最直观的循环形象

T_{\text{总}} = \sum_{i=1}^{n} T_{\text{体}}(i)

4第 4 页 · : 循环

: 实例：非极端元素+起泡

上页用等差级数收尾循环求和。这页把同一把刀落在真实算法上——起泡排序每趟都有一位「极端」选手一路冒到顶，其余「非极端」选手中途就被拦下。

起泡排序结构

外层 n-1 趟，内层从前往后两两比较，前者大就交换

极端元素

每趟中最大的元素一路冒泡到本趟末尾，参与全部 n-i 次比较

非极端元素

其余元素只要发现右边比自己大，就原地停下，不必走完全程

总比较次数

各趟比较次数相加得等差级数，时间复杂度 O(n²)

运动会选拔赛对应 →起泡排序一趟

冠军（极端）必须跑完全程才排第一，其他选手（非极端）只要被前面超过就停下

\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}

5第 5 页 · : 实例：非极端元素+起泡

: 正确性的证明

起泡排序跑通了，但'跑通'≠'永远正确'。测试只是抽查，正确性证明才能对所有输入给出保证。

终止性

算法必须在有限步内结束，不能死循环

部分正确性

若算法终止，则输出满足规格

循环不变量

每次迭代前后均保持成立的性质

数学归纳

由第k步成立推出第k+1步成立

工程验收对照图纸对应 →测试与正确性证明

测试抽查几户，证明对照规格逐条核验所有情形

\{P\}\ S\ \{Q\}

6第 6 页 · : 正确性的证明

: 封底估算-1

证完正确性，紧接着会问'它跑得动吗'。与其列精确方程，不如先在封底粗算数量级——这就是封底估算。

本质

用数量级估算替代精确分析，快速判断算法的可行性

估算对象

操作次数、内存占用、数据规模三者的制约关系

关键技巧

向上取整、合并同类项、只保留最大增长项

使用边界

因子2~10内有效，不适合精确比较两种相近方案

搬家前估算要几趟车对应 →封底估算

不细到立方米，但能判断'一辆金杯够不够'；够就不用细算，不够再上方程

7第 7 页 · : 封底估算-1

: 封底估算-2

上一页讲了封底估算的核心思路——不求精确，只抓量级。这一页把它落到具体数字上：记住几个基准量、做几次单位换算，就能秒判一段代码是秒级还是天级。

硬件基准数字

CPU 约 10⁹ 操作/秒；1GB≈10⁹ 字节；硬盘读约 10⁸ 字节/秒

单位先对齐

时间统一到秒、空间统一到字节，N 代入时量级要对齐

抓主项原则

N 大时高阶项主导，常数和低阶项忽略：O(N²) 中 10⁸≫10⁴

反推问题规模

已知时间预算 T，反推能处理的最大 N：N_max≈(T·10⁹)^(1/k)

三大典型场景

估运行时间、估内存峰值、估网络传输量

开车估算到达时间对应 →封底估算运行时间

距离÷平均速度≈时间；总操作数÷CPU 速度≈运行时间

T \approx \frac{N^k}{R},\quad N_{\max} \approx \left(\frac{R \cdot T}{c}\right)^{1/k}

8第 8 页 · : 封底估算-2

本节要点

✓分析剥离实现层，揪住操作计数与增长趋势
✓正确性靠不变量，效率靠量级，二者不可互替
✓封底估算把抽象阶数落到具体数字与时间

延伸主题：摊还分析空间复杂度平均情形与概率分析

9第 9 页 · 本节要点

课后思考

三道题没有标准答案。建议先遮住参考答案自己琢磨，再对比思路差异。

1为什么起泡排序两层循环做下来是 n(n-1)/2 次而不是 n²？'量级'和'精确计数'之间到底差了什么？

参考答案量级只看最高阶项的增长趋势；精确计数则保留每一项与常数。封底估算刻意丢掉细节，是用精度换速度。

2如果一段双层 for 循环的内层步长不固定（比如每轮步长翻倍），如何用封底估算快速判断整体复杂度上界？

参考答案把内层执行次数写成外层变量的函数，看它对求和贡献了哪种级数（等差、等比或其他），然后只保留量级最大的那一项。

3封底估算把常数扔掉。但嵌入式或高频场景下，2n 和 100n 的常数差可能比 n vs n² 更要命。什么场景下这种估算会误判？

参考答案当多个算法复杂度同阶但常数差距大，或'有效 n'很小时，常数会反过来主导性能，必须结合实测规模判断，不能只看书。

10第 10 页 · 课后思考