沃利斯积分的分段渐近估阶：拉普拉斯方法的思想启蒙

摘要: 分段渐近估阶的例子，与实践中的注意事项

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 冒泡排序平均需要跑多少趟：拉马努金Q函数初探 和 插入多少次发生哈希冲突：拉马努金Q分布与二元渐近分析 中，我们通过对算法分析中的实际问题的分析，导出了两个和式的渐近估阶问题：

$$Q(N) = \sum\limits_{k=1}\limits^{N}\frac{N!}{(N-k)!N^{k}}$$ $$P(N) = \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!}$$

其中 $Q(N)$ 称为 Ramanujan Q 函数，$P(N)$ 称为 Ramanujan-Knuth P 函数，在《计算机程序设计艺术》中有关于这两个函数的相关论述。这两个函数 $N\rightarrow\infty$ 时的渐近估阶问题，都涉及到关于 $k, N$ 的二元渐进性问题，在估阶的时候需要对 $k$ 的不同范围分别讨论。

比较巧合的是，这两个和式的估阶的主项都是 $\sqrt{\frac{\pi N}{2}}$，基于这个结论，在前面两篇文章中，我们解决了冒泡排序平均比较次数、哈希冲突前的平均插入条数等问题。

而要推导出上述估阶的主项，并给出误差界，需要用到拉普拉斯方法，大致的思想是把求和范围从中间截断，分为两段，例如截断点为 $k_{0}$，于是 $\sum\limits_{k=0}\limits^{N}$ 就变为了 $\sum\limits_{k=0}\limits^{k_{0}}$ 和 $\sum\limits_{k=k_{0}+1}\limits^{N}$ 两段。原因在于 $0 \leq k \leq k_{0}$ 以及 $k_{0} < k \leq N$ 时，被加数的渐近估阶不一样，因此需要分段处理。

进一步问：为什么 k 在不同范围的时候，被加项 $f(k, N)$ 的渐近估阶不一样。原因就在于推导过程中在使用诸如 $e^{x}$，$\ln(x)$ 等函数的带大 $O$ 余项的泰勒展开的时候，条件是展开的函数在 $x$ 的范围内有界才能这么展开。展开的余项 $O(g)$ 符号其实是一个不等式，因此也可以理解为只有在 $x$ 的范围使得所展开的函数有界的时候，带大 $O$ 余项的泰勒展开所隐含的不等式才成立。

而这里 $x$ 是一个与 $k$ 和 $N$ 都有关的量，即 $x=x(k,N)$，这就造成了 k 与 N 满足一定关系的时候，x 满足带大 O 余项泰勒展开的成立范围，而 k 与 N 不满足一定关系的时候，x 就不在带大 O 余项的泰勒展开所需的成立范围了，需要进行其它处理。

本文我们暂时搁置拉马努金 Q 函数的渐近估阶问题。先解决以下沃利斯积分(Wallis) $I_{n}$，当 $n\rightarrow\infty$ 的渐近估阶问题，这个问题更加经典，并且容易提取出方法论：

$$I_{n} = \int^{\frac{\pi}{2}}_{-\frac{\pi}{2}}(\cos x)^{n}\mathrm{d}x = \sqrt{\frac{2\pi}{n}} + O(n^{-\frac{3}{5}})$$

本文的大致内容如下：

• 我们首先介绍大 O 小 o 符号的定义及其区别，以及带大 O 余项和小 o 余项的泰勒展开的区别。
• 然后通过沃利斯积分的例子说明为什么要进行分段渐近估阶。
• 用分段渐近估计的方法给出以上沃利斯积分的渐近估阶。
• 由以上沃利斯积分渐近估阶的解决过程，引出拉普拉斯方法的思想的流程。

在下一篇文章中，我们用拉普拉斯方法推导拉马努金 Q 函数的渐近估阶。

---

带大 O 余项的泰勒展开

对于泰勒展开公式，我们在大学中比较熟悉的是带 peano 余项和带 Lagrange 余项这两种。

