算法初步教學(xué)課件

算法初步講師:目錄A二三四一理解算法地定義理解算法與程序地區(qū)別掌握時(shí)間復(fù)雜度與空間復(fù)雜度地分析掌握簡(jiǎn)單基本程序地時(shí)間復(fù)雜度計(jì)算算法初步什么是算法？算法是一系列用來(lái)解決單個(gè)或多個(gè)問(wèn)題,或并具有執(zhí)行計(jì)算功能地命令地集合程序vs.算法A算法初步算法與程序地區(qū)別時(shí)間復(fù)雜度A算法初步時(shí)間復(fù)雜度在時(shí)間維度上判斷一個(gè)算法是否高效地工具時(shí)間復(fù)雜度地定義:時(shí)間頻度:一個(gè)算法地語(yǔ)句執(zhí)行次數(shù),通常記為時(shí)間復(fù)雜度考察地是當(dāng)輸入規(guī)模趨于無(wú)窮時(shí),時(shí)間頻度地漸近情況若有某個(gè)輔助函數(shù),使得地極限值（當(dāng)趨近于無(wú)窮大時(shí)）為不等于零地常數(shù),則稱是地同數(shù)量級(jí)函數(shù)。記作算法初步時(shí)間復(fù)雜度地意義:對(duì)于解決同一問(wèn)題地算法來(lái)說(shuō),當(dāng)輸入規(guī)模極為龐大時(shí),時(shí)間復(fù)雜度地差距意味著計(jì)算機(jī)運(yùn)算地效率很大數(shù)量級(jí)地差距。同樣解決排序問(wèn)題,A算法地復(fù)雜度為,而B算法地復(fù)雜度為,如果排序問(wèn)題地輸入規(guī)模為一零零零萬(wàn),則用A算法運(yùn)行程序解決問(wèn)題需要大約三個(gè)小時(shí),而用B算法只需要不到兩秒算法初步時(shí)間復(fù)雜度是漸地:

因?yàn)楫?dāng)趨于無(wú)窮地時(shí)候,對(duì)算法運(yùn)行時(shí)間占主導(dǎo)地位因?yàn)楫?dāng)趨于無(wú)窮地時(shí)候,前面地常數(shù)因子遠(yuǎn)沒(méi)有輸入規(guī)模地依賴重要算法初步簡(jiǎn)單程序地復(fù)雜度分析循環(huán)一個(gè)輸入規(guī)模為地for/while循環(huán)地時(shí)間復(fù)雜度為有i個(gè)輸入規(guī)模為地for/while循環(huán)疊加在一起地算法地時(shí)間復(fù)雜度為分支因?yàn)榉种Ъ匆馕吨豢杉娴?所以絕不可能出現(xiàn)同時(shí)入同一個(gè)前提下地兩個(gè)分支地情況。因此我們可以得出結(jié)論,一個(gè)分支結(jié)構(gòu)地運(yùn)行時(shí)間絕不會(huì)超過(guò)前提條件判斷地運(yùn)行時(shí)間,加上分支結(jié)構(gòu)較復(fù)雜地分支地運(yùn)行時(shí)間?？臻g復(fù)雜度A算法初步空間復(fù)雜度:空間復(fù)雜度是對(duì)一個(gè)算法所需存儲(chǔ)空間地量度,一般情況下只考慮算法在運(yùn)行過(guò)程臨時(shí)占用地存儲(chǔ)空間與時(shí)間復(fù)雜度一樣,空間復(fù)雜度也考察輸入規(guī)模趨于無(wú)窮時(shí)所占用空間地漸近情況,所以空間復(fù)雜度也用大符號(hào)來(lái)表示,也記做算法初步常用算法時(shí)間與空間復(fù)雜度匯總:排序算法均時(shí)間復(fù)雜度最優(yōu)時(shí)間復(fù)