第3章 函数的增长

导读

在算法分析中，我们需要一种精确而简洁的方式来描述算法的运行时间如何随输入规模的增长而变化。这就是渐进记号（Asymptotic Notation）的作用。本章将系统地介绍各种渐进记号——O、Ω、Θ、o、ω——以及它们之间的关系和运算规则。我们还将学习如何分析常见函数的增长率，掌握比较函数增长速度的方法。

函数的增长分析是算法效率评估的数学基础。理解不同函数的增长特性，能够帮助我们在设计算法时做出更明智的选择，也能更准确地预测算法在大规模输入下的表现。

核心概念详解

3.1 渐进记号概述

渐进记号用于描述函数在输入趋向无穷大时的渐近行为。在算法分析中，这些函数通常表示算法的运行时间或空间需求。使用渐进记号的优势在于：

• 忽略常数因子，关注增长率
• 忽略低阶项，简化表达
• 与具体机器和编程语言无关
• 便于算法之间的比较

3.2 Θ记号（紧确界）

Θ记号提供了函数的渐近紧确界（tight bound）。形式化定义：

Θ(g(n)) = {f(n) : 存在正常数c₁、c₂和n₀，使得对所有n ≥ n₀，有0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)}

直觉上，Θ(g(n))表示函数f(n)与g(n)同阶——在n足够大时，f(n)被夹在c₁g(n)和c₂g(n)之间。

示例：

• 6n³ + 3n² + 1 = Θ(n³)
• 证明：取c₁ = 6, c₂ = 10, n₀ = 1，则对所有n ≥ 1，6n³ ≤ 6n³ + 3n² + 1 ≤ 10n³

重要性质：

• f(n) = Θ(g(n))当且仅当f(n) = O(g(n))且f(n) = Ω(g(n))
• Θ记号描述的是同一个数量级的增长

3.3 O记号（渐近上界）

O记号提供了函数的渐近上界（upper bound）。形式化定义：

O(g(n)) = {f(n) : 存在正常数c和n₀，使得对所有n ≥ n₀，有0 ≤ f(n) ≤ cg(n)}

O记号在算法分析中最为常用，通常用于描述算法的最坏情况运行时间。

示例：

• n² + n = O(n²)：取c = 2, n₀ = 1
• 3n = O(n²)：取c = 3, n₀ = 1（注意：O(n²)是上界，不是紧确界）
• n = O(n)：取c = 1, n₀ = 1

常见误用：

• "f(n) = O(g(n))"中的等号是不对称的。O(g(n))表示一个集合，f(n) ∈ O(g(n))才是严格写法
• O(n) = O(n²)是成立的（因为O(n) ⊂ O(n²)），但O(n²) = O(n)不成立

3.4 Ω记号（渐近下界）

Ω记号提供了函数的渐近下界（lower bound）。形式化定义：

Ω(g(n)) = {f(n) : 存在正常数c和n₀，使得对所有n ≥ n₀，有0 ≤ cg(n) ≤ f(n)}

Ω记号常用于描述问题的下界——解决某类问题至少需要多少时间。

示例：

• 基于比较的排序算法的最坏情况运行时间是Ω(n log n)
• n³ = Ω(n²)：取c = 1, n₀ = 1
• n = Ω(1)：取c = 1, n₀ = 1

3.5 o记号和ω记号（非紧确界）

o记号（非紧确上界）：

o(g(n)) = {f(n) : 对任意正常数c > 0，存在常数n₀ > 0，使得对所有n ≥ n₀，有0 ≤ f(n) < cg(n)}

等价地：lim(n→∞) f(n)/g(n) = 0

o记号表示f(n)的增长严格慢于g(n)。例如：n = o(n²)，但n ≠ o(n)。

ω记号（非紧确下界）：

ω(g(n)) = {f(n) : 对任意正常数c > 0，存在常数n₀ > 0，使得对所有n ≥ n₀，有0 ≤ cg(n) < f(n)}

等价地：lim(n→∞) f(n)/g(n) = ∞

ω记号表示f(n)的增长严格快于g(n)。例如：n² = ω(n)，但n² ≠ ω(n²)。