在渐近估阶当中，更实用的是带大 O 余项的，定理描述如下：

定理 (带大 O 余项的泰勒展开)

在 $x_{0}$ 的某个邻域内，若 $f^{(n)}(x)$ 存在且有界，即 $|f^{(n)}(x)| \leq M$，则：

$$f(x) = \sum\limits_{k=0}\limits^{n-1}\frac{f^{(n)}(x_{0})}{k!}(x - x_{0})^{k} + O(|x - x_{0}|^{n})$$

在 $x_{0}$ 的该邻域内成立。

这里需要注意，上述展开成立的范围是 $x_{0}$ 的邻域内，这是一个范围，具体讲就是使得 $f^{(n)}(x)$ 有界的 $x$ 的取值范围。另一方面 $O$ 符号本质上是个不等式，这从大 O 符号的定义可以看出来。

定义 (大 O 符号)

设 $g(x)>0$，若存在常数 $A > 0$，使得当 $x\in (a, b)$ 时有：

$$|f(x)| \leq Ag(x)$$

则称当 $x\in(a,b)$ 时，$g(x)$ 是 $f(x)$ 的强函数，记为：

$$f(x) = O(g(x)) \quad\quad x\in(a,b)$$

因此带大 O 余项的泰勒展开其实就是当 $x$ 在某个范围（使得 $f^{(n)}(x)$ 有界的范围）内成立的不等式。而带小 o 符号的余项，也就是 peano 余项的泰勒展开，仅仅是一个局部的极限过程，无法描述整体。这就是为什么渐近估阶当中一般用大 O 符号的原因。

以下是几个非常常用的带大 O 余项的泰勒展开：

• (1) $e^{f} = 1 + f + O(f^{2}) \quad\quad \sup f < +\infty$

这个公式展开的是 $e^{f}$，而只有当 $f$ 必须有界的时候，$e^{f}$ 才有界，因此上面的带大 O 余项的泰勒展开的条件是 $\sup f < + \infty$。

• (2) $\cos(f) = 1 - \frac{f}{2} + O(f^{4})$

由于不论 $f$ 取什么值，$\cos f$ 总有界，因此以上带大 O 余项的泰勒展开总成立。

• (3) $\ln(1 + f) = f + O(f^{2}) \quad\quad \inf f > -1$

由于 $\ln(1 + f)$ 只有当 $f > -1$ 的时候才有界，因此以上带大 O 余项的泰勒展开式成立的条件的 $\inf f > -1$。

带参变量的大 O 符号

这里还需要注意的一点是，大 O 符号中的定义中有个常数 $A$，这个常数是与自变量无关的，但常数 $A$ 却可能跟参变量有关。

比如 $\sin(nx) = O(n)$ 中，$x$ 作为参变量，式中 $O(n)$ 的大 O 常数 $A$ 与 $x$ 是有关的，如果把符号记全，应该写为 $\sin(nx) = O_{x}(n)$。

如果要对 $\sin(nx)$ 求和或积分进行渐近估阶，例如 $\int_{a}^{b}\sin(nx)\mathrm{d}x$ 当 $n\rightarrow \infty$ 的渐近估阶，将被积函数的估阶代入即有 $\int_{a}^{b}O(n)\mathrm{d}x$，但注意，这里的大 O 是有参变量 $x$ 的，因此对 $x$ 积分的时候，就不能把其中的 $O(n)$ 作为常数处理。

下面我们看一个具体的例子：$(\cos\frac{x}{\sqrt{n}})^{n}$ 以及 $\int^{\frac{\pi}{2}}_{0}(\cos\frac{x}{\sqrt{n}})^{n}\mathrm{d}x$ 当 $n\rightarrow\infty$ 的渐近估阶。从该例子中我们可以看到参变量对渐近估阶的影响。

下面我们推导以下渐近估阶：

$$(\cos \frac{x}{\sqrt{n}})^{n} = e^{-\frac{x^{2}}{2}}(1 + O(\frac{1}{n}))$$

