算法设计与分析之数学基础
数学是算法的基础，这一章主要讲的是如何用数学描述算法的复杂度
通常我们都知道用大O函数来描述算法的复杂度，但这一章给出了更多的概念。
同阶函数
$$
同阶函数\Theta(g(n))
$$
这个函数直观来讲就是用来处理复杂度
$$
O(2n^2) = O(n^2)
$$
定义如下：
$$
\Theta(g(n))={f(n) | \exists c1, c2>0, n0, \forall n>n0, c_1g(n)\leq f(n)\leq c_2g(n)} 称为与g(n)同阶的函数集合。
$$
记住它是用来化简系数的就好理解了
低阶函数
$$
O(g(n))
$$
这就是总所周知的大O函数，它是用来描述最坏情况的，也就是复杂度的上限。
如果
$$
f(n) = O(n^k)
$$
则称f(n)是多项式界限的，这个后面会用到
定义如下
$$
O(g(n)) = {f(n)|\exists c >0, n_0, \forall n>n_0, 0\leq f(n)\leq cg(n)}
$$
高阶函数
$$
\Omega(g(n))
$$
高阶函数和低阶函数恰恰相反，用来描述最好情况的。
定义如下：
$$
\Omega(g(n)) = {f(n)|\exists c>0, n_0, \forall n \geq n_0, 0\leq cg(n)\leq f(n)}
$$
这里有个小考点
对于描述运行时间必须完全准确
$$
– 最好运行时间是 \Omega(n)
– 最坏运行时间是 \Omega(n2)
– 或者说，运行时间是\Omega(n)
– 或者说，运行时间是O(n2)
– 但是说运行时间是\Omega(n2)则有误
$$
严格低阶函数
这个和低阶函数唯一的区别就是不可以等于上界…
符号是这个：
$$
o(g(n))
$$
严格高阶函数
这个和高阶函数唯一的区别就是不可以等于下界…
符号是这个：
$$
\omega(g(n))
$$
注意这些比较都必须满足一个条件就是f(n)是多项式界限的，比如下面这个函数就不行。
$$
n^(1+sin(n))
$$
求解复杂度/计算复杂度的常用方法
数学归纳法
$$
证明\Sigma_{k=0}n3k = O(3^k)
$$
$$
证明对于c \geq \frac{3}{2}, 存在一个n_0，当n \geq n_0的时候，\Sigma_{k=0}n3k \leq c3^n.
$$
$$
当n=0的时候，1 <= \frac{3}{2}成立。
$$
$$
先假设当n\leq m的时候成立，令n=m+1,则\Sigma_{k=0}{m+1}3k = \Sigma_{k=0}m3k + 3^{m+1} \leq c3m+3{m+1} = (\frac{c}{3}+1)3^{m+1}
$$
$$
对于(\frac{c}{3}+1)3^{m+1}，有c\geq \frac{3}{2}，则(\frac{c}{3}+1)\geq \frac{3}{2}=c，所以此时的等价于c3^{m+1}
$$
$$
所以对于n=m+1的时候假设同样成立，根据数学归纳法可以知\Sigma_{k=0}n3k = O(3^k)
$$
利用放缩法求大致值
这个求的是否准确，很看放缩的功底。
思路是切线渐进，可以回顾高中数学。
ppt上例题：
还可以通过下一项和上一项比较的方式，如果发现是单调递减的，可以知道必小于n*a0
因为求存在同阶函数，所以求阶可以大致求，不需要像高中那样求出完全相等的式子。
有些级数必须记住
求积分法锁定区间
方法原理如下：
递归方程的算法复杂度分析
这里介绍Master定理，貌似可以通杀所有计算题
$$
目的：求阶T(n)=aT(\frac{n}{b})+f(n)方程，a\geq 1, b>0是常数，f(n)是正函数
$$
$$
1.f(n)=O(n^{log_b{a-\varepsilon}})，则\exists \varepsilon>0,那么T(n) = \Theta(n^{log_ba})
$$
$$
2.f(n)=\Theta(n{log_ba})，那么T(n)=\Theta(n{log_ba}logn)
$$
$$
3.f(n)=\Omega(n^{log_ba+\varepsilon}),\exists \varepsilon>0,且对于某个常数c<1和足够大的n，有af(\frac{n}{b})\leq cf(n)，那么T(n)=\Theta(f(n))
$$
更进一步：
缺陷：
