算法分析框架
-
基本操作
：
它通常是算法最内层循环中最费时的操作
。四则运算中:加、减、乘、除。其中最耗时的操作是除法，其次是乘法，最后是加法和减法。 -
问题规模
：排序:数组中元素个数n.
检索:被检索数组的元素个数n.
矩阵相乘:矩阵的行列数i,j,k.
图的遍历:图的顶点数n,边数m -
稳定性
：如果一个
排序算法保留了等值元素在输入中的相
对顺序，就可以说它是
稳定
的(stable)。换句话说，如果一个输入列表包含两个相等的元素，它们的位置分别是i和j，i<j, 而在排好序的列表中，它们的位置分别为i’和j’,那么i'<j’肯定就是成立的。一
般来说，将相隔很远的键交换位置的算法虽然不稳定，但往往速度
很快。 -
在位
：对于排序算法来说，第二个值得注意的特性是算法需要的
额外存储空间（如数组）
。如果一个算法不需要额外的存储空间(除了个别存储单元以外)，我们就说它是在位的(in-place)。重要的排序算法有些是在位的，有些则不是。
基本算法效率类型
| 类型 | 名称 | 注释 |
|---|---|---|
| 1 | 常量 | 为数很少的效率最高的算法，很难举出几个合适的例子，因为典型情况下，当输入的规模变得无穷大时，算法的运行时间也会趋向于无穷大 |
| log n | 对数 | 一般来说, 算法的每一次循环都会消去问题规模的一个常数因子。注意，一个对数算法不可能关注它的输入的每一个部分(哪怕是输入的一个固定部分):任何能做到这一点的算法最起码拥有线性运行时间 |
| n | 线性 | 扫描规模为n的列表(例如，顺序查找)的算法属于这个类型 |
| n logn | 线性对数 | 许多分治算法,包括合并排序和快速排序的平均效率，都属于这个类型 |
| n^2 | 平方 | 一般来说，这是包含两重嵌套循环的算法的典型效率。基本排序算法和n阶方阵的某些特定操作都是标准的例子 |
| n^3 | 立方 | 一般来说，这是包含三重嵌套循环的算法的典型效率。线性代数中的一些著名的算法属于这一类型 |
| 2^n | 指数 | 求n个元素集合的所有子集的算法是这种类型的典型例子。“指数” 这个术语常常被用在一个更广的层面上，不仅包括这种类型，还包括那些增长速度更快的类型 |
| n! | 阶乘 | 求n个元素集合的完全排列的算法是这种类型的典型例子 |
递归算法效率分析
分析递归算法时间效率的通用方案
(1)决定用哪个(哪些)参数作为输入规模的度量标准。
(2)找出算法的基本操作。
(3)检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。如果有这种可能，则必须对最差效率、平均效率以及最优效率做单独研究。
(4)对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。
(5)解这个递推式，或者至少确定它的解的增长次数。
非递归算法效率分析
分析非递归算法效率的通用方案.
(1)决定用哪个(哪些)参 数表示输入规模。
(2)找出算法的基本操作(作为-一个规律，它总是位于算法的最内层循环中)。
(3)检查基本操作的执行次数是否只依赖于输入规模。如果它还依赖于一些其他的特性，则最差效率、平均效率以及最优效率(如有必要)需要分别研究。
(4)建立一个算法基本操作执行次数的求和表达式。
(5)利用求和运算的标准 公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。
∑
例子：
算法MaxElement(A[..n- 1])
//求给定数组中最大元素的值
//输入:实数数组A{0..n- 1]
//输出: A中最大元素的值
maxval←A[O]
for i←1 to n-1 do
if A[i] > maxval
maxval←A[I]
return maxval
此时输入规模为n,循环体中有赋值和比较两种操作，由于比较每次都会执行，赋值并不是，所以基本操作为比较。
把C(n)记作比较运算的执行次数，则有求和表达式 C(n)=
= n-1 = Θ(n)
算法的数学基础
-
几类重要的函数
1、至少指数级： 2n, 3n, n!, …
2、多项式级： n, n2, nlogn, n1/2, …
3、对数多项式级： logn, log2n, loglogn, …
4、对数函数：logn= log2 n
logkn = (logn)k
loglogn= log(logn)
性质：
(1) log2n = Θ (logln)
(2) logbn = o(n^α )α > 0
(3) a^logb n= n^logb a
5、指数函数与阶乘
stirling公式 n! = (2πn)^1/2 (n/e)^n(1+Θ(1/n))
n! = o(n^n)
n! = ω(2^n)
log(n!) = Θ(nlogn)
log(n!) = Ω(nlogn)
-
序列求和的方法
-
迭代法求解递推方程
- 不断用递推方程的右部替换左部迭代法
- 直到出现初值停止迭代
- 每次替换，随着 n 的降低在和式中多出一项
- 将初值代入并对和式求和
- 可用数学归纳法验证解的正确性
-
差消法化简递推方程
-
递归树