其中 $x$ 可以理解为参变量，当 x 为一个已知常数的时候，上述估计是正确的。大致的推导过程如下：

$$\begin{align} (\cos \frac{x}{\sqrt{n}})^{n} &= (1 - \frac{x^{2}}{2n} + O(\frac{1}{n^{2}}))^{n} \\ &= e^{n\ln(1 - \frac{x^{2}}{2n} + O(\frac{1}{n^{2}}))} \\ &= e^{n(-\frac{x^{2}}{2n} + O(\frac{1}{n^{2}}) + O((-\frac{x^{2}}{2n} + O(\frac{1}{n^{2}}))^{2})} \\ &= e^{n(-\frac{x^{2}}{2n} + O(\frac{1}{n^{2}}))} \\ &= e^{-\frac{x^{2}}{2} + O(\frac{1}{n})} \\ &= e^{-\frac{x^{2}}{2}}(1 + O(\frac{1}{n})) \\ \end{align}$$

上面的推导过程中，第一行用到了 $\cos x$ 的展开、第三行用到了 $\ln x$ 的展开、最后一行用到了 $e^{x}$ 的展开。在使用这些展开的时候，$x$ 均为已知常数。

如果我们要基于上述 $(\cos \frac{x}{\sqrt{n}})^{n}$ 的估阶结果，对以该函数作为被积函数的积分 $\int^{\frac{\pi}{2}\sqrt{n}}_{0}(\cos\frac{x}{\sqrt{n}})^{n}\mathrm{d}x$ 进行渐近估阶的话，一个比较自然的思路如下：

$$\int^{\frac{\pi}{2}\sqrt{n}}_{0}(\cos\frac{x}{\sqrt{n}})^{n}\mathrm{d}x = \int^{\frac{\pi}{2}\sqrt{n}}_{0}e^{-\frac{x^{2}}{2}}(1 + O(\frac{1}{n}))\mathrm{d}x$$

但是前面我们提到过，式中的 $O(\frac{1}{n})$ 是带有参变量 $x$ 的，因此上述积分中的 $O(\frac{1}{n})$ 不能视为常数，并不是很好处理。因此需要把参变量 $x$ 写进 $O$ 中，推导见下一节。

为什么要进行分段估计

如前所述，我们需要在大 $O$ 符号中把参变量 $x$ 也写进去。推导过程如下：

$$\begin{align} (\cos \frac{x}{\sqrt{n}})^{n} &= (1 - \frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}))^{n} \\ &= e^{n\ln(1 - \frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}))} \\ &= e^{n(-\frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}) + O((-\frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}))^{2})} \\ &= e^{n(-\frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}))} \\ &= e^{-\frac{x^{2}}{2} + O(\frac{x^{4}}{n})} \\ &= e^{-\frac{x^{2}}{2}}(1 + O(\frac{x^{4}}{n})) \\ \end{align}$$

但注意，上面的推导过程中，第一行用到了 $\cos x$ 的展开、第三行用到了 $\ln x$ 的展开、最后一行用到了 $e^{x}$ 的展开。

这些展开必须要 $x$ 在使得被展开函数有界的范围内，这些展开才成立，下面我们分别看这几个展开。

首先是第一行的 $\cos \frac{x}{\sqrt{n}}$，由于不论 $\frac{x}{\sqrt{n}}$ 取什么值，$cos$ 函数总有界，上述展开均成立。

其次是第三行的 $\ln(1 - \frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}))$，这步展开想要成立，需要 $ - \frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}})$ 不能趋于 $-1$。但是这一项是有可能趋于 -1 的，原因在于 $ - \frac{x^{2}}{2n} + O(\frac{x^{4}}{n^{2}}) = \cos\frac{x}{\sqrt{n}} - 1$，而 $\cos\frac{x}{\sqrt{n}}$ 在当 $x$ 与 $n$ 满足一定关系时是有可能趋于 0 的。具体就是当 $x\rightarrow \frac{\pi}{2}\sqrt{n}$ 时，$\frac{x}{\sqrt{n}} \rightarrow \frac{\pi}{2}$。因此这一步想要成立，$x$ 就不能充分接近 $\frac{\pi}{2}\sqrt{n}$。

