第9章 渐近分析进阶 (Advanced Asymptotic Analysis)

一、导读

9.1 本章学习目标

在本章结束时，你将能够：

• 理解渐近记号的精确定义：大O、大Ω、大Θ、小o、小ω
• 掌握渐近展开的方法和技巧
• 运用斯特林公式近似阶乘
• 使用主定理分析分治算法的复杂度
• 理解调和数的渐近行为和欧拉常数
• 应用鞍点法和拉普拉斯方法估算复杂求和
• 比较不同函数的增长速率
• 理解渐近级数与收敛级数的区别
• 掌握欧拉-麦克劳林求和公式

9.2 为什么本章如此重要

渐近分析是算法分析的基石。它提供了一种简洁而精确的方式来描述算法在输入规模趋于无穷时的行为，忽略常数因子和低阶项，聚焦于本质的增长趋势。

对于程序员而言，掌握渐近分析意味着能够：

准确评估算法效率：不依赖具体实现和硬件

选择合适的算法：根据问题规模选择最优方案

预测系统性能：估算大规模数据下的运行时间

理解理论界限：知道问题的最优复杂度是多少

优化代码：识别瓶颈并进行针对性改进

阅读学术论文：理解算法文献中的复杂度声明

《具体数学》将渐近分析放在最后，是因为它综合运用了全书的所有工具：求和、二项式系数、特殊数、生成函数、概率等。渐近分析是将离散数学与连续数学、有限与无限联系起来的桥梁。

在实际工程中，渐近分析帮助我们做出关键决策。例如，当处理百万级数据时，O(n log n) 算法比 O(n²) 算法快数千倍；当设计分布式系统时，理解通信复杂度的渐近行为可以指导架构选择。

9.3 核心问题引导

大O、大Ω、大Θ的严格定义是什么？它们之间有什么区别？

如何比较两个函数的增长速率？

斯特林公式的内容是什么？如何推导？

主定理的三种情况分别对应什么场景？

调和数 H_n 的渐近展开是什么？欧拉常数从何而来？

什么是渐近级数？它与收敛级数有何不同？

如何用渐近方法估算复杂的组合求和？

欧拉-麦克劳林公式如何连接求和与积分？

二、核心概念详解

9.1 渐近记号的精确定义

大O记号

定义：设 f(n) 和 g(n) 是从自然数到正实数的函数。我们说 f(n) = O(g(n))，如果存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有：

$$|f(n)| \leq c \cdot |g(n)|$$

直观理解：f(n) 的增长速度不超过 g(n) 的常数倍。大O给出了上界。

示例：

• 3n² + 2n + 1 = O(n²)（取 c = 4, n₀ = 1）
• log n = O(n^ε) 对任意 ε > 0
• n! = O(nⁿ)

常见误区：O(g(n)) 是一个集合，不是单个函数。写 f(n) = O(g(n)) 实际上是说 f(n) ∈ O(g(n))。

大Ω记号

定义：f(n) = Ω(g(n))，如果存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有：

$$|f(n)| \geq c \cdot |g(n)|$$

直观理解：f(n) 的增长速度不低于 g(n) 的常数倍。大Ω给出了下界。

示例：

• n³ = Ω(n²)
• 2ⁿ = Ω(n¹⁰⁰)（指数最终超过任何多项式）
• n! = Ω((n/2)^{n/2})

大Θ记号

定义：f(n) = Θ(g(n))，如果 f(n) = O(g(n)) 且 f(n) = Ω(g(n))。即存在正常数 c₁, c₂ 和 n₀，使得对所有 n ≥ n₀，有：

$$c_1 \cdot |g(n)| \leq |f(n)| \leq c_2 \cdot |g(n)|$$

直观理解：f(n) 和 g(n) 的增长速度相同（至多相差常数倍）。大Θ给出了紧确界。

示例：

• 3n² + 2n + 1 = Θ(n²)
• n log n = Θ(n log n)
• $\binom{2n}{n} = \Theta(\frac{4^n}{\sqrt{n}})$

小o记号

