算法基础知识

算法的基本概念

算法定义：算法是指解决问题的一种方法或一个过程。

基本特性：有穷性、确定性、正确性、输入输出

函数的渐近的界

渐近分析 Asymptotics

这里应该是 $f \in ω (g)$

little 符号比 big 符号更精确。

良序原理=>归纳法

斯特林公式

$n! \approx 2 πn (\frac{n}{e})^{n}$

$lim_{n \to + \infty} \frac{n !}{2 πn ( \frac{n}{e} ) ^{n}} = 1$

调和级数和二叉树

幂级数 $\sum_{i} i^{k} = O (n^{k + 1})$

主定理和等比级数

错位相减法

算法平均时间复杂度

下面这篇文章介绍的比较详细。

master 定理的证明又长又臭，我也不会证，有兴趣的同学可以看这篇文章。

注释：这里的最常见的那个符号是 $Θ$ ，不是 $O$ ，最后一点写法可能有问题。

推荐下面的视频：

油管视频链接

这位印度老师是 Udemy 的教师，评论中好评如潮。本人专门看了下屈婉玲《算法设计与分析》发现书中的这块内容也很老套，很难理解。

B站视频链接

首先将复杂度的递归式展开为树的形式；之后，计算树每层的复杂度；最后，将所有层的复杂度相加，得到T(n)的复杂度。