3.6 各记号之间的关系

五种渐进记号可以用类比来理解：

传递性：

• 若f = O(g)且g = O(h)，则f = O(h)
• 类似的传递性对Ω、Θ、o、ω都成立

反射性：

• f = O(f)（对所有O、Ω、Θ成立）

对称性：

• f = Θ(g)当且仅当g = Θ(f)

转置对称性：

• f = O(g)当且仅当g = Ω(f)
• f = o(g)当且仅当g = ω(f)

3.7 常见函数及其增长率

以下是算法分析中常见的函数，按增长率从低到高排列：

常数函数：O(1)

• 不随输入规模变化的操作
• 示例：数组访问、基本算术运算

对数函数：O(log n)

• 每次将问题规模减半的操作
• 示例：二分查找
• 注意：在算法分析中，log通常指以2为底的对数

多对数函数：O(log² n)

• 示例：某些平衡树操作

多项式对数：O(log^k n)

• 对数的多项式次幂

线性函数：O(n)

• 需要遍历所有元素的操作
• 示例：线性查找、数组求和

线性对数：O(n log n)

• 示例：归并排序、堆排序

平方函数：O(n²)

• 示例：冒泡排序、选择排序

立方函数：O(n³)

• 示例：矩阵乘法的朴素算法

多项式函数：O(n^k)

• k为常数的多项式

指数函数：O(2^n)

• 示例：穷举搜索、某些递归算法

阶乘函数：O(n!)

• 示例：旅行商问题的穷举解法

3.8 函数增长的比较

比较两个函数增长率的方法：

极限法：

计算lim(n→∞) f(n)/g(n)：

• 若极限为0，则f = o(g)
• 若极限为常数c > 0，则f = Θ(g)
• 若极限为∞，则f = ω(g)
• 若极限不存在（振荡），则无法用上述关系比较

洛必达法则：

当极限为0/0或∞/∞不定式时，可以对分子分母分别求导：

lim f(n)/g(n) = lim f'(n)/g'(n)

斯特林近似：

n! ≈ √(2πn) · (n/e)^n

这个近似在分析涉及阶乘的算法时非常有用。

3.9 函数运算规则

加法规则：

• 若f(n) = O(g(n))，则f(n) + h(n) = O(g(n) + h(n))
• 特别地，若f(n) = O(g(n))且g(n)支配h(n)，则f(n) + h(n) = O(g(n))

乘法规则：

• 若f(n) = O(g(n))且h(n) = O(k(n))，则f(n)·h(n) = O(g(n)·k(n))
• 特别地，c·f(n) = O(g(n))，其中c是常数

多项式规则：

• 若f(n)是k次多项式，则f(n) = Θ(n^k)
• 多项式的阶由其最高次项决定

对数规则：

• log^a(n) = o(n^b)，对任意a, b > 0
• 即任何正幂次的对数都增长得比任何正幂次的多项式慢

3.10 实用分析技巧

忽略低阶项：

n³ + n² + n = Θ(n³)，因为当n足够大时，n³项主导整个表达式。

忽略常数因子：

5n² = Θ(n²)，常数因子不影响渐进增长率。

关注最高层循环：

对于嵌套循环，最内层的执行次数通常决定了算法的总时间复杂度。

递归分析：

对于递归算法，建立递归式并使用适当方法求解。

摊销分析：

某些操作偶尔代价很高，但平均下来代价很低。摊销分析考虑一系列操作的平均代价。

重要知识点

知识点1：渐进记号的严格数学定义

理解渐进记号的关键在于量词的顺序。例如，O(g(n))的定义中：

• 先存在c和n₀（∃c, n₀）
• 然后对所有n ≥ n₀（∀n ≥ n₀）

这意味着c和n₀是固定的，不随n变化。混淆量词顺序是理解渐进记号时常见的错误。

知识点2：对数在算法分析中的重要性

对数函数在算法分析中极为常见，原因包括：

• 分治策略中，每次将问题规模减半，递归深度为log n
• 二叉树的深度为log n
• 二分查找每次排除一半的搜索空间