定义：f(n) = o(g(n))，如果对任意 ε > 0，存在 n₀，使得对所有 n ≥ n₀，有：

$$|f(n)| < \varepsilon \cdot |g(n)|$$

等价地：$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

直观理解：f(n) 的增长速度严格慢于 g(n)。

示例：

• n = o(n²)
• log n = o(n^ε) 对任意 ε > 0
• nᵏ = o(cⁿ) 对任意 k 和 c > 1

小ω记号

定义：f(n) = ω(g(n))，如果 g(n) = o(f(n))。即 $\lim_{n \to \infty} \frac{g(n)}{f(n)} = 0$。

直观理解：f(n) 的增长速度严格快于 g(n)。

示例：

• n² = ω(n)
• 2ⁿ = ω(nᵏ) 对任意 k
• n! = ω(cⁿ) 对任意常数 c

渐近等价

定义：f(n) ~ g(n)（读作"f 渐近等价于 g"），如果：

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$$

示例：n² + n ~ n²，因为 $\frac{n^2+n}{n^2} = 1 + \frac{1}{n} \to 1$。

9.2 函数增长速率的比较

以下是常见函数按增长速率从慢到快的排序：

$$1 \prec \log n \prec (\log n)^k \prec n^\epsilon \prec n \prec n \log n \prec n^2 \prec n^k \prec 2^n \prec n! \prec n^n$$

其中 k > 1，0 < ε < 1。

关键观察：

对数函数增长极慢：log₂(10⁶) ≈ 20

多项式函数中等增长

指数函数增长极快：2²⁰ ≈ 10⁶

阶乘介于指数和 nⁿ 之间

洛必达法则的应用

当直接比较困难时，可以使用洛必达法则计算极限：

$$\lim_{n \to \infty} \frac{f(n)}{g(n)}$$

如果极限为0，则 f = o(g)；如果极限为非零常数，则 f = Θ(g)；如果极限为∞，则 f = ω(g)。

示例：比较 n! 和 2ⁿ。

使用斯特林公式（见下文）：n! ≈ √(2πn)(n/e)ⁿ。

$$\frac{n!}{2^n} \approx \frac{\sqrt{2\pi n}(n/e)^n}{2^n} = \sqrt{2\pi n}\left(\frac{n}{2e}\right)^n$$

当 n > 2e ≈ 5.44 时，这个比值趋于∞，所以 n! = ω(2ⁿ)。

另一个示例：比较 (log n)ᵏ 和 n^ε。

$$\lim_{n\to\infty} \frac{(\log n)^k}{n^\epsilon} = \lim_{x\to\infty} \frac{x^k}{e^{\epsilon x}} = 0$$

（令 x = log n，则 n = eˣ）

所以对任意 k 和 ε > 0，(log n)ᵏ = o(n^ε)。

9.3 斯特林公式

定理陈述

斯特林公式（Stirling's Formula）给出了阶乘的渐近近似：

$$n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

其中 ~ 表示渐近等价，即 $\lim_{n \to \infty} \frac{n!}{\sqrt{2\pi n}(n/e)^n} = 1$。

更精确的形式

$$n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1 + \frac{1}{12n} + \frac{1}{288n^2} - \frac{139}{51840n^3} + O\left(\frac{1}{n^4}\right)\right)$$

或者用对数形式：

$$\ln(n!) = n\ln n - n + \frac{1}{2}\ln(2\pi n) + \frac{1}{12n} - \frac{1}{360n^3} + O\left(\frac{1}{n^5}\right)$$

推导思路

方法1：积分近似

$$\ln(n!) = \sum_{k=1}^{n} \ln k \approx \int_1^n \ln x \, dx = [x\ln x - x]_1^n = n\ln n - n + 1$$

这给出了主导项 n ln n - n。更精确的近似需要使用欧拉-麦克劳林求和公式。

方法2：伽马函数

n! = Γ(n+1)，其中 $\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt$。

使用拉普拉斯方法或鞍点法可以导出斯特林公式。核心思想是被积函数在 t=n 附近有尖锐的峰值，主要贡献来自该区域。

方法3：沃利斯公式

