文档介绍：第1章算法分析基本概念
上海第二工业大学温敬和
******@it.
2008年3月11日
1
引言
历史背景
二分搜索
合并二个已排序的表
选择排序
插入排序
自底向上合并排序
时间复杂性
空间复杂性
最优算法
~ 如何估计算法运行时间...…(略)
2
引言
Donald
计算机科学就是
算法研究
例,编译程序和操作系统是具有特定目标的算法的直接实现。
3
算法(Algorithm)
解题方案的准确完整的描述,是在有限步骤内求解某一问题所使用的一组定义明确的规则。
①无论是解题思路还是编写程序,都是在实施某种算法。前者是推理实现,后者是操作实现。
②算法不是程序,但算法是用程序或程序伪代码来描述的。
4
算法分析(Algorithm Analysis)
算法分析是研究算法一旦转换成某种语言的程序,该程序在计算机上运行需要多少时间和存储空间,才能完成解题方案。
确定一个程序的运行效率,可使用数学分析方法,也可使用实验测试方法,以期在理论和实践作出评价。
5
历史背景
20世纪早期,能否用一种有效的过程(算法)来求解问题受到广泛关注,人们的注意力是放在问题的可解和不可解的分类上。
问题的可判定性和可解性的研究领域称为“可计算理论”。
数字计算机出现以后,由于有限的资源,提出了尽可能少用资源的有效算法的需求,导致出现计算复杂性的新领域。
“计算复杂性”是研究可解类问题的效率,所谓效率是指解决问题所需的时间和空间。
6
二分搜索
㈠顺序搜索(线性搜索)
问题:设A[1..n]为一个n个元素(整数)的数组,判定给定元素x是否在A中。
算法:扫描A的所有项目,将每个项目与x比较,如果在第j次比较后(1≤j≤n)搜索成功,即x=A[j],则返回j值;否则返回0,表示没有找到。这种方法称为顺序搜索。
7
LinearSearch(Page 3)
输入:n个元素的数组A[1..n]和元素x。
输出:如果x=A[j],1≤j≤n,则输出 j,否则输出0。
1. j←1
2. while (j<n) and (x≠A[j])
3. j ←j+1
4. end while
5. if (x=A[j]) then return j else return 0
出循环分析:
①x=A[j],此时j<n 。
②j等于n,但A[n]与x尚未比较。
1. j←1
while (j≤n)
if (x=A[j]) then return j
j←j+1
5. end while
return 0
8
㈡顺序搜索法分析
最少比较次数为1,最多比较次数为n 。
㈢二分搜索
令A[low..high]为元素按升序排列的非空数组,数A[mid] 为中间元素。假定x>A[mid],如果x在A中,则它必定是
A[mid+1],A[mid+2],…,A[high]
中的一个,接下来只需在A[mid+1..high]中搜索x。换句话说,A[low..mid]中的项目在后续比较中被掉弃了。类似地,如果x<A[mid],只需在A[low..mid-1]中搜索x。由于重复进行二等分,导致了一个称为二分搜索的有效策略。
9
BinarySearch(Page 4)
输入:n个元素的数组A[1..n](按升序排列)和元素x。
输出:如果x=A[j],1≤j≤n,则输出 j,否则输出0。
1. low←1 : high←n : j←0
2. while (low≤high) and (j = 0)
3. mid←(low+high)/2//取整
4. if (x=A[mid]) then j←mid
else if (x<A[mid]) then high←mid-1
6. else low←mid+1 //x>A[mid]
7. end while
8. return j
10