文档介绍：计算机算法导论---算法选讲
南开大学信息技术科学学院
杨巨峰
Webster词典
算法即在有限步骤内解一个数学问题的过程,步骤中常常包括某一操作的重复。更广义地说,一个算法就是为解一个问题或实现某一目标的逐步过程
算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。此外,他还应具有如下五个重要特性
有穷性
确定性
输入
输出
能行性
《计算机程序设计艺术》
2
什么是算法
算法评估与分析
MAXMIN问题
排序问题
字符串匹配
3
主要内容
4
1 算法评估与分析
正确性
原则上应该证明算法对于任意合理的输入都正确
实际中常用推理法证明
时间代价
必须抛弃的评价指标
算法运行的实际执行时间
运行过程中所执行的指令条数
运行过程中程序循环的次数
空间代价
最优性
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的最坏情形时间复杂度和最好情形时间复杂度定义如下
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;
}
A[j+1]=V;
return;
}
}
10
示例
1 2 3 4 5 6 7 8 9 10 9次比较
10 9 8 7 6 5 4 3 2 1 45次比较
3 7 4 5 10 2 9 6 1 8 ?次比较