沃利斯公式：$\frac{\pi}{2} = \prod_{n=1}^{\infty} \frac{4n^2}{4n^2-1}$。

结合这个公式和二项式系数的渐近行为，可以推导出斯特林公式中的 √(2π) 因子。

应用

示例1：估算二项式系数

$$\binom{2n}{n} = \frac{(2n)!}{(n!)^2} \approx \frac{\sqrt{4\pi n}(2n/e)^{2n}}{2\pi n(n/e)^{2n}} = \frac{4^n}{\sqrt{\pi n}}$$

示例2：算法分析

某些排列算法的时间复杂度涉及 n!，使用斯特林公式可以得到更易处理的形式。例如，枚举所有排列的算法复杂度为 O(n·n!) = O(n^{n+1/2}e^{-n})。

示例3：统计物理

在统计物理中，计算微观状态数时经常涉及阶乘。斯特林公式使得这些计算变得可行。

9.4 主定理

主定理（Master Theorem）用于分析形如 T(n) = aT(n/b) + f(n) 的递推关系，其中 a ≥ 1, b > 1。

定理陈述

设 T(n) = aT(n/b) + f(n)，其中 a ≥ 1, b > 1 是常数，f(n) 是渐近正函数。令 $c = \log_b a$。

情况1：如果 f(n) = O(n^{c-ε}) 对某个 ε > 0，则 T(n) = Θ(n^c)。

情况2：如果 f(n) = Θ(n^c)，则 T(n) = Θ(n^c log n)。

情况3：如果 f(n) = Ω(n^{c+ε}) 对某个 ε > 0，且 af(n/b) ≤ kf(n) 对某个 k < 1 和充分大的 n（正则条件），则 T(n) = Θ(f(n))。

直观解释

递归树方法可以帮助理解主定理：

• 递归树有 log_b n 层
• 第 i 层有 aⁱ 个节点，每个节点的工作量为 f(n/bⁱ)
• 叶子节点总数为 a^{log_b n} = n^{log_b a} = n^c

情况1：叶子节点的工作量主导，总工作量由叶子数量决定

情况2：每层工作量大致相同，总工作量 = 每层工作量 × 层数

情况3：根节点的工作量主导，递归调用的开销相对较小

示例

示例1：归并排序

T(n) = 2T(n/2) + Θ(n)。这里 a=2, b=2, c=log₂2=1, f(n)=Θ(n)=Θ(n^c)。

属于情况2，所以 T(n) = Θ(n log n)。

示例2：二分搜索

T(n) = T(n/2) + Θ(1)。这里 a=1, b=2, c=log₂1=0, f(n)=Θ(1)=Θ(n^c)。

属于情况2，所以 T(n) = Θ(log n)。

示例3：Strassen矩阵乘法

T(n) = 7T(n/2) + Θ(n²)。这里 a=7, b=2, c=log₂7≈2.81, f(n)=Θ(n²)=O(n^{2.81-ε})。

属于情况1，所以 T(n) = Θ(n^{log₂7}) ≈ Θ(n^{2.81})。

示例4：朴素矩阵乘法的分治版本

T(n) = 8T(n/2) + Θ(n²)。这里 a=8, b=2, c=log₂8=3, f(n)=Θ(n²)=O(n^{3-ε})。

属于情况1，所以 T(n) = Θ(n³)。这与朴素矩阵乘法的复杂度一致。

主定理的局限

主定理不适用于：

• f(n) 不是多项式的情况
• a 或 b 不是常数的情况
• 子问题规模不均匀的情况

对于这些情况，需要使用其他方法，如递归树、代入法或Akra-Bazzi定理。

9.5 调和数的渐近展开

基本展开

$$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \cdots$$

其中 γ ≈ 0.5772156649 是欧拉-马斯刻若尼常数。

推导

使用欧拉-麦克劳林求和公式：

$$\sum_{k=1}^{n} f(k) = \int_1^n f(x)dx + \frac{f(1)+f(n)}{2} + \sum_{k=1}^{m} \frac{B_{2k}}{(2k)!}(f^{(2k-1)}(n)-f^{(2k-1)}(1)) + R_m$$

