求和和渐近符号的介绍。

调和级数

一些木块通过堆叠能超出桌子多长？一种处理方法是贪心法，从最上方开始，移动直到不能移动为止。

记末状态第 $k$块距离桌子边缘的距离为$r_k$，贪心下上面$k-1$块质心应该恰好在第$k$ 块的边缘。$c_k=r_{k+1}$ 。那么利用质心的定义，有：

$$ c_k=\frac{(k-1)c_{k-1}+1\cdot (r_k-\frac{1}{2})}{k} $$

代入 $c_k=r_{k+1}$ 得到：

$$ r_{k+1}=r_k-\frac{1}{2k} $$

也就是说第 $k$块比第$k+1$块多了$\frac{1}{2k}$。那么利用$r_{n+1}=0$ 就有：

$$ r_1=\sum_{i=1}^n \frac{1}{2i} $$

实际上，求和

$$ H_n=\sum_{i=1}^n \frac{1}{i} $$

被称为调和级数。他是发散的，因为 $\frac{1}{i}$从$k$加到$2k$一定大于$\frac{1}{2}$。 如果注意力涣散注意不到这一点，我们可以使用积分估计。由于$f(1)=1,f(n)=\frac{1}{n}$ ，并计算

$$ \int_1^n \frac{dx}{x}dx=ln(n) $$

那么就得到

$$ \frac{1}{n}+ln(n)\leq H_n\leq 1+ln(n) $$

也就是说，$H_n\sim ln(n)$，这也给出了$H_n$ 发散的证据。同时，他们的差是收敛的，也就是欧拉常数：

$$ \gamma = \lim_{n \to \infty} \left( \sum_{k=1}^{n} \frac{1}{k} - \ln(n) \right) $$

阶乘

我们熟知的

$$ n!=\prod_{i=1}^ni $$

并不能很好地看出 $n!$ 有多大，一种简单的想法是取对数得到

$$ ln(n!)=\sum_{i+1}^nln(i) $$

然后我们运用积分估计，$f(x)=ln(x)$ ，计算

$$ \int_1^nlnxdx=(xln(x)-x)\bigg|_1^n=nln(n)-n+1 $$

那么就是

$$ nln(n)-n+1\leq ln(n!)\leq ln(n)+nln(n)-n+1 $$

还原成阶乘就得到

$$ \frac{n^n}{e^{n-1}}\leq n!\leq \frac{n^{n+1}}{e^{n-1}} $$

这就清楚多了。但实际上可以更加精确。

斯特林公式(Stirling’s Formula)

$$ n!=(\frac{n}{e})^n\cdot \sqrt{2\pi n}\cdot e^{\epsilon(n)} $$

其中 $\frac{1}{12n+1}\leq \epsilon(n)\leq \frac{1}{12n}$，从而$n$较大的时候$e^{\epsilon(n)}$ 几乎可以忽略。那么就有

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

渐近记号

我们已经熟悉了

波浪号(tilde)

$$ f(x)\sim g(x)\ \ \text{if } \lim_{x\to \infty} \frac{f(x)}{g(x)}=1 $$

大 $O$ 记号

$$ f(x)=O(g(x))\ \ \text{ if} \lim_{x\to \infty}|\frac{f(x)}{g(x)}|<\alpha \ \ \text{(finite)} $$

就是说 $f(x)$增长得没有$g(x)$快。记号可能是$f(x)\leq O(g(x))$(但不会写大于)或者$f(x)\ \text{is } O(g(x))$或者$f(x)\in O(g(x))$ 。要证明，只要考虑比值极限是否有限即可。

例如， $10^i x^2=O(x^2)$ ，$x^i=O(e^x)$ ，$10=O(1)$，其中$i$ 是常数。

$\Omega$ 记号

$$ f(x)=\Omega (g(x))\ \ \text{ if} \lim_{x\to \infty}|\frac{f(x)}{g(x)}|>0 $$

与大 $O$对应，表示了增长的下界。所以对应的可以说$f(x)\geq \Omega(g(x))$ 。
Thm : $f(x)=O(g(x)) \text{ 当且仅当 } g(x)=\Omega(f(x))$ .

$\Theta$记号$f(x)=\Theta(g(x))$如果既有$O$又有$\Omega$，也就是比值的极限大于$0$ 而且有限。

$$ \begin{aligned} \text{总结: } & \text{忽略常数，可以简单类比：} \\ O & \text{ means } \le \\ \Omega & \text{ means } \ge \\ \Theta & \text{ means } = \end{aligned} $$

那么自然就会想到还有小于号和大于号。对应就是 $o$和$\omega$ 。

$o$ 记号

$$ f(x)=o(g(x))\ \ \text{if } \frac{f(x)}{g(x)}=0 $$

$\omega$ 记号

$$ f(x)=\omega(g(x))\ \ \text{if } \frac{f(x)}{g(x)}=\infty $$

一个神秘的证明：

设 $f(n)=\sum_{i=1}^n i$，那么$f(n)=O(n)$ 。

[!证明]
利用归纳法。
归纳假设为 $P(n): f(n)=O(n)$ 。

奠基步：$f(1)=O(1)$ 显然成立。

归纳步：假设 $P(k)$ 成立，$f(k+1)=f(k)+k+1=O(n)+O(n)=O(n)$
从而由归纳公理，命题成立。

归纳假设假定了 $n$ ，这实际上是不合理的。

所以尽量不要在归纳法中运用渐近记号。