CSCI3160 T01 渐近增长与复杂度

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T01 渐近增长与复杂度 · 原件 T01-函数增长-未核.pdf（本地课件） p.1–20 定位：补足主课中运行时间函数和渐近记号的区别。

p.1–3：最坏情况与大 O 是两个问题【新】

p.1 标题；p.2 指出最坏运行时间先是一个关于规模n的函数，大O只是比较函数增长的记号。p.3 例如10+10log₂n，可以用渐近阶忽略常数和低阶项，但“大O”本身既不指最坏，也不指平均。

p.2 “the definition has nothing to do with ‘big-O’.”

p.4–6：常数为何被抽象

p.4 首先比较 5n 与 10n 次原子操作，并指出比较 a<b、乘法 a·b、访问内存的实际耗时可能不同，所以单看次数不能判定哪一个实际更快。相同原子操作数不意味着相同实际耗时，不同操作成本不同。p.5 比较n次乘法加4n次访存，与9n次乘法加n次访存：前者较快当且仅当3c_mem<8c_mult。p.6 无论机器上正成本常数如何变化，两者都是线性、只差常数因子。这是抽象层面的结论，不是承诺实际机器常数不重要。

p.7–9：增长率最终超过固定常数

p.7 关注大规模增长。p.8 n与10000log₂n比较，在n=2³⁰时，后者为300000，前者1073741824，比值约3579.14。p.9 把降低增长率作为算法设计主要目标。小n时较高常数可能使对数算法反而慢，渐近更优不等于所有输入规模都更快。

p.10–12：大 O 的两个常数

p.10 为转场。p.11 定义存在c>0、n0，使所有n≥n0满足f(n)≤cg(n)。c与n0可以依函数而定，但不能随n改变。p.12 有10000log₂n=O(n)，反向不成立，因为n/log n无界。

补充：把定义里的量词读成可检验承诺。 证明 $3n+7=O(n)$ ，可以先固定 c=10、n₀=1；随后每个 n≥1 都满足 $3n+7\le10n$ 。不是对每个 n 临时选一个 c。反过来，若要否定 $n^2=O(n)$ ，给定对方任意固定 c 和 n₀，只要取整数 n 同时大于二者，就有 $n^2>cn$ ，击破“所有足够大 n”的承诺。

自测：n=O(n²) 与 n²=O(n) 为什么不矛盾地一真一假？

O 表示单方向上界，不是等号。前者只说 n 不比 n² 长得更快，后者却要求用固定常数倍 n 压住 n²。习惯写成等号是记号惯例，不能按普通代数对称地交换左右。若要两个方向都成立，应证明 Θ。

p.13–14：对数底数与松上界

p.13 换底公式log_a n=log_b n/log_b a，a、b是固定大于1常数时只差常数，因此O(log n)可省底。p.14 将运行时间写成渐近形式；要注意O不是自动“最快增长项的精确界”：n也是O(n²)，若要表达紧确阶，用Θ。

p.15–17：下界和紧界

p.15 f=Ω(g)等价g=O(f)。p.16 展开为充分大n时f(n)≥cg(n)，p.17 同时上下界才是Θ。数字例（原件p.20）：n²+2n+1在n≥1时介于n²与4n²，分别取下界常数1、上界常数4，即Θ(n²)。

p.18：八个上界逐一判断

p.18 “Verify all the following”

10000000=O(1)，取c=10000000；100√n+10n≤110n（n≥1）；1000n^1.5≤1000n²。其余比较使用两条原则：任何固定次幂的log n小于任意固定正幂n；任何固定正幂n小于底数>1的指数。因此(log₂n)³=O(√n)，(log₂n)^9999999999=O(n^0.0000000001)，反向不成立；n^9999999999=O(2ⁿ)，反向不成立。巨大常数指数只使交叉点遥远，不改变最终增长次序。

补充推导：令t=ln n，则 $(\ln n)^a/n^b=t^a/e^{bt}\to0$ （固定a、b>0）；再取对数比较n^a与2ⁿ，a ln n−n ln2趋于负无穷。

p.19–20：下界与紧界练习

p.19 log₂n=Ω(1)取n≥2；0.001n=Ω(√n)可取c=0.001、n≥1；2n²=Ω(n^1.5)取c=2；余两题分别由“正幂胜过对数幂”“指数胜过多项式”得到下界，除以1000000只改常数。

p.19 的五条完整待证式为

\log_2n=\Omega(1),\quad0.001n=\Omega(\sqrt n),\quad2n^2=\Omega(n^{1.5}),

n^{0.0000000001}=\Omega((\log_2n)^{9999999999}),\qquad \frac{2^n}{1000000}=\Omega(n^{9999999999}).

最后两条直接把 p.18 已成立的上界关系左右交换，并按定义改成 Ω；乘以任意固定正数不改变这种关系。

p.20 的10000+30log₂n+1.5√n为Θ(√n)，因为正的√n项提供下界，另外两项渐近不超过它。把指数改成0.5000001后，除以√n出现n^0.0000001趋无穷，故不是Θ(√n)，而是Θ(n^0.5000001)。最后n²+2n+1已在前面用常数严格证明。

历年增长排序见附录 A1。本辅导的渐近记号细节不新建讲义记忆条目。

本讲核心考点

（A 级：Midterm-2021T1 Q4；Review-Quiz-2020T2 Q1）增长函数排序。
（C 级通识）用常数与阈值解释 O、Ω、Θ。
（C 级通识）大 O 不等于最坏情况，渐近优越不等于所有n更快。

附录

A1 作业/往年题演练（非讲义内容）：历年函数排序

题面（Midterm-2021T1-题目.pdf · Q4 · p.2；公式已对照题解扫描页核对并重排）

p.2 “4. [3 points] Order the following functions in increasing order according to their asymptotic growth rates:”

(a) $n\log^2 n$ , (b) $1.2^n$ , (c) $n^2+n\log^3 n$ , and (d) $\sqrt{2^n}$ .

先比较多项式部分。a 除以 n² 得到 log²n/n，趋于 0；c 除以 n² 得到 1+log³n/n，趋于 1，所以 a 比 c 慢。b 是固定底数大于 1 的指数，快于 c。d 的根号覆盖整个 2ⁿ，因此等于 $(\sqrt2)^n$ ，其底数约 1.414 大于 1.2；b/d 的比值为 $(1.2/\sqrt2)^n$ ，趋于 0。因此排序为 a<c<b<d。原件不是“2 的根号 n 次方”；文本抽取把根号和上标分行，必须看原图。

题面（Review-Quiz-2020T2-题目.pdf · Q1 · p.1；公式按原题重排）

p.1 “1. Order the following functions in increasing order according to their asymptotic growth rates (no need to explain reasons):”

(a) $1.1^n$ , (b) $n^2+88n\log^3n$ , (c) $\sqrt{2^n}$ , and (d) $n^2\log n$ .

b 的主项为 n²，而 d 多一个趋于无穷的 log n，故 b<d。a 是指数，渐近快于 d；c 的底数仍为根号 2，大于 a 的底数 1.1，所以 a<c。最终 b<d<a<c，与已读题解一致。

补充对应：Final-2021T1-题解.pdf Part I Q1(b)（PDF p.1 右栏，扫描件，视觉读取）原句为 “ $n\log n=O(n^{1.01})$ .”；除以右侧得到 log n/n^0.01→0，因此成立。这个例子强调任何固定正幂最终超过对数，哪怕指数只有 0.01。

回到正文：练习

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：T01-函数增长-未核.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。