对于 f(x) = 1/x：

• $\int_1^n \frac{1}{x}dx = \ln n$
• $\frac{f(1)+f(n)}{2} = \frac{1+1/n}{2}$
• 高阶导数涉及伯努利数

经过计算可得上述展开式。

欧拉常数

欧拉-马斯刻若尼常数定义为：

$$\gamma = \lim_{n\to\infty} \left(H_n - \ln n\right) \approx 0.5772156649$$

这是一个重要的数学常数，出现在许多数学公式中。目前尚不清楚 γ 是否是有理数。

广义调和数

$$H_n^{(r)} = \sum_{k=1}^{n} \frac{1}{k^r}$$

当 r > 1 时，$H_\infty^{(r)} = \zeta(r)$（黎曼ζ函数）。

例如：$H_\infty^{(2)} = \frac{\pi^2}{6}$，$H_\infty^{(4)} = \frac{\pi^4}{90}$。

当 r = 1 时，调和级数发散，$H_n \sim \ln n$。

9.6 渐近级数

定义

渐近级数是一个形式级数 $\sum_{k=0}^{\infty} a_k \phi_k(n)$，使得对任意 m：

$$f(n) - \sum_{k=0}^{m-1} a_k \phi_k(n) = O(\phi_m(n))$$

其中 φₖ(n) 是一个渐近序列，通常 φₖ₊₁(n) = o(φₖ(n))。

关键点：渐近级数不一定收敛！它只是在截断后给出良好的近似。

示例

斯特林公式的完整展开是一个渐近级数：

$$n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \sum_{k=0}^{\infty} \frac{a_k}{n^k}$$

这个级数是发散的，但取前几项就能得到极好的近似。

与收敛级数的区别

• 收敛级数：固定 x，让项数趋于无穷，和趋近于某个值
• 渐近级数：固定项数，让变量趋于无穷，误差相对于最后一项是小量

最佳截断：对于渐近级数，存在一个最佳截断点，超过该点后增加项数反而会增加误差。这是因为渐近级数的系数通常快速增长。

9.7 欧拉-麦克劳林求和公式

欧拉-麦克劳林求和公式连接了求和与积分：

$$\sum_{k=a}^{b} f(k) = \int_a^b f(x)dx + \frac{f(a)+f(b)}{2} + \sum_{k=1}^{m} \frac{B_{2k}}{(2k)!}(f^{(2k-1)}(b)-f^{(2k-1)}(a)) + R_m$$

其中 B₂ₖ 是伯努利数，Rₘ 是余项。

应用：

• 推导调和数的渐近展开
• 估算复杂的求和
• 数值积分的误差分析

9.8 拉普拉斯方法与鞍点法

拉普拉斯方法

用于估算形如 $\int_a^b e^{Mf(x)}g(x)dx$ 的积分，当 M 很大时。

核心思想：积分的主要贡献来自 f(x) 的最大值点附近。在最大值点 x₀ 处做泰勒展开：

$$f(x) \approx f(x_0) + \frac{1}{2}f''(x_0)(x-x_0)^2$$

积分近似为高斯积分：

$$\int_a^b e^{Mf(x)}g(x)dx \approx e^{Mf(x_0)}g(x_0)\sqrt{\frac{2\pi}{-Mf''(x_0)}}$$

鞍点法

用于估算复平面上的围道积分，是拉普拉斯方法的推广。

应用：从生成函数中提取系数的渐近行为。例如，使用柯西积分公式：

$$[z^n]A(z) = \frac{1}{2\pi i}\oint \frac{A(z)}{z^{n+1}}dz$$

通过选择合适的围道（经过鞍点），可以估算系数的渐近行为。

三、程序员的视角

9.1 在算法分析中的应用

复杂度分类

• O(1)：常数时间，如数组访问
• O(log n)：对数时间，如二分搜索
• O(n)：线性时间，如遍历
• O(n log n)：如归并排序、快速排序平均情况
• O(n²)：如冒泡排序、朴素矩阵乘法
• O(2ⁿ)：指数时间，如旅行商问题的暴力解法
• O(n!)**：阶乘时间，如全排列枚举