然后是最后一行的 $e^{O(\frac{x^{4}}{n})}$，这步展开需要 $O(\frac{x^{4}}{n})$ 有界，也就是不能趋于无穷才行，因此 $x = O(n^{-4})$ 时，这步展开才能成立。

因此在处理积分 $\int^{\frac{\pi}{2}\sqrt{n}}_{0}(\cos\frac{x}{\sqrt{n}})^{n}\mathrm{d}x$ 时，必须要 $x = O(n^{-4})$ 时才能进行 $(\cos\frac{x}{\sqrt{n}})^{n}$ 的上述展开。

但是另一方面，积分范围 $\int^{\frac{\pi}{2}\sqrt{n}}_{0}$ 横跨了 $O(n^{-4})$，因此想要对上述积分渐近估阶，就必须要以 $O(n^{-4})$ 为分割点，将积分区间分为两段，分段处理。

能够得到多精确的估阶，就要看分段分的怎么样。分段分的越漂亮，估计的就越精确。下面我们就用分段估计法估计沃利斯积分 $I_{n}$。

沃利斯积分的分段渐近估阶

经过前面的铺垫，现在我们来处理沃利斯积分的渐近估阶问题。也就是 $n\rightarrow\infty$ 时，估计以下积分：

$$I_{n} = \int^{\frac{\pi}{2}}_{-\frac{\pi}{2}}(\cos x)^{n}\mathrm{d}x$$

由于余弦函数在 $x = 0$ 处取到最大值 1，另一方面被积函数是一个很大的幂 ($n\rightarrow\infty$)，因此在任何包含 0 的线段之外的部分对积分的贡献都是指数级的小量，因而在对积分渐近估计时可以丢弃。该线段我们称其为积分的中心范围，这是我们处理该积分的初始想法，沿着这个想法我们继续往下看。

首先进行换元 $x = \frac{w}{\sqrt{n}}$，于是原积分可以写为：

$$I_{n} = \frac{1}{\sqrt{n}}\int^{\frac{\pi}{2}\sqrt{n}}_{-\frac{\pi}{2}\sqrt{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w$$

另一方面，根据前面推导过的渐近估阶，可得：

$$(\cos x)^{n} = (\cos \frac{w}{\sqrt{n}})^{n} = e^{-\frac{w^{2}}{2}}(1 + O(w^{4}n^{-1}))$$

根据前面的讨论，只要 $w = O(n^{\frac{1}{4}})$，前面推导过程中用到的几个带大 O 余项的泰勒展开就都成立。因此我们可以考虑选 $k_{n} = n^{\frac{1}{10}}$ 作为分段的分割点（这个分割点的取法不唯一，但最终估阶的精确程度与分割点的取法有关）。

用 $|w| \leq k_{n}$ 来定义中心范围，于是在该范围内，积分可以写为：

$$\frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w$$

$[-k_{n}, k_{n}]$ 这个范围内的上述积分称为估计的主部，其余的部分称为尾部。

分段估计的思想就是分别估计主部和尾部，下面我们分为三步来处理：

第1步：忽略原积分的尾部

由于 $w = O(n^{-4})$ 时有 $(\cos \frac{w}{\sqrt{n}})^{n} = e^{-\frac{w^{2}}{2}}(1 + O(w^{4}n^{-1}))$，因此 $n\rightarrow\infty$ 时，我们有 $(\cos\frac{k_{n}}{\sqrt{n}})^{n} \sim e^{-\frac{n^{1/5}}{2}}$。

另一方面，由于被积函数 $(\cos\frac{w}{\sqrt{n}})^{n}$ 在积分范围内是单峰的，因此 $k_{n} < |w| < \frac{\pi}{2}\sqrt{n}$ 这部分积分区间的大部分上，被积函数都是关于 $k_{n}$ 的指数级小量。因此就有：

$$\begin{align} I_{n} &= \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w + \frac{1}{\sqrt{n}}(\int^{\frac{\pi}{2}\sqrt{n}}_{k_{n}} + \int^{-k_{n}}_{-\frac{\pi}{2}\sqrt{n}}) \\ &= \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w + O(e^{-\frac{k_{n}^{2}}{2}}) \end{align}$$

也就是说，忽略尾部，以中心区域的积分作为估计的主部，误差界为 $O(e^{-\frac{k_{n}^{2}}{2}}) = O(e^{-\frac{n^{1/5}}{2}})$。

第2步：对中心区域渐近估阶

$$\begin{align} \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w &= \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}(1 + O(w^{4}n^{-1}))\mathrm{d}w \\ &= \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}\mathrm{d}w + O(n^{-\frac{3}{5}}) \\ \end{align}$$

