【正文】 llowing program segment: s=0。 for (i=0。i=n。i++) for (j=0。j=n。j++) for (k=0。k=i+j。k++) s++。 解：該算法的基本操作是語句 S++，其頻度為： 0 0 0 0 0 0033( 2 2 ) ( 1 )( ) 1 ( 1 )21( 2 2 )2( 1 ) ( )ijn n n n ni j k i j inii n nT n i jninn o n?? ? ? ? ? ??? ? ?? ? ? ? ??? ? ?? ? ?? ? ? ? ? ??例 一個沒有循環(huán)的算法的基本運算次數(shù)與問題規(guī)模n無關(guān) ,記作 O(1),也稱作 常數(shù)階 。 一個只有一重循環(huán)的算法的基本運算次數(shù)與問題規(guī)模 n的增長呈線性增大關(guān)系 ,記作 O(n),也稱 線性階 。 其余常用的還有平方階 O(n2)、立方階 O(n3)、對數(shù)階 O(log2n)、指數(shù)階 O(2n)等。 各種不同數(shù)量級對應的值存在著如下關(guān)系： O(1)O(log2n)O(n)O(n*log2n)O(n2) O(n3)O(2n)O(n!) 例 求階乘和： sum=1!+2!+3!+… …+n! 方法 1： float sum1(int n) {float s=0,p=1。 int i。 for(i=1。i=n。i++) { p=p*i。 s=s+p} return s。 } time plexity ：T(n) = O(n) 方法 2： float sum1(int n) {float s=0,p=1。 int i,j。 for(i=1。i=n。i++) { p=1 for(j=1。j=i。j++) p=p*i。 s=s+p。} return s。 } time plexity：T(n) = O(n2) T(n) = = =n1 + n2 + n3 + ……+1= ??????11 11njjni????11)(njjn2)1( ?nn例 Bubble Sort algorithm void bubble_sort (int a[ ], int n ) { //用起泡排序方法，將 a[ ] 中 n個整數(shù)的序列排列成自小至大有序的整數(shù)序列 int i,j,t。 for(j=1。j=n1。j++) for(i=1。j=nj。i++) if(a[i]a[i+1]) {t=a[i]。 a[i]=a[i+1]。 a[i+1]=t。} } // bubble_sort （ 2） Space Efficiency 表示隨著問題規(guī)模 n的增大，算法運行所需存儲量的增長率與 g(n) 的增長率相同。 記作： S(n)=O (g(n)) 算法和算法的分析 算法的存儲量包括 輸入數(shù)據(jù)所占空間； 程序本身所占空間； 輔助變量 (形參，棧等 )所占臨時空間。 算法和算法的分析 我們用執(zhí)行算法所需的 輔助空間 的大小作為算法所需空間的度量。 例 數(shù)組的逆置 方法 1：就地置換 Space Efficiency ： S(n)= O(1) a1 a2 … … … … an 1 an 算法和算法的分析 方法 2 另辟空間 a1 a2 … … … … an 1 an b1 b2 … … … … bn 1 bn Space Efficiency ： S(n)= O(n) 算法和算法的分析 學習提要 掌握本課程所涉及到的基本名詞、術(shù)語和概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系及性質(zhì)。 了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。 理解算法設計的五個要素和基本要求；掌握算法效率的度量方法，著重學習算法的時間復雜度分析。 本章小結(jié) ? 數(shù)據(jù)結(jié)構(gòu)研究的對象 ? 數(shù)據(jù)結(jié)構(gòu)是研究 非數(shù)值問題 中計算機的操作對象以及它們之間的關(guān)系和操作的學科 ? 基本概念 ? data ? Data element ? Data item ? Data structure ? 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。 logical structure storage structure operation： sort insert select update delete linear structure nonlinear structure sequential storage linked storage linear list stack queue tree graph 數(shù)據(jù)結(jié)構(gòu)的三個方面： ? 抽象數(shù)據(jù)類型：是一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。 算法的度量 ： Time plexity Space Complexity ? 算法的時間復雜度、空間復雜度 ? T(n) = O(f(n)) ? O(n) = O(f(n)) ? 例 15 ++x。 ? 例 16 for (i=1。 i=n。 ++i) ? ++x。 ? 例 17 for (i=1。 i=n。 ++i) ? for (j=1。 j=n。 ++j) ? ++x。 2i 1 1 11n n njinn? ? ???? ? ?T(n)=O(n2) O(1) O(n) ? 例 18 for (i=1。 i=n。 ++i) ? for (j=1。 j=i1。 ++j) ? ++x。 1i 1 1 1( 1 )112jinnjinni??? ? ??? ? ?? ? ?T(n) = O(n2) ? 例 19 for (i=1。 i=n。 ++i) ? for (j=1。 j=n。 ++j) ? { ? c[i][j]=0。 ? for (k=1。 k=n。 ++k) ? c[i][j]+=a[i][k]*b[k][j]。 ? } Ο(n3) 例 110 for (i=1。 i=n。 i=2*i) ++x。 設基本執(zhí)行次數(shù)為 T(n)，則： ? 即 ? T(n)=log2n ()2 Tn n?2T ( n) l og n?Ο(1)＜ Ο(log2n)＜ Ο(n)＜ Ο(nlog2n)＜ Ο(n2)＜ Ο(n3) ＜ … ＜ Ο(2n)＜ Ο(n!) Count=0。x=1。 While(xn) { x*=2。 Count++。 } T(n)=log2n