【算法】算法的数学基础

1.函数的阶

$\Theta$为同阶函数，即：
$$
\Theta(g(n))={f(n)|\exists c_1,c_2>0,n_0,\forall n>n_0,c_1g(n)\leq f(n)\leq c_2g(n)}
$$
举个例子，
$$
\frac{1}{2}n^2-3n=\Theta(n^2)\
6n^3\neq \Theta(n^2)
$$
$O$为低阶函数，即：
$$
O(g(n))={f(n)|\exists c>0,n_0,\forall n>n_0,0\leq f(n)\leq cg(n)}
$$
几何上来看，就是超过一个常数时，$f(n)$不会超过$cg(n)$。

$\Omega$为高阶函数。

2.递归方程及其解法

什么是递归方程呢？由自身定义自身的方程。

举个例子：
$$
T(n)=T(\frac{n}{2})+3
$$
就是一个递推方程。值得一提的解法有两种：迭代法、$Master$定理法

迭代法

很简单，就是把递归方程循环地展开，把递归式转化为和式，根据级数关系求解，举个例子：

$Master$定理法