实际意义

可以看出，指数和阶乘算法即使在 n 较小时也变得不可行。

空间复杂度

渐近分析也适用于空间复杂度。例如：

• 数组：O(n)
• 平衡二叉搜索树：O(n)
• 动态规划表格：O(n²) 或 O(n)

9.2 常见陷阱

陷阱1：忽视常数因子

虽然渐近分析忽略常数，但在实际应用中，常数可能很重要。例如，O(n) 算法可能比 O(n log n) 算法慢，如果常数因子很大。

建议：在实际系统中，同时考虑渐近复杂度和常数因子。

陷阱2：平均情况 vs 最坏情况

渐近分析通常针对最坏情况。平均情况分析需要概率知识，可能得出不同的结论。

示例：快速排序最坏情况 O(n²)，但平均情况 O(n log n)。

陷阱3：小输入规模

对于小输入规模，渐近行为可能不适用。简单算法可能比复杂算法更快。

建议：在实际实现中，对小输入使用简单算法，对大输入使用高效算法（如混合排序）。

9.3 与其他领域的联系

• 物理学：统计力学中的大数近似
• 工程学：信号处理的渐近行为
• 经济学：大规模市场行为的近似
• 生物学：种群增长的渐近模型

四、代码实战

9.1 渐近分析工具

import math
import time

class AsymptoticAnalysis:
    """渐近分析工具"""
    
    @staticmethod
    def stirling_approximation(n):
        """斯特林公式近似 n!"""
        return math.sqrt(2 * math.pi * n) * (n / math.e) ** n
    
    @staticmethod
    def stirling_log(n):
        """斯特林公式的对数形式"""
        return n * math.log(n) - n + 0.5 * math.log(2 * math.pi * n)
    
    @staticmethod
    def harmonic_asymptotic(n, terms=3):
        """调和数的渐近近似"""
        gamma = 0.57721566490153286060651209008240243104215933593992
        result = math.log(n) + gamma
        if terms >= 2:
            result += 1.0 / (2 * n)
        if terms >= 3:
            result -= 1.0 / (12 * n**2)
        if terms >= 4:
            result += 1.0 / (120 * n**4)
        return result
    
    @staticmethod
    def compare_growth_rates():
        """比较不同函数的增长速率"""
        print("函数增长速率比较:")
        print(f"{'n':>6} {'log n':>10} {'n':>8} {'n log n':>12} {'n^2':>10} {'2^n':>12}")
        print("-" * 70)
        
        for n in [10, 20, 50, 100]:
            log_n = math.log2(n)
            n_log_n = n * log_n
            n_sq = n ** 2
            two_pow_n = 2 ** n
            
            print(f"{n:>6} {log_n:>10.2f} {n:>8} {n_log_n:>12.2f} {n_sq:>10} {two_pow_n:>12.2e}")
    
    @staticmethod
    def master_theorem_example(a, b, f_n_order, n):
        """主定理示例：计算 T(n) = a*T(n/b) + n^f_n_order 的渐近行为"""
        c = math.log(a, b)
        
        if f_n_order < c:
            return f"T(n) = Θ(n^{c:.3f}) [情况1]"
        elif abs(f_n_order - c) < 1e-10:
            return f"T(n) = Θ(n^{c:.3f} log n) [情况2]"
        else:
            return f"T(n) = Θ(n^{f_n_order:.3f}) [情况3]"
    
    @staticmethod
    def binomial_asymptotic(n, k):
        """使用斯特林公式近似二项式系数"""
        # C(n,k) ≈ sqrt(n/(2*pi*k*(n-k))) * n^n / (k^k * (n-k)^(n-k))
        if k == 0 or k == n:
            return 1
        coeff = math.sqrt(n / (2 * math.pi * k * (n - k)))
        val = coeff * (n**n) / (k**k * (n-k)**(n-k))
        return val

# 测试
aa = AsymptoticAnalysis()

print("=== 渐近分析测试 ===")

