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

static

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

for(inti=1;i<=n;i*=2){ count++;//(2)統(tǒng)計(jì)次數(shù)}System.out.println(count);}例1-3示例3示例4count++O(log2n)示例4算法分析14示例1示例2示例3分析下列程序段的時(shí)間復(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)

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