一、算法分析的数学基础
1、几类重要的函数的阶
- 阶的高低至少指数级： 2n, 3n, n!, …
- 注意阶乘至少是指数级
- 多项式级： n, n2, nlogn, n1/2, …
- 对数多项式级： logn, log2n, loglogn, …
2、对数函数的一些性质
有关性质(1)的证明
有关性质(2)(3)的证明
性质二的证明在性质一的基础上使用了有关函数渐近的界的定理产生的重要结论：对数函数的阶<幂函数的阶<指数函数的阶
性质三的证明则是两边都进行 logb运算
3、指数函数与阶乘
阶乘比nn增长慢，比一般的指数函数增长块，且其去对数后是一个多项式同阶的，证明如下：
斯特林公式的应用：
4、取整函数的性质
二、算法分析的一些数学方法
1、序列求和或者估计和
(1)一些级数求和公式
求和过程中还有一些如拆项、变限等方法需要灵活运用
例如：
(2)估计和式上界的放大法
例如：
(3)用积分做和式的渐近的界
就是灵活运用积分，例如：
2、递推方程的求解
设序列 a0, a1, … , an, … , 简记为 { an },一个把 an与某些个 ai ( i < n ) 联系起来的等式叫做关于序列 { an } 的递推方程
例如：Fibonacci数
递推方程：f(n)=f(n-1)+f(n-2)
初值：f(0)=1, f(1)=1
(1)迭代法求解
迭代法求解：不断用递推方程的右部替换左部，直到出现初值停止迭代，将初值代入并对和式求和，可用数学归纳法验证解的正确性
例如：
对于某些递推方程，直接迭代比较困难，可以尝试对递推方程和初值进行换元，然后求和，求和后进行相反换元，得到原始递推方程的解
例如：
解的正确性-归纳验证：
(2)差消法求解
对于高阶递推方程先要用差消法化简为一阶方程，再迭代求解
例如：
最后迭代求解:
(3)递归树
递归树是迭代的图形表述,递归树的生成过程与迭代过程一致。*递归树上所有项恰好是迭代之后产
生和式中的项.对递归树上的项求和就是迭代后方程的解. *
生成方法：
应用实例:
3、求解递推方程的主定理及其应用
主定理：
通过递归树这一个视角解释主定理的含义：
- 最后一行的alogbn通过对数转换成nlogba
一个Tn这样形式的式子，通过递归树的计算，得到了叶子节点耗费的计算量和各层根节点之和耗费的计算量，两者加起来就是Tn的计算量。而主定理，就是判断这两部分以那部分为主。
- 情况1：表示f(n)的阶比第一部分的阶小，以第一部分为主，由于是多项式阶上的差距，所以第二部分直接忽略
- 情况2：表示f(n)的阶和第一部分等阶，由于有logbn+1层，加和后经过换底公式得到结果
- 情况3：表示f(n)的阶比第一部分大，以第二部分为主，而再加上第二个约束条件，①是保证了根节点一定大于下一层节点计算代价之和。af(n/b)/f(n)<c,c<1所以分母大于分子，再从递归树中就很明显得出结果②是保证级数收敛，是正则条件。这样就得到以f(n)的阶为主
注意：logn不是一个多项式阶ne所以情况1哪怕是logn的加和也不会在多项式上超过第一部分的阶
拓展形式：
应用：
不能使用主定理时，可考虑使用递归树求解。