对数的底数在渐进分析中不重要，因为log_a(n) = log_b(n) / log_b(a)，换底只是乘以常数。

知识点3：多项式与指数的本质区别

多项式函数和指数函数的增长率有本质差异：

• n^100 = o(1.01^n)
• 任何多项式都增长得比任何指数慢

这个区别在算法分析中至关重要：

• 多项式时间的算法被认为是"高效的"
• 指数时间的算法通常只适用于小规模问题

知识点4：渐进记号的组合

在实际分析中，经常需要组合使用渐进记号：

• O(n) + O(n) = O(n)
• O(n) · O(n) = O(n²)
• O(O(n)) = O(n)

但需要注意：O(n) - O(n) 不一定等于 O(0)，因为两个O(n)函数可能不同。

知识点5：实际运行时间与渐进分析的关系

渐进分析描述的是大规模输入下的趋势，实际运行时间还受以下因素影响：

• 常数因子：O(n)的算法可能有比O(n log n)更大的常数
• 输入特征：某些算法对特定输入表现更好
• 硬件特性：缓存、流水线、并行性等
• 实现质量：代码优化程度

常见误区

误区1：O(n²)意味着精确的n²步操作

O(n²)只表示运行时间的上界是n²的常数倍。实际运行时间可能是3n²、n² + n或0.5n² + 100n。O记号忽略常数因子和低阶项，只关注增长率。

误区2：渐进最优的算法一定最快

渐进最优的算法在小规模输入下不一定最快。例如：

• 理论上的最优排序算法可能有很大的常数因子
• 实际中，快速排序虽然是O(n²)最坏情况，但通常比O(n log n)最坏情况的堆排序更快

误区3：log n的增长可以忽略

虽然log n增长很慢，但在大规模数据下，n log n和n的差异是显著的。例如，当n = 10⁹时，log n ≈ 30，这意味着n log n比n大30倍。

误区4：O(2^n)和O(n!)没有区别

虽然两者都是指数级增长，但n!的增长远快于2^n。根据斯特林近似，n! ≈ (n/e)^n，远大于2^n。在算法分析中，区分这两者很重要。

误区5：空间复杂度可以忽略

在某些场景下，空间复杂度比时间复杂度更重要：

• 嵌入式系统和移动设备内存有限
• 大数据处理中内存是瓶颈
• 空间过大会导致缓存失效，间接影响时间性能

实践应用

应用1：算法选择中的增长率分析

在实际工程中，根据输入规模选择合适的算法：

• n ≤ 10：O(n!)或O(2^n)的算法可以接受
• n ≤ 100：O(n³)的算法可以接受
• n ≤ 10000：O(n²)的算法可以接受
• n ≤ 10⁶：需要O(n log n)或更好的算法
• n > 10⁶：需要O(n)或O(log n)的算法

应用2：性能预测和优化

通过渐进分析预测算法在不同规模下的表现：

• 如果当前处理1000条数据需要1秒，处理100万条数据需要多久？
• O(n²)算法：10⁶倍时间 ≈ 11.5天
• O(n log n)算法：约1000倍时间 ≈ 16分钟
• O(n)算法：1000倍时间 ≈ 1000秒 ≈ 16分钟

应用3：系统设计中的复杂度考量

在大规模系统设计中，算法的渐进复杂度决定了系统的可扩展性：

• 数据库索引：O(log n)的B树查询 vs O(n)的线性扫描
• 缓存策略：O(1)的哈希表 vs O(log n)的平衡树
• 网络路由：O(n²)的路由算法在大规模网络中不可行

应用4：并行计算中的复杂度分析

并行计算改变了复杂度的计算方式：

• 如果算法可以完美并行化，p个处理器可以将时间除以p
• 但通信开销和同步开销也需要考虑
• Amdahl定律：串行部分限制了并行加速的上限

应用5：近似算法中的复杂度权衡

对于NP难问题，近似算法提供了时间和精度的权衡：

• 精确算法：指数时间，得到最优解
• 近似算法：多项式时间，得到近似解
• PTAS（多项式时间近似方案）：可以任意接近最优解，但时间随精度提高而增加

