算法分析與設(shè)計(jì).ppt

《算法分析與設(shè)計(jì).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、算法分析與設(shè)計(jì)郭彥宏2005年改1算法和數(shù)據(jù)結(jié)構(gòu)程序=算法+數(shù)據(jù)結(jié)構(gòu)軟件：刻畫現(xiàn)實(shí)世界，解決現(xiàn)實(shí)世界中的問題語言：實(shí)現(xiàn)的工具算法：解的描述（程序的靈魂）數(shù)據(jù)結(jié)構(gòu)：現(xiàn)實(shí)世界的數(shù)據(jù)模型程序=算法+數(shù)據(jù)結(jié)構(gòu)2算法設(shè)計(jì)與分析算法定義為了完成特定任務(wù)指令的有窮序列好的算法的特性確定性有窮性可行性健壯性輸入、效率和存儲(chǔ)要求輸出3算法設(shè)計(jì)與分析算法的復(fù)雜度與評價(jià)時(shí)間與空間方法:1、事后分析2、事前分析4算法設(shè)計(jì)與分析幾個(gè)例子（問題）表達(dá)式解釋6+5*4=？字符串匹配串“ABCAC”出現(xiàn)在另一個(gè)串“ABCABCACAC”的第幾個(gè)位置上排序一個(gè)序列，如何最快地對其進(jìn)行排序壓縮編碼AAAABBBC

2、DDE??圖的最短路徑地理研究中的交通網(wǎng)絡(luò)5算法設(shè)計(jì)與分析A[1…10]={1,3,5,6,7,10,22,27,34,56}在A中搜索x＝22例1.16算法設(shè)計(jì)與分析算法1.1Linearsearchj←1While（jintMax(Ta[],intn){//尋找a[0:n-1]中的最大元素intpos=0;for(inti=1;i

3、8算法設(shè)計(jì)與分析算法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算法設(shè)計(jì)與分析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算法設(shè)計(jì)與分析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算法設(shè)計(jì)與分析選擇排序fori←1ton-1k←iforj←i+1tonifA[j]//(C語言）voidSelectionSort(Ta[],intn){//及

6、時(shí)終止的選擇排序boolsorted=false;for(intsize=n;!sorted&&(size>1);size--){intpos=0;sorted=true;//找最大元素for(inti=1;i

7、元素分別向右移動(dòng)一個(gè)位置。對于本例，需要移動(dòng)11,9,8和6，并把4插入到新空出來的位置a[2]中。16算法設(shè)計(jì)與分析插入排序fori←2tonx←A[i]j←i-1while(j>0)and(A[j]>x)A[j+1]←A[j]j←j-1endwhileA[j+1]←xendfor17算法設(shè)計(jì)與分析templatevoidInsert(Ta[],intn,constT&x){//向有序數(shù)組a[0:n-1]中插入元素xinti;for(i=n-1;i>=0&&x