第3步：完成尾部

对于上式中 $\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}\mathrm{d}w$ 这个积分，可以看出该积分的尾部也很小，具体就是对于 $W \geq 0$，有：

$$\int^{\infty}_{W}e^{-\frac{w^{2}}{2}}\mathrm{d}w \leq e^{-\frac{W^{2}}{2}}\int^{\infty}_{0}e^{-\frac{h^{2}}{2}}\mathrm{d}h = \sqrt{\frac{\pi}{2}}e^{-\frac{W^{2}}{2}}$$

因此做变量代换 $w = W + h$ 就有：

$$\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}\mathrm{d}w = \int^{\infty}_{-\infty}e^{-\frac{w^{2}}{2}}\mathrm{d}w + O(e^{-\frac{1}{2}k_{n}^{2}})$$

完整估阶

由前面三步对应的三个逼近：

$$I_{n} = \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w + O(e^{-\frac{k_{n}^{2}}{2}})$$ $$\frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w = \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}\mathrm{d}w + O(n^{-\frac{3}{5}}) \\$$ $$\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}\mathrm{d}w = \int^{\infty}_{-\infty}e^{-\frac{w^{2}}{2}}\mathrm{d}w + O(e^{-\frac{1}{2}k_{n}^{2}})$$

合起来，就得出沃利斯积分的最终的完整渐近估阶：

$$I_{n} = \frac{1}{\sqrt{n}}\int^{\infty}_{-\infty}e^{-\frac{w^{2}}{2}}\mathrm{d}w + O(n^{-\frac{3}{5}}) = \sqrt{\frac{2\pi}{n}} + O(n^{-\frac{3}{5}})$$

拉普拉斯方法

从上述对沃利斯积分的渐近估阶的过程，我们已经可以总结出拉普拉斯方法的思想。

拉普拉斯方法适用于估计一个依赖于大参数 $n$ 作为幂的实积分，当 $n\rightarrow\infty$ 时，积分的渐近行为。其基本思想是利用积分中的指数项在某个点（通常是函数的极值点）附近的局部性质来近似整个积分。其具体步骤分为三步：

(1) 忽略尾部：估计原积分的尾部并忽略
(2) 中心逼近：在中心区域进行逼近并得到误差界
(3) 完成尾部：将尾部的积分范围加到中心区域的逼近中

对于沃利斯积分的例子，其各个步骤按照拉普拉斯方法的流程大致如下：