# 斯特林公式验证
print("\n斯特林公式验证:")
print(f"{'n':>6} {'n!':>15} {'斯特林近似':>15} {'相对误差':>12}")
print("-" * 50)
for n in [1, 5, 10, 20]:
    exact = math.factorial(n)
    approx = aa.stirling_approximation(n)
    error = abs(exact - approx) / exact
    print(f"{n:>6} {exact:>15} {approx:>15.2f} {error:>12.6f}")

# 更精确的斯特林公式
print("\n更精确的斯特林公式:")
for n in [5, 10, 20]:
    exact = math.factorial(n)
    approx_basic = aa.stirling_approximation(n)
    # 加入 1/(12n) 修正
    approx_corrected = approx_basic * (1 + 1/(12*n))
    error_basic = abs(exact - approx_basic) / exact
    error_corrected = abs(exact - approx_corrected) / exact
    print(f"n={n}: 基本误差={error_basic:.6f}, 修正后误差={error_corrected:.6f}")

# 调和数渐近近似
print("\n调和数渐近近似:")
print(f"{'n':>6} {'H_n (精确)':>15} {'渐近近似':>15} {'误差':>12}")
print("-" * 50)
for n in [10, 100, 1000]:
    exact = sum(1.0/k for k in range(1, n+1))
    approx = aa.harmonic_asymptotic(n)
    error = abs(exact - approx)
    print(f"{n:>6} {exact:>15.8f} {approx:>15.8f} {error:>12.2e}")

# 增长速率比较
print()
aa.compare_growth_rates()

# 主定理示例
print("\n主定理示例:")
print(aa.master_theorem_example(2, 2, 1, 100))  # 归并排序
print(aa.master_theorem_example(7, 2, 2, 100))  # Strassen
print(aa.master_theorem_example(1, 2, 0, 100))  # 二分搜索

# 二项式系数渐近
print("\n二项式系数渐近:")
n, k = 100, 50
exact = math.comb(n, k)
approx = aa.binomial_asymptotic(n, k)
error = abs(exact - approx) / exact
print(f"C({n},{k}): 精确值≈{exact:.2e}, 近似值≈{approx:.2e}, 相对误差={error:.6f}")

9.2 实验：不同排序算法的实际性能

import random
import time

def bubble_sort(arr):
    """冒泡排序 O(n^2)"""
    n = len(arr)
    arr = arr.copy()
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def merge_sort(arr):
    """归并排序 O(n log n)"""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def benchmark_sorting(sort_func, sizes):
    """基准测试排序算法"""
    results = []
    for n in sizes:
        arr = [random.randint(0, n) for _ in range(n)]
        start = time.time()
        sort_func(arr)
        elapsed = time.time() - start
        results.append((n, elapsed))
    return results

# 测试
sizes = [100, 500, 1000, 2000]
print("\n排序算法性能比较:")
print(f"{'n':>6} {'冒泡排序(s)':>15} {'归并排序(s)':>15}")
print("-" * 40)

bubble_results = benchmark_sorting(bubble_sort, sizes)
merge_results = benchmark_sorting(merge_sort, sizes)

for i, n in enumerate(sizes):
    print(f"{n:>6} {bubble_results[i][1]:>15.6f} {merge_results[i][1]:>15.6f}")

五、深入思考

5.1 历史背景

渐近分析起源于19世纪的数学分析。高德纳（Donald Knuth）在其《计算机程序设计艺术》中系统地将渐近分析应用于算法分析。主定理由Jon Bentley、Dorothea Haken等人推广。斯特林公式由詹姆斯·斯特林于1730年发表，但更早的形式已被德·莫弗尔发现。

5.2 未解决的问题

紧确界的存在性：某些问题的最优复杂度是否有多项式时间的紧确界？P vs NP 问题

渐近级数的最优截断：如何选择截断点以获得最佳近似？

超越主定理的情况：如何处理非标准形式的递推关系？Akra-Bazzi定理提供了部分答案

5.3 延伸阅读

《具体数学》第9章 - Graham, Knuth, Patashnik

《Introduction to Algorithms》第3章 - Cormen et al.

《Analytic Combinatorics》 - Philippe Flajolet and Robert Sedgewick

