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$,我们有

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

因此

2.Bounding

此题是讨论

成立的条件。

成立:

此时

所以

不成立:

此时

所以

3.In Between Functions

不成立。

那么

答案例子(供参考):

4.Recurrence Relation Practice

回顾主定理:

如果

那么

(a)

此时

所以

(b)

如果$c = 1$,那么

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

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

如果$c > 1$,那么

(c)

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

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

所以

//