$$\begin{align} I_{n} &= \int^{\frac{\pi}{2}}_{-\frac{\pi}{2}}(\cos x)^{n}\mathrm{d}x \\ &\sim \frac{1}{\sqrt{n}}\int^{\frac{\pi}{2}\sqrt{n}}_{-\frac{\pi}{2}\sqrt{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w \quad\quad (令 x = \frac{w}{\sqrt{n}}，取 k_{n} = n^{\frac{1}{10}}) \\ &\sim \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}(\cos \frac{w}{\sqrt{n}})^{n}\mathrm{d}w \quad\quad (忽略尾部) \\ &\sim \frac{1}{\sqrt{n}}\int^{k_{n}}_{-k_{n}}e^{-\frac{w^{2}}{2}}\mathrm{d}w \quad\quad (中心逼近) \\ &\sim \frac{1}{\sqrt{n}}\int^{\infty}_{-\infty}e^{-\frac{w^{2}}{2}}\mathrm{d}w \quad\quad (完成尾部) \\ &\sim \sqrt{\frac{2\pi}{n}} \end{align}$$

完全渐近展开

由于尾部中的指数级小误差项相对于中心逼近中的多项式级误差项 $O(w^{4}n^{-1})$ 可以忽略，因此决定最终的估计式的误差的因素就在于中心逼近的误差。

而中心逼近的解决过程是分段渐近估计，分段渐近估计的过程主要就是函数在所分的段中有界，进而应用带大 O 余项的泰勒展开，只要在泰勒展开中取更多的项，中心逼近的误差就可以改进。

对于以上沃利斯积分 $I_{n}$ 来说，前面我们取的是：

$$(\cos \frac{w}{\sqrt{n}})^{n} = e^{-\frac{w^{2}}{2}}(1 + O(w^{4}n^{-1}))$$

最终得到：

$$I_{n} = \sqrt{\frac{2\pi}{n}} + O(n^{-\frac{3}{5}})$$

而如果我们多取一项：

$$(\cos \frac{w}{\sqrt{n}})^{n} = e^{-\frac{w^{2}}{2}}(1 - \frac{w^{4}}{12n} + O(w^{8}n^{-2}))$$

那么就可以对结果增加一个校正项：

$$\epsilon_{n} = -\frac{1}{\sqrt{n}}\int_{-\infty}^{\infty}e^{-\frac{w^{2}}{2}}\frac{w^{4}}{12n}\mathrm{d}w = -\sqrt{\frac{\pi}{8n^{3}}}$$

最终得到：

$$I_{n} = \sqrt{\frac{2\pi}{n}} - \sqrt{\frac{\pi}{8n^{3}}} + O(n^{-\frac{17}{10}})$$

以此类推，我们可以得到 $I_{n}$ 的尺度为 $n^{-\frac{1}{2}}$、$n^{-\frac{3}{2}}$、$n^{-\frac{5}{2}}, \cdots$ 的完全渐进展开。

总结

本文我们解决了沃利斯积分 $I_{n} = \int^{\frac{\pi}{2}}_{-\frac{\pi}{2}}(\cos x)^{n}\mathrm{d}x, n\rightarrow\infty$ 的渐近估阶问题。解决过程可以推广到被积函数在幂上有一个大参数 n 这一大类情形，解决这一大类情形的方法称其为拉普拉斯方法，步骤如下：

(1) 忽略尾部：估计原积分的尾部并忽略
(2) 中心逼近：在中心区域进行逼近并得到误差界
(3) 完成尾部：将尾部的积分范围加到中心区域的逼近中

对中心区域和尾部的分割点的选取，依赖于对被积函数的分段估计。因此本文首先详细地讨论了为什么要进行分段估计的问题，主要涉及到带大 O 余项的泰勒展开的成立条件，含参变量的大 O 符号这两方面。

在解决过程中，基于对被积函数的分析，发现尾部的误差是指数级的小量，另一方面，由分段估计解决掉对中心区域的逼近，其逼近误差是一个大于指数级（多项式级）的小量，因此合起来后的误差是多项式级的小量。也就是最终结果：

$$I_{n} = \int^{\frac{\pi}{2}}_{-\frac{\pi}{2}}(\cos x)^{n}\mathrm{d}x = \sqrt{\frac{2\pi}{n}} + O(n^{-\frac{3}{5}})$$

通过这个例子，我们有了拉普拉斯方法的思想和流程，在下一篇文章中，应用拉普拉斯方法，我们终于可以推导出之前在算法分析的很多例子中都用到过的拉马努金 Q 函数的渐近估阶。

---