Analysis of Algorithms Week 4

这次回顾第四周的内容。

课程主页：https://www.coursera.org/learn/analysis-of-algorithms

Exercise

4.9

If $\alpha<\beta,$ show that $\alpha^{N}$ is exponentially small relative to $\beta^{N}$. For $\beta=1.2$ and $\alpha=1.1,$ find the absolute and relative errors when $\alpha^{N}+\beta^{N}$ is approximated by $\beta^{N},$ for $N=10$ and $N=100 .$

解：因为当$N$充分大时，对于任意$M$，下式成立

$$\left(\frac{\alpha}{ \beta} \right)^N <\frac{1}{N^M}$$

所以第一个结论成立，另一方面：

当$N=10$时，绝对误差和相对误差为：

$$2.5937424601000023\\ 0.41890388788459326$$

当$N=100$时，绝对误差和相对误差为：

$$13780.61233982238\\ 0.00016639639425326973$$

def e1(alpha, N):
    return alpha ** N

def e2(alpha, beta, N):
    return (alpha / beta) ** N

alpha = 1.1
beta = 1.2

#输出
N = 10
print(e1(alpha, N))
print(e2(alpha, beta, N))

#输出
N = 100
print(e1(alpha, N))
print(e2(alpha, beta, N))

4.71

Show that $P(N)=\sum_{k \ge 0} \frac{(N-k)^{k}(N-k) !}{N !}=\sqrt{\pi N / 2}+O(1)$

解：参考P131

$$\begin{aligned} P(N) &=\sum_{k \ge 0} \frac{(N-k)^{k}(N-k) !}{N !}\\ &=\sum_{k \ge 0}\frac{(N-k)^k}{\prod_{i=0}^{k - 1}(N-i)}\\ &=\sum_{k \ge 0} \exp\left(-\ln \frac{\prod_{i=0}^{k - 1}(N-i)}{(N-k)^k}\right)\\ &=\sum_{k \ge 0} \exp\left(-\sum_{i=0}^{k - 1}\ln \frac{N-i}{N-k}\right)\\ &=\sum_{k \ge 0} \exp\left(-\sum_{i=0}^{k - 1}\ln \left( 1+\frac{k-i}{N-k}\right)\right)\\ &=\sum_{k \ge 0} \exp\left(-\sum_{j=1}^{k }\ln \left( 1+\frac{j}{N-k}\right)\right)\\ &=\sum_{k \ge 0} \exp\left(-\sum_{j=1}^{k }\frac{j}{N-k} + O\left(\frac{j^2}{(N-k)^2}\right)\right)\\ &=\sum_{k \ge 0} \exp\left(-\frac{(k+1)k}{2(N-k)} + O\left(\frac{k^3}{(N-k)^2}\right)\right)\\ &=\sum_{k \ge 0} \exp\left(-\frac{(k+1)k}{2N} \frac{1}{1-\frac{k}{N}} + O\left(\frac{k^3}{(N-k)^2}\right)\right)\\ &=\sum_{k \ge 0} \exp\left(-\frac{(k+1)k}{2N} +O\left(\frac{k^3}{N^2}\right)+ O\left(\frac{k^3}{(N-k)^2}\right)\right)\\ &= \sum_{k \ge 0} \exp\left(-\frac{k^2}{2N} \right) \exp\left(-\frac{k}{2N}+O\left(\frac{k^3}{N^2}\right)+ O\left(\frac{k^3}{(N-k)^2}\right)\right)\\ &= \sum_{k \ge 0} \exp\left(-\frac{k^2}{2N} \right) \left(1 + O\left(\frac{k}{N}\right)+O\left(\frac{k^3}{N^2}\right)\right)\\ &= \sum_{k \ge 0} \exp\left(-\frac{k^2}{2N} \right) + \exp\left(-\frac{k^2}{2N} \right)O\left(\frac{k}{N}\right)+ \exp\left(-\frac{k^2}{2N} \right)O\left(\frac{k^3}{N^2}\right)\\ &= \sum_{k \ge 0} \exp\left(-\frac{k^2}{2N} \right) + O(1)\\ &=\sqrt{N} \int_{0}^{\infty} e^{-x^{2} / 2} \mathrm{d} x+O(1)\\ &=\sqrt{\pi N / 2}+O(1) \end{aligned}$$

Problem

1

Which of the following is an asymptotic expansion of $e^{H_{N}} ?$

• $1-\frac{1}{2 N}+O\left(\frac{1}{N^{2}}\right)$
• $N+O(1)$
• $1+\frac{1}{N}+O\left(\frac{1}{N^{2}}\right)$
• $1+\frac{1}{2 N}+O\left( \frac{1}{N^{2}}\right)$
• $1-\frac{1}{N}+O\left(\frac{1}{N^{2}}\right)$

解：

$$\begin{aligned} e^{H_{N}} &= \exp\left( \ln N +\gamma + O\left(\frac 1 N \right)\right)\\ &= N + O(1) \end{aligned}$$

2

Which of the following has approximate value $1.22019 ?$

• $1.01^{10}$
• $1.05^{10}$
• $1.01^{20}$
• $1.01^{50}$
• $1.01^{100}$

解：

利用

$$\begin{aligned} (1+x)^{k}=1+k x+\left(\begin{array}{l}{k} \\ {2}\end{array}\right) x^{2}+\left(\begin{array}{l}{k} \\ {3}\end{array}\right) x^{3}+O\left(x^{4}\right) \end{aligned}$$

可得选择

$$1.01^{20}$$