这次回顾第四周的内容。

课程主页：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$，下式成立

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

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

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

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

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)$

解：

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}$

解：

利用

可得选择