數(shù)據(jù)結(jié)構(gòu)-期末復(fù)習(xí)資料課件

數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)算法的時間復(fù)雜度計算方法主單鏈表要」堆棧和隊列的概念和應(yīng)用知〈串的概念和應(yīng)用識點樹的概念和應(yīng)用圖的概念和應(yīng)用查找和排序數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)1算法的時間復(fù)雜度計算方法算法滿足以下性質(zhì)(1輸入性(2)輸出性(3)有限性(4)確定性(5)可執(zhí)行性算法設(shè)計滿足以下目標(biāo):(1)正確性(2)可讀性(3)健壯性(4)高時間效率(5)高空間效率算法的時間復(fù)雜度計算方法2算法時間復(fù)雜度定義:(m=O(f(m),當(dāng)且僅當(dāng)存在正常數(shù)c和no,對所有的n(m≥n)滿足T(n)cxf(m)。T(n)為算法的基本語句執(zhí)行次數(shù),稱為時間復(fù)雜度,隨n增大與f(n)增長接近相同,級,用of(n))表示其復(fù)雜度即可稱同一個數(shù)亙常見的時間復(fù)雜度表示O(1),O(n),o(n)O(n)o(bn)ocgn算法時間復(fù)雜度定義:(m=O(f(m),當(dāng)且僅當(dāng)存在正常數(shù)c3推導(dǎo)大O階的方法:(1)用常數(shù)1取代運行時間中的所有加法常數(shù)。(2)在修改后的運行次數(shù)函數(shù)中,只保留最高階項。(3如果最高階項在且不是1,則去除與這個項相乘的常數(shù)最后得到的結(jié)果就是大0階推導(dǎo)大O階的方法:4例1求和算法,求1+2+3.499+1005050inti,sum=0,n=100;執(zhí)行了1次for(i=l;i<=n;i++執(zhí)行n+1次isum=sum+i/行m次tf(");執(zhí)行了1次該算法一共執(zhí)行了1+n+1+n+1=2n+3次在求時間復(fù)雜度的時候我們忽略頭尾循環(huán)判斷的開銷,只需要分析影響一個算法時間復(fù)雜度的主要部分即可,即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)該算法的時間復(fù)雜度為T)=O(m)稱為線性階注意:分析這類算法的復(fù)雜度關(guān)鍵是分析循環(huán)結(jié)構(gòu)的運行情況例1求和算法,求1+2+3.499+10050505例2求和算法,求1+2+3.+99+1005050intsum=0.ne100行了1次sum=(1+n)*n/2執(zhí)行1次printf(od",sum);執(zhí)行了1次該算法一共執(zhí)行了1+1+1=3次在求時間復(fù)雜度的時候只需要分析影響一個算法時間復(fù)雜度的主要部分即可,即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)該算法的時間復(fù)雜度為T(m)=O(1)稱為常數(shù)階注意:不管這個常數(shù)是多少,我們都記做O(①),而不是O(3)例2求和算法,求1+2+3.+99+10050506例3求和算法,求1+2+3.+99+100+inti,j,X=0,sum=0,n=100/執(zhí)行了1次for(i=l;i<=n;i++ifor(j=l;j<=n;j++X++/執(zhí)行mn次sum=sum+x;)printf(%d”,sum);執(zhí)行了1次在求時間復(fù)雜度的時候我們忽略頭尾循環(huán)判斷的開銷,只需要分析影響一個算法時間復(fù)雜度的主要部分即可,即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)該算法的時間復(fù)雜度為T(n)=O(m2)稱為平方階注意:循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)的次數(shù)例3求和算法,求1+2+3.+99+100+7例1-3設(shè)數(shù)組a和b在前邊部分已賦值,求如下兩個n階矩陣相乘運算算法的時間復(fù)雜度for(i=0;k<n;i++)for(j=0;j<n;j++)ici]j1=0;∥基本語句1for(k=0;k<n;k++)c[ij}=c[ij]+a[ik]b[kljl;〃基本語句2該算法的時間復(fù)雜度為T(n)=O(n3)例1-3設(shè)數(shù)組a和b在前邊部分已賦值,求如下兩個n階矩8例14設(shè)n為如下算法處理的數(shù)據(jù)個數(shù),求如下算法的時間復(fù)雜度。for(i=l;i<=n:i=21)printf(i=%dm”,i);解設(shè)基本語句的執(zhí)行次數(shù)為T(m有≤n,即有T(m)sb所以該算法的時間復(fù)雜度為Tn)=O(bn)。稱為對數(shù)階例14設(shè)n為如下算法處理的數(shù)據(jù)個數(shù),求如下算法的9例1-5:下邊的算法是用冒泡排序法對數(shù)字α中的n個整數(shù)類型的數(shù)據(jù)元素(a[0J-a{n-1),從小到大進(jìn)行排序,求該算法的時間復(fù)雜度。voidBubblesort(intall,intn)inti,j,flag=l;inttempfor(i=l;i<n&&flag==l;i++)flag=0for(=0;j<n-i;j++)if(a[j]alj+lDiflag=l;temp=aljl:alj=a[j+1];alj+l=temp;例1-5:下邊的算法是用冒泡排序法對數(shù)字α中的n個整數(shù)10數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件11數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件12數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件13數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件14數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件15數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件16數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件17數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件18數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件19數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件20數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件21數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件22數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件23數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件24數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件25數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件26數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件27數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件28數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件29數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件30數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件31數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件32數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件33數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件34數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件35數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件36數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件37數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件38數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件39數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件40數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件41數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件42數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件43數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件44數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件45數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件46數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件47數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件48數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件49數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件50數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件51數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件52數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件53數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件54數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件55數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件56數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件57數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件58數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件59數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件60數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件61數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件62數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件63數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件64數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件65數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)算法的時間復(fù)雜度計算方法主單鏈表要」堆棧和隊列的概念和應(yīng)用知〈串的概念和應(yīng)用識點樹的概念和應(yīng)用圖的概念和應(yīng)用查找和排序數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)66算法的時間復(fù)雜度計算方法算法滿足以下性質(zhì)(1輸入性(2)輸出性(3)有限性(4)確定性(5)可執(zhí)行性算法設(shè)計滿足以下目標(biāo):(1)正確性(2)可讀性(3)健壯性(4)高時間效率(5)高空間效率算法的時間復(fù)雜度計算方法67算法時間復(fù)雜度定義:(m=O(f(m),當(dāng)且僅當(dāng)存在正常數(shù)c和no,對所有的n(m≥n)滿足T(n)cxf(m)。T(n)為算法的基本語句執(zhí)行次數(shù),稱為時間復(fù)雜度,隨n增大與f(n)增長接近相同,級,用of(n))表示其復(fù)雜度即可稱同一個數(shù)亙常見的時間復(fù)雜度表示O(1),O(n),o(n)O(n)o(bn)ocgn算法時間復(fù)雜度定義:(m=O(f(m),當(dāng)且僅當(dāng)存在正常數(shù)c68推導(dǎo)大O階的方法:(1)用常數(shù)1取代運行時間中的所有加法常數(shù)。(2)在修改后的運行次數(shù)函數(shù)中,只保留最高階項。(3如果最高階項在且不是1,則去除與這個項相乘的常數(shù)最后得到的結(jié)果就是大0階推導(dǎo)大O階的方法:69例1求和算法,求1+2+3.499+1005050inti,sum=0,n=100;執(zhí)行了1次for(i=l;i<=n;i++執(zhí)行n+1次isum=sum+i/行m次tf(");執(zhí)行了1次該算法一共執(zhí)行了1+n+1+n+1=2n+3次在求時間復(fù)雜度的時候我們忽略頭尾循環(huán)判斷的開銷,只需要分析影響一個算法時間復(fù)雜度的主要部分即可,即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)該算法的時間復(fù)雜度為T)=O(m)稱為線性階注意:分析這類算法的復(fù)雜度關(guān)鍵是分析循環(huán)結(jié)構(gòu)的運行情況例1求和算法,求1+2+3.499+100505070例2求和算法,求1+2+3.+99+1005050intsum=0.ne100行了1次sum=(1+n)*n/2執(zhí)行1次printf(od",sum);執(zhí)行了1次該算法一共執(zhí)行了1+1+1=3次在求時間復(fù)雜度的時候只需要分析影響一個算法時間復(fù)雜度的主要部分即可,即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)該算法的時間復(fù)雜度為T(m)=O(1)稱為常數(shù)階注意:不管這個常數(shù)是多少,我們都記做O(①),而不是O(3)例2求和算法,求1+2+3.+99+100505071例3求和算法,求1+2+3.+99+100+inti,j,X=0,sum=0,n=100/執(zhí)行了1次for(i=l;i<=n;i++ifor(j=l;j<=n;j++X++/執(zhí)行mn次sum=sum+x;)printf(%d”,sum);執(zhí)行了1次在求時間復(fù)雜度的時候我們忽略頭尾循環(huán)判斷的開銷,只需要分析影響一個算法時間復(fù)雜度的主要部分即可,即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)該算法的時間復(fù)雜度為T(n)=O(m2)稱為平方階注意:循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)的次數(shù)例3求和算法,求1+2+3.+99+100+72例1-3設(shè)數(shù)組a和b在前邊部分已賦值,求如下兩個n階矩陣相乘運算算法的時間復(fù)雜度for(i=0;k<n;i++)for(j=0;j<n;j++)ici]j1=0;∥基本語句1for(k=0;k<n;k++)c[ij}=c[ij]+a[ik]b[kljl;〃基本語句2該算法的時間復(fù)雜度為T(n)=O(n3)例1-3設(shè)數(shù)組a和b在前邊部分已賦值,求如下兩個n階矩73例14設(shè)n為如下算法處理的數(shù)據(jù)個數(shù),求如下算法的時間復(fù)雜度。for(i=l;i<=n:i=21)printf(i=%dm”,i);解設(shè)基本語句的執(zhí)行次數(shù)為T(m有≤n,即有T(m)sb所以該算法的時間復(fù)雜度為Tn)=O(bn)。稱為對數(shù)階例14設(shè)n為如下算法處理的數(shù)據(jù)個數(shù),求如下算法的74例1-5:下邊的算法是用冒泡排序法對數(shù)字α中的n個整數(shù)類型的數(shù)據(jù)元素(a[0J-a{n-1),從小到大進(jìn)行排序,求該算法的時間復(fù)雜度。voidBubblesort(intall,intn)inti,j,flag=l;inttempfor(i=l;i<n&&flag==l;i++)flag=0for(=0;j<n-i;j++)if(a[j]alj+lDiflag=l;temp=aljl:alj=a[j+1];alj+l=temp;例1-5:下邊的算法是用冒泡排序法對數(shù)字α中的n個整數(shù)75數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件76數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件77數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件78數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件79數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件80數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件81數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件82數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件83數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件84數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件85數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件86數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件87數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件88數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件89數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件90數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件91數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件92數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件93數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件94數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件95數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件96數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件97數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件98數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件99數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件100數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件101數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件102數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件103數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件104數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件105數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件106數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件107數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件108數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件109數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件110數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件111數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件112數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件113數(shù)據(jù)結(jié)構(gòu)——期末復(fù)習(xí)資料課件114數(shù)據(jù)結(jié)構(gòu)——