CS170 Efficient Algorithms and Intractable Problems Section0

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

最近规划复习算法分析的内容，主要材料是UCB的CS170，斯坦福的算法课程以及《算法概论》，这部分总结CS170相关内容，视频选择是fa20，作业选择的是fa18。

这次回顾Section 0。

1.Asymptotic Bound Practice

证明：

$\forall \epsilon > 0$，我们有

$$\begin{aligned} \lim_{x\to \infty} \frac{\log x}{x^{\epsilon}} &= \lim_{x\to \infty} \frac{(\log x)'}{(x^{\epsilon})'}\\ &= \lim_{x\to \infty} \frac{1/x}{\epsilon x^{\epsilon -1}}\\ &=\frac 1 {\epsilon} \lim_{x\to \infty} \frac 1 {x^\epsilon} \\ &=0 \end{aligned}$$

所以存在$x_0 > 0$，以及$c >0 $，使得当$x> x_0$时，

$$\frac{\log x}{x^{\epsilon}} \le c \Leftrightarrow \log x \le c x^{\epsilon}$$

因此

$$\log x \in O\left(x^{\epsilon}\right)$$

2.Bounding

此题是讨论

$$\sum_{i=1}^{n} f(i) \in \Theta(f(n))$$

成立的条件。

成立：

取

$$f_1(x) = 2^x$$

此时

$$\begin{aligned} \sum_{i=1}^{n} f_1(i) &= \sum_{i=1}^{n} 2^i\\ &= 2^{n+1} - 1\\ f_1(n)& =2^n \end{aligned}$$

所以

$$\sum_{i=1}^{n} f_1(i)\in \Theta(f_1(n))$$

不成立：

取

$$f_2(x) = x$$

此时

$$\begin{aligned} \sum_{i=1}^{n} f_2(i) &= \sum_{i=1}^{n} i\\ &= \frac{n(n+1)}{2}\\ f_2(n)& =n \end{aligned}$$

所以

$$\sum_{i=1}^{n} f_2(i)\not \in \Theta(f_2(n))$$

3.In Between Functions

不成立。

取

$$\begin{aligned} f(n) &=n^5 \sin (2\pi n) + 2^n \cos (2\pi n)\\ &=\begin{cases} 2^n& n= 2k\\ n^5 & n= 2k+1 \end{cases} \end{aligned}$$

那么

$$f(n) \not \in O(n^c)且f(n) \not \in \Omega(\alpha ^n)$$

答案例子（供参考）：

$$f(n)=2^{\sqrt n}$$

4.Recurrence Relation Practice

回顾主定理：

如果

$$T(n) = aT\left(\frac n b \right) + \Theta(n^d)$$

那么

$$T(n)=\begin{cases} \Theta(n^d), &a<b^d\\ \Theta(n^d\log n), &a=b^d\\ \Theta(n^{\log_b a }), & a>b^d \end{cases}$$

(a)

$$T(n)=2 \cdot T\left(\frac{n}{2}\right)+\sqrt{n}$$

此时

$$\begin{aligned} a& = 2\\ b&= 2\\ d&= \frac 1 2\\ 1=\log_b a & > d =\frac 12 \end{aligned}$$

所以

$$T(n)=\Theta(n)$$

(b)

$$T(n)=T(n-1)+c^{n}$$

如果$c = 1$，那么

$$T(n) =T(0) + n \Rightarrow T(n) = \Theta(n)$$

如果$c\neq 1$，递推可得

$$\begin{aligned} T(n) &= T(0) + \sum_{i=1}^n (T(i) - T(i - 1))\\ &= T(0) + \sum_{i=1}^n c^i\\ &= T(0) + \frac{c(c^n - 1)}{c - 1} \end{aligned}$$

如果$0< c < 1$，那么

$$\begin{aligned} T(n) &= T(0) + \frac{c(c^n - 1)}{c - 1}\\ &=T(0) + \frac{c(1-c^n)}{1-c}\\ &\le T(0) + \frac c {1- c}\\ &\ge T(0)\\ T(n)&= \Theta(1) \end{aligned}$$

如果$c > 1$，那么

$$\begin{aligned} T(n) &= T(0) + \frac{c(c^n - 1)}{c - 1}\\ T(n)&= \Theta(c^n) \end{aligned}$$

(c)

使用递归树的方法，在第$i$层中，有$2^i$个节点，每个节点的时间复杂度为$3$，所以第$i$层的时间复杂度为$3\times 2^i$，注意第$i$层的规模为$n^{\frac {1}{2^i}}$，令

$$\begin{aligned} n^{\frac 1 {2^i }}&= 2\\ \frac 1 {2^i } & = \log_n 2\\ i&=\log_2 \log_2 n \end{aligned}$$

从而层数为$\log_2 \log_2 n$，总时间复杂度为

$$\begin{aligned} 3\sum_{i=1}^{\log_2 \log_2 n} 2^i &= 3 \left( 2^{\log_2 \log_2 n + 1} -1\right)\\ &=3\left(2 \log_2 n - 1 \right) \end{aligned}$$

所以

$$T(n)=\Theta(\log n)$$