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$,下式成立

所以第一个结论成立,另一方面:

当$N=10$时,绝对误差和相对误差为:

当$N=100$时,绝对误差和相对误差为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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}$

解:

利用

可得选择