本文由mysky_2012贡献
南开大学信息技术科学学院
杨巨峰
Webster词典
? 算法即在有限步骤内解一个数学问题的过程，步骤中常常包括某一操作的重复。更广义地说，一个算法就是为解一个问题或实现某一目标的逐步过程
D.E.Knuth
? 算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。此外，他还应具有如下五个重要特性
有穷性确定性输入输出能行性《计算机程序设计艺术》
2
1. 2. 3. 4.
算法评估与分析 MAXMIN问题排序问题字符串匹配
3
4
正确性
? 原则上应该证明算法对于任意合理的输入都正确 ? 实际中常用推理法证明
时间代价
? 必须抛弃的评价指标
算法运行的实际执行时间运行过程中所执行的指令条数运行过程中程序循环的次数
空间代价最优性
5
是指算法运行中起主要作用且花费最多时间的操作
? 两个实数矩阵的乘法问题中，矩阵的实数元素之间的数乘 ? 对N个整数进行排序的算法中，整数间的比较和交换
引入基本操作的概念，用其执行次数来度量算法的时间代价，是算法分析的基础
6
算法的运行时间代价除了与算法本身的基本操作数有关外，还与问题实例的长度有关，即受输入规模影响
? ? ? ? 排序问题：待排序元素序列的长度n 矩阵乘积：n阶方阵的阶数n 图问题：图的顶点数n和边数m 字符串匹配问题：文本T的长度n
T(n)
? 算法的时间复杂度，用问题实例长度的函数表示 ? 也就是用该算法用于问题长度为n的实例所需要的基本操作次数来刻画
7
如果解决问题P的算法A和算法B，其时间复杂度分别是TA(n)和TB(n)，则判断A、B性能优劣的标准是查看在n足够大时TA(n)和TB(n)的大小关系
8
对于同一算法，如果有相同的问题长度，但采用不同的输入，其时间代价一般也不同。因此在实际的算法分析中，复杂度函数值T(n)不是唯一的设Dn为问题P的所有长度为n的实例集合，输入实例I∈Dn，t(I)是用来解决问题P的算法A在以I为输入时的执行代价（基本操作数），则算法A的最坏情形时间复杂度和最好情形时间复杂度定义如下
W (n) = MAX {t ( I )}
I ∈D n
B(n) = MIN{t ( I )}
I ∈D n
一般地，T (n) = W (n)
9
InsertSort
void InsertSort(int A[], int n) { for(int i=2;i<=n;i++) { int V = A[i]; int j=i-1; while((A[j]>V)&;&;(j>0)) { A[j+1]=A[j]; j=j-1; 1 2 3 4 5 6 7 8 9 10 } 10 9 8 7 6 5 4 3 2 1 A[j+1]=V; 3 7 4 5 10 2 9 6 1 8 return; } }
9次比较 45次比较？次比较
10
许多实际问题的可能实例集是一个极大的集合，即使把问题长度限定为n，实例集Dn依然很大。其中使算法A耗费最大代价W(n)的实例往往只占很小的一部分，而大多数实例耗费的代价常常远小于W(n),因此转而使用期望复杂度或称平均情形复杂度评价算法性能
A(n) =
I ∈D n
∑ P( I )t ( I )
11
解析表达式阶表达式
? O ? ? ? θ
多项式函数和指数函数
12
形式化定义
? 称复杂度函数T(n)是O(f(n))，即T(n)=O(f(n))，如果存在常数c>0与n0，当n>n0时有T(n)<=cf(n),例如：
T1(n)=(n+1)/2=O(n) c=1,n0=1 T2(n)=3n2+4n+5=O(n2) c=10,n0=2
? T1(n)=O(n2)和T2(n)=O(n3) 也是对的
13
形式化定义
? 称复杂度函数T(n)是?(f(n))的，即T(n)=?(f(n))，如果存在常数c>0与n0，当n>n0时有T(n)>=cf(n)，例如：
T1(n)=(n+1)/2=?(n) c=0.5,n0=1 T2(n)=3n2+4n+5=?(n2) c=3,n0=1
? T1(n)=O(1)和T2(n)=O(n) 也是对的
14
形式化定义
? 称复杂度函数T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常数c1>0,c2>0与n0，当n>n0时有 c1f(n)>=T(n)>=c2f(n)，例如：
T1(n)=(n+1)/2=?(n) c1=1,c2=0.5,n0=1 T2(n)=3n2+4n+5=?(n2) c1=10,c2=3,n0=2
? 显然如果T(n)=O(f(n))而且T(n)=?(f(n))，则容易得到 T(n)=θ(f(n))
15
类型 1 logn n nlogn n2 n3 2n n!
名称常量对数线性 n-log-n 平方立方指数阶乘
说明效率最高，但是很少有算法达到算法的每一次循环都会消除问题规模的一个常数因子。一个对数算法不可能关注输入的每一个部分扫描规模为n的列表分治算法两重嵌套循环三重嵌套循环
16
下列等式哪些是正确的？哪些是错误的？
A. B. C. D. n(n+1)/2=O(n3) n(n+1)/2=O(n2) n(n+1)/2=θ(n3) n(n+1)/2=?(n)
17
18
题目
? 求n元中的最大元MAX(n)和最小元MIN(n)
学习目的
? 理解算法的评价方法 ? 体会算法设计及算法改进
19
void MAXMIN1(int L[], int n){ int MAX = L[1], j; for(int i=2;i<=n;i++){ if(MAX
算法讨论：算法讨论： 1.算法是正确的； 2.以元素之间的比较为基本操作，则求 MAX的代价是n-1，求MIN的代价是n-2 ，故总时间是2n-3 3.算法的代价只与L的长度n有关，而与L 的具体元素没有关系，故 T(n)=W(n)=A(n)=2n-3，亦可记为 T(n)=O(n)或T(n)=θ(n) 4.空间消耗除了L之外只需几个单元 S(n)=O(1) 算法思考：算法思考：从n元中求最大元用n-1次比较是最优的，从剩下的n-1元中求最小元用n-2次比较也是最优的，但是把二
