數(shù)據(jù)結(jié)構(gòu)(Java語言描述)(第2版)課件 1.2 算法_第1頁
數(shù)據(jù)結(jié)構(gòu)(Java語言描述)(第2版)課件 1.2 算法_第2頁
數(shù)據(jù)結(jié)構(gòu)(Java語言描述)(第2版)課件 1.2 算法_第3頁
數(shù)據(jù)結(jié)構(gòu)(Java語言描述)(第2版)課件 1.2 算法_第4頁
數(shù)據(jù)結(jié)構(gòu)(Java語言描述)(第2版)課件 1.2 算法_第5頁
已閱讀5頁,還剩12頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

數(shù)據(jù)結(jié)構(gòu)主講人:張靜常州信息職業(yè)技術(shù)學(xué)院1.2算法程序=算法+數(shù)據(jù)結(jié)構(gòu)Part01算法及其特性算法(Algorithm)是描述解決特定問題的思路、方法和步驟,是求解步驟(指令)的有限序列。輸入:一個算法應(yīng)該有零個或多個輸入。算法的概念算法的重要特性算法及其特性有窮性:一個算法必須在執(zhí)行有窮步驟之后正常結(jié)束,不能形成無窮循環(huán),并且每一個步驟都在可接受的時間內(nèi)完成。確定性:算法中的每一條指令必須有確切的含義,不能產(chǎn)生多義性??尚行裕核惴ㄖ械拿恳粭l指令必須是切實可執(zhí)行的。輸出:一個算法應(yīng)該有一個或多個輸出。算法和程序都是用來表達解決問題的邏輯步驟;算法是對解決問題的方法的具體描述,程序是用某種程序設(shè)計語言對算法的具體實現(xiàn)。算法和程序的關(guān)系區(qū)別算法及其特性程序和算法的最大區(qū)別是程序可以是無窮的,而算法必須滿足有窮性,即算法不允許無限循環(huán)。例如,操作系統(tǒng)是個程序,這個程序在不遭破壞的情況下永遠不會停止,即使沒有作業(yè)需要處理,它仍處于一個等待循環(huán)中。Part02算法的描述方法使用類似計算機程序設(shè)計語言的所謂偽語言來描述算法,接近高級程序設(shè)計語言的寫法,但不一定能直接編譯運行的代碼。偽代碼直接以可讀性高的高級程序設(shè)計語言來表示。高級程序設(shè)計語言使用中文、英文、數(shù)字等自然語言來描述算法。自然語言使用流程圖或N-S圖來描述算法??驁D算法的描述方法本課程采用Java語言表示。Part03算法分析算法設(shè)計的要求算法分析正確性可讀性健壯性時間高效性-算法的時間復(fù)雜度空間高效性-算法的空間復(fù)雜度一個算法的時間耗費,就是該算法中所有語句的頻度之和。算法分析算法的時間復(fù)雜度表示算法的時間效率與算法所處理的數(shù)據(jù)元素個數(shù)n(問題規(guī)模)函數(shù)關(guān)系的最常用函數(shù)是O()函數(shù)(O()讀作大O)。算法的時間復(fù)雜度T(n)可記作:T(n)=O(f(n))O()說明O(1)稱為常數(shù)時間,表示算法的運行時間是一個常數(shù)倍,與問題規(guī)模無關(guān)。O(n)稱為線性時間,執(zhí)行時間增加的大小與問題規(guī)模成線性關(guān)系。O(log2n)稱為冪對數(shù)時間,成長速度比線性時間慢,比常數(shù)時間快。O(n2)稱為平方時間,算法的運行時間成二次方增長。O(n3)稱為立方時間,算法的運行時間成三次方增長。O(2n)稱為指數(shù)時間,算法的運行時間成2的n次方增長。O(nlog2n)稱為線性對數(shù)時間,介于線性和二次方增長之間。以上時間復(fù)雜度的順序:O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)算法分析11示例1示例2示例3示例1假設(shè)某算法運行時間為T(n)=4n3+3n2+9n,求它的時間復(fù)雜度。例1-1示例4n3+3n2+9n4O()算法分析12示例1示例2示例3分析下列程序段的時間復(fù)雜度public

static

voidmain(String[]args){ intn=100,sum=0;//(1)賦初值for(inti=1;i<=n;i++){sum=sum+i;//(2)累加和}System.out.println(sum);}例1-2示例2示例4sum=sum+i;O(n)算法分析13示例1示例2示例3分析下列程序段的時間復(fù)雜度public

static

voidmain(String[]args){intn=8,count=0;//(1)賦初值

for(inti=1;i<=n;i*=2){ count++;//(2)統(tǒng)計次數(shù)}System.out.println(count);}例1-3示例3示例4count++O(log2n)示例4算法分析14示例1示例2示例3分析下列程序段的時間復(fù)雜度public

static

voidmain(String[]args){intn=100,count=0;for(inti=1;i<=n;i++){

for(intj=1;j<=i;j++){ count++;} }System.out.println(count);}例1-4示例4O(n2)

最壞時間復(fù)雜度:最壞情況下的時間復(fù)雜度。最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界。平均時間復(fù)雜度:在所有可能的輸入實例均以等概率出現(xiàn)的情況下,算法的期望運行時間。算法分析算法分析16算法(程序)本身所占用的存儲空間;輔助變量所占用的存儲空間。輸入數(shù)據(jù)所占用的存儲空間;算法的空間復(fù)雜度是指算法在運行過程中所占用的輔助存儲空間大小??臻g復(fù)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論