《The Art of Computer Programming, Vol. 1》 - Donald Knuth

《Asymptotic Methods in Integrals》 - Bleistein and Handelsman

六、实验笔记

实验一：斯特林公式的精度分析

目标：分析斯特林公式在不同 n 值下的精度，验证渐近展开的各项贡献。

步骤：

计算 n! 的精确值（使用高精度库）

计算斯特林近似值（不同阶数的展开）

比较相对误差随 n 的变化

绘制误差曲线

思考题：

• 需要多少项才能达到双精度浮点数的极限？
• 最佳截断点在哪里？

实验二：主定理的验证

目标：通过实际运行时间验证主定理的预测。

步骤：

实现归并排序、Strassen矩阵乘法等算法

测量不同 n 值的运行时间

拟合 T(n)/n^c 或 T(n)/(n^c log n) 的行为

验证是否符合主定理的预测

注意：实际运行时间受常数因子、缓存效应等影响，可能需要较大 n 才能观察到渐近行为。

实验三：调和数的收敛性

目标：验证 Hₙ - ln n 趋近于欧拉常数 γ。

步骤：

计算不同 n 值的 Hₙ

计算 Hₙ - ln n

观察是否趋近于 γ ≈ 0.5772...

尝试外推法加速收敛

七、本章小结

关键概念：

• 渐近记号：O, Ω, Θ, o, ω
• 斯特林公式：$n! \sim \sqrt{2\pi n}(n/e)^n$
• 主定理：分析 T(n) = aT(n/b) + f(n)
• 调和数渐近：$H_n = \ln n + \gamma + \frac{1}{2n} - \cdots$
• 欧拉-麦克劳林公式：连接求和与积分

核心技巧：

使用极限比较函数增长率

用斯特林公式近似阶乘和二项式系数

用主定理快速分析分治算法

理解渐近级数与收敛级数的区别

使用欧拉-麦克劳林公式推导渐近展开

实用建议：

• 在实际应用中，不要忽视常数因子
• 平均情况分析通常需要概率知识
• 渐近分析是工具，不是目的；始终结合实际需求
• 对于小输入，简单算法可能更高效

八、习题

基础题

习题 9.1：证明 n² + 3n + 2 = Θ(n²)。

提示：找到合适的 c₁, c₂, n₀。

习题 9.2：使用斯特林公式估算 $\binom{100}{50}$。

提示：使用 $\binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}$。

习题 9.3：用主定理分析 T(n) = 4T(n/2) + n² 的渐近行为。

提示：a=4, b=2, c=log₂4=2, f(n)=n²=Θ(n^c)，属于情况2。

习题 9.4：计算 H₁₀₀ 的近似值。

提示：使用 Hₙ ≈ ln n + γ + 1/(2n)。

进阶题

习题 9.5：[ME] 证明 $\lim_{n \to \infty} \frac{\log n}{n^\epsilon} = 0$ 对任意 ε > 0。

提示：使用洛必达法则或换元 x = log n。

习题 9.6：[ME] 推导调和数的渐近展开的前三项。

提示：使用欧拉-麦克劳林公式，f(x) = 1/x。

习题 9.7：[ME] 比较 n! 和 nⁿ 的增长速率。

提示：使用斯特林公式，n! ~ √(2πn)(n/e)ⁿ，而 nⁿ = e^{n ln n}。

挑战题

习题 9.8：[HM25] 使用欧拉-麦克劳林公式推导更精确的斯特林公式。

提示：对 f(x) = ln x 应用公式，从 1 到 n 求和。

习题 9.9：[HM30] 研究阿克曼函数的渐近行为及其逆函数。

提示：阿克曼函数 A(m,n) 增长极快。其逆函数 α(n) 增长极慢，α(n) ≤ 4 对所有实际输入的 n。

习题 9.10：[HM40] 证明主定理的三种情况，并给出反例说明正则条件的必要性。

提示：使用递归树方法。对于正则条件的反例，考虑 T(n) = 2T(n/2) + n sin²(n)。

本章完

《具体数学》教材重写完成