专题进阶 · 基础与数据结构推荐总顺序 · 第 24 / 148 课

用上界、下界和紧界描述增长,并说明输入条件与成本模型。

先学会这些,再进入本课 时间复杂度
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 基础与数据结构

Big OAsymptotic Notation

O 给出渐近上界,Θ 表示同阶紧界;忽略常数不等于实际性能中常数不重要。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用上界、下界和紧界描述增长,并说明输入条件与成本模型。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

程序做 3n+2 次操作,为什么写 O(n)?又为什么 O(n²) 也没错,却通常不是好答案?

02一步步得到方法

把符号读成一句完整的话

f(n)=O(g(n)) 表示存在常数 c>0 和阈值 n₀,使所有 n≥n₀ 都满足 f(n)≤c·g(n)。它表达最终的上界,既不表示精确次数,也不自动表示最坏情况。

对 f(n)=3n+2,n≥1 时有 3n+2≤5n,因此可取 c=5、n₀=1。与此同时 f(n)≥3n,所以也有 Ω(n),上下同阶合起来就是 Θ(n)。

为什么先写输入条件

线性搜索的最好情况是第一个位置命中,最坏情况是不存在目标。二者分别是 Θ(1) 与 Θ(n),但算法名称没有改变。平均情况必须说明目标和输入如何分布。

两个独立循环分别扫描 n 和 m 个元素,成本为 Θ(n+m),不能无理由只留 n。两层循环若内层每次执行 m 次,则是 Θ(nm)。当 m 固定为 10,才可简化为 Θ(n)。

渐近结论如何用于选择

1000n 与 n² 在小规模下可能由后者更快,渐近分析只说明增长趋势。实际比较还要看常数、内存访问、输入分布和实现;先排除明显不可承受的增长,再对真实工作负载测量。

03把一个小例子完全算清楚

比较 n=1、10、100 时 f(n)=3n+2,与线性上界 5n。

步骤计算与状态为什么这样做
n=1f=5,5n=5上界恰好相等
n=10f=32,5n=50仍落在线性上界以内
n=100f=302,5n=500比例趋近 3,不会无限增大

窄屏可左右滑动表格,阅读完整计算与理由。

这里给出了一个适用于所有 n≥1 的不等式证明;几个样本只能辅助理解,不能代替证明。

04为什么这个方法成立

  1. 对 n≥1,常数 2≤2n,因此 3n+2≤5n。
  2. 对 n≥1,3n+2≥3n,因此存在同阶下界。
  3. 上下界同时成立得到 Θ(n);也属于 O(n²),只是上界不够紧。

05把推导翻译成代码

Python · 可独立运行的教学实现

def operation_count(n):
    assert n >= 0
    return 3 * n + 2

def pair_count(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            count += 1
    return count

逐个理解关键决定

range(i + 1, n)
内层次数依次为 n−1、n−2、…、0;不能把每轮都当作 n 次来求精确总数。
count += 1
这里数的是配对次数,不是墙钟时间。总计 n(n−1)/2,n≥2 时为 Θ(n²)。

06时间、空间与实现范围

求一个闭式表达式在固定宽度算术模型中是 O(1);被表达式描述的另一个程序仍可能耗时 O(n)。

pair_count 枚举所有无序位置对,时间 Θ(n²),计数器额外空间 O(1)。

07改变条件,检查哪里会出错

看到 O 就说最坏情况

先定义被分析的函数,例如 T_worst(n),再给它的渐近上界。

两个嵌套循环必为 O(n²)

若内层每次折半或总指针只前进 n 次,必须按实际执行次数求和。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

5n²+7n+3 的紧界是什么?

需要一点提示

找增长最快的一项,并给上下界。

查看解析与答案

Θ(n²)。n≥1 时 n²≤5n²+7n+3≤15n²。

练习 2 · 边界与辨析

一个循环将 i 从 1 每次乘 2,直到 i≥n,执行几次?

需要一点提示

写出 1、2、4、8。

查看解析与答案

约 ceil(log₂n) 次,因此 Θ(log n),不是 Θ(n)。

练习 3 · 变式与迁移

输入有 n 个字符串,每个长 m,逐个完整比较需要什么成本?

需要一点提示

一次字符串比较并不总是常数。

查看解析与答案

最坏要检查 nm 个字符,时间 O(nm)。若找到失配可提前停,最好情况不同。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Python 官方教程 · 数据结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。