版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 貴陽2025年貴州貴陽市白云區(qū)第十四中學(xué)秋季臨聘教師招聘筆試歷年參考題庫附帶答案詳解
- 聊城2025年山東聊城市東昌府區(qū)中等職業(yè)教育學(xué)校招聘13人筆試歷年參考題庫附帶答案詳解
- 湘西2025年湖南湘西州永順縣公安局輔警招聘10人筆試歷年參考題庫附帶答案詳解
- 河南2025年河南林業(yè)職業(yè)學(xué)院招聘6人筆試歷年參考題庫附帶答案詳解
- 廣西2025年廣西自然資源和不動產(chǎn)登記中心招聘筆試歷年參考題庫附帶答案詳解
- 嘉興2025年浙江嘉興市中醫(yī)醫(yī)院招聘編外合同制人員(第二批)筆試歷年參考題庫附帶答案詳解
- 2026年大數(shù)據(jù)綜合問題解析及答案
- 2026年游戲設(shè)計與開發(fā)技術(shù)題庫
- 2026年金融投資分析師考試題庫與參考答案
- 職業(yè)性眼病患者隨訪管理體系的建立
- 《國家十五五規(guī)劃綱要》全文
- 《工業(yè)工程概論》課件-第3章 人因工程學(xué)
- DB37∕T 4328-2021 建筑消防設(shè)施維修保養(yǎng)技術(shù)規(guī)程
- 中美中小企業(yè)融資模式與策略差異剖析:基于比較研究的視角
- 年產(chǎn) 48 萬平方米高頻高速、多層及高密度印制電路板 生產(chǎn)線擴建項目 環(huán)境影響報告書
- 2025年秋季第一學(xué)期學(xué)校全面工作計劃:融合教育守初心 全面發(fā)展啟新程【課件】
- 2024年度EHS工作計劃安全工作計劃安全工作方案(管理方案)
- 2025屆上海市高考英語考綱詞匯表
- 公司證照管理管理制度
- 黑龍江哈爾濱2024年中考語文現(xiàn)代文閱讀真題
- 知識圖譜構(gòu)建實踐
評論
0/150
提交評論