算法分析与设计.ppt

《算法分析与设计.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、算法分析与设计郭彦宏2005年改1算法和数据结构程序=算法+数据结构软件：刻画现实世界，解决现实世界中的问题语言：实现的工具算法：解的描述（程序的灵魂）数据结构：现实世界的数据模型程序=算法+数据结构2算法设计与分析算法定义为了完成特定任务指令的有穷序列好的算法的特性确定性有穷性可行性健壮性输入、效率和存储要求输出3算法设计与分析算法的复杂度与评价时间与空间方法:1、事后分析2、事前分析4算法设计与分析几个例子（问题）表达式解释6+5*4=？字符串匹配串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位置上排序一个序列，如何最快地对其进行排序压缩编码AAAABBBC

2、DDE?图的最短路径地理研究中的交通网络5算法设计与分析A[1…10]={1,3,5,6,7,10,22,27,34,56}在A中搜索x＝22例1.16算法设计与分析算法1.1Linearsearchj←1While（jintMax(Ta[],intn){//寻找a[0:n-1]中的最大元素intpos=0;for(inti=1;i

3、8算法设计与分析算法1.2binarysearchlow←1;high←n;j←0while(low≤high)and(j=0)mid←(low+high)/2ifx=A[mid]thenj←midelseifx

4、5,46,47]1,4,11算法设计与分析Comment:B[[p…r]s←p;t←q+1;k←pwhiles≤qandt≤rifA[s]≤A[t]thenB[k]←A[s]s←s+1elseB[k]←A[t]t←t+1endifk←k+1endwhileifs=q+1thenB[k…r]←A[[t…r]elseB[k…r]←A[s…q]endifA[p…r]←B[p…r]12算法设计与分析template//(C语言）voidMerge(Tc[],Td[],intl,intm,intr){//把c[l:m]和c[m:r]归并到d[l:r];.inti=l,j=

5、m+1,k=l;while((i<=m)&&(j<=r))if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q];elsefor(intq=i;q<=m;q++)d[k++]=c[q];}13算法设计与分析选择排序fori←1ton-1k←iforj←i+1tonifA[j]//(C语言）voidSelectionSort(Ta[],intn){//及

6、时终止的选择排序boolsorted=false;for(intsize=n;!sorted&&(size>1);size--){intpos=0;sorted=true;//找最大元素for(inti=1;i

7、元素分别向右移动一个位置。对于本例，需要移动11,9,8和6，并把4插入到新空出来的位置a[2]中。16算法设计与分析插入排序fori←2tonx←A[i]j←i-1while(j>0)and(A[j]>x)A[j+1]←A[j]j←j-1endwhileA[j+1]←xendfor17算法设计与分析templatevoidInsert(Ta[],intn,constT&x){//向有序数组a[0:n-1]中插入元素xinti;for(i=n-1;i>=0&&x