3.11 渐进记号的严格数学性质

传递性的证明：

定理：若f(n) = O(g(n))且g(n) = O(h(n))，则f(n) = O(h(n))。

证明：

• 由f(n) = O(g(n))：存在c₁, n₁使得对所有n ≥ n₁，f(n) ≤ c₁·g(n)
• 由g(n) = O(h(n))：存在c₂, n₂使得对所有n ≥ n₂，g(n) ≤ c₂·h(n)
• 取n₀ = max(n₁, n₂)，c = c₁·c₂
• 对所有n ≥ n₀：f(n) ≤ c₁·g(n) ≤ c₁·c₂·h(n) = c·h(n)
• 因此f(n) = O(h(n))

Θ记号的等价性：

定理：f(n) = Θ(g(n))当且仅当f(n) = O(g(n))且f(n) = Ω(g(n))。

证明：

• (⇒)：由Θ定义，存在c₁, c₂, n₀使得c₁g(n) ≤ f(n) ≤ c₂g(n)

- c₂部分给出f(n) = O(g(n))

- c₁部分给出f(n) = Ω(g(n))

• (⇐)：由O和Ω的定义分别得到上界和下界，合并即为Θ

3.12 函数增长率的详细比较

增长率层次（从慢到快）：

O(1) < O(log* n) < O(log log n) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < ... < O(2ⁿ) < O(n!)

迭代对数log* n：

log* n是将n取对数直到结果≤1所需的次数。

• log* 2 = 1
• log* 4 = 2
• log* 16 = 3
• log* 65536 = 4
• log* 2^65536 = 5

log n增长极其缓慢，对于所有实际规模的输入，log n ≤ 5。

阿克曼函数和反阿克曼函数α(n)：

反阿克曼函数α(n)增长比log* n还慢。对于所有实际规模的输入，α(n) ≤ 4。并查集操作的摊还时间复杂度涉及α(n)。

3.13 渐进分析的实用技巧

多项式的处理：

• 多项式的阶由其最高次项决定
• n³ + 100n² + n + 1 = Θ(n³)
• 证明：当n ≥ 1时，n³ ≤ n³ + 100n² + n + 1 ≤ 102n³

对数的处理：

• log_a n = log_b n / log_b a，换底只是乘以常数
• 在渐进分析中，对数的底不重要
• log^k n表示(log n)^k，不是log(log(...(n)...))

求和的处理：

• Σ(i=1 to n) i = n(n+1)/2 = Θ(n²)
• Σ(i=1 to n) 1/i = H_n ≈ ln n + 0.5772 = Θ(log n)
• Σ(i=0 to n) 2^i = 2^(n+1) - 1 = Θ(2^n)

本章小结

本章系统深入地介绍了函数增长的分析方法和渐进记号。我们学习了：

五种渐进记号：Θ（紧确界）、O（上界）、Ω（下界）、o（严格上界）、ω（严格下界），它们分别对应于数学关系中的=、≤、≥、<、>。

数学性质：传递性、反射性、对称性、转置对称性的严格证明。

常见函数的增长率：从常数O(1)到阶乘O(n!)，包括迭代对数log* n和反阿克曼函数α(n)等增长极慢的函数。

函数比较方法：极限法、洛必达法则等工具可以帮助我们比较函数的增长速率。

运算规则：渐进记号的加法、乘法规则，以及多项式、对数和求和的处理技巧。

实际应用：渐进分析在算法选择、性能预测、系统设计中的重要作用。

函数的增长分析是算法理论的数学基础。掌握这些工具，我们就能更精确地分析和比较算法的效率，为后续的算法设计和分析奠定坚实基础。

关键术语

思考题

证明：对任意实数a和b，其中b > 0，有(n+a)^b = Θ(n^b)。

解释为什么"算法A的运行时间是O(n²)"和"算法A的运行时间是Θ(n²)"的含义不同。

比较以下函数对的增长率：

- n^log n 和 2^(log² n)

- n! 和 2^n

- log*(n) 和 log(log n)

设计一个算法，其运行时间为O(n log n)，并证明你的分析是正确的。