第二講 算法分析概要與線性表

1、算法復雜度概念 線性表（上）,2008/02/19,2,關(guān)于浮點數(shù)四則運算的定義,3,算法復雜度問題：,一般是指問題隨規(guī)模的增長算法所需消耗的運算時間和內(nèi)存空間的增長趨勢。 因此不考慮計算機本身硬件的特質(zhì)，一般也忽略算法所消耗的與問題規(guī)模無關(guān)的固定量的計算與空間。,4,如何描述增長趨勢的高低？,不考慮不變量： C + f(n) f(n) 忽略不能與時俱進的因素 k * f(n) f(n) 區(qū)分同類型的增長方式的不同量級 f(n) = nk f(n) = nk+c 專注增長趨勢中最本質(zhì)的區(qū)別 C log n n nk kn (k 1),5,算法復雜度的考察方法,考察一個算法的復雜度，一般考察的是

2、當問題復雜度n的增加時，運算所需時間、空間代價f(n)的上下界。（Asymptotic upper or lower bound） 進一步而言，又分為最好情況、平均情況、最壞情況三種情況。通常最壞情況往往是我們最關(guān)注的。,6,算法復雜度的上界（大O表示法）,大O表示法是用一個函數(shù)f(n)來描寫算法復雜度的上界的表示方式。記為：O（f(n)）,7,大表示法,如果能同時找到算法復雜度的上下確界函數(shù)g(n)，f(n)。 且g(n) = f(n)，則算法復雜度能更精確的表達為(f(n),8,算法復雜度的優(yōu)化（fibonacci數(shù)列問題）,剛開始（零年）1對 一年后1對 二年后2對 三年后3對 今年的兔

3、子對數(shù) = 前年已經(jīng)有的兔子總數(shù) + 去年的兔子數(shù),0 1 2 3 4,Fibonacci 數(shù)列,9,采用展開遞推公式的方法,fib(5),fib(3),fib(4),+,fib(1),fib(2),+,fib(0),fib(1),+,fib(2),fib(3),+,fib(1),fib(2),+,從fib(n)開始，自頂向下逐層展開。 直到fib(0) 或 fib(1)為止。 然后逐層計算上去。,= 1,= 1,= 1,= 1,10,遞歸算法的運算復雜度分析,fib(5),fib(3),fib(4),+,T(n) = T(n-1) + T(n-2) +1 T(1) = T(0) = 1,fi

4、b(1),fib(2),+,fib(0),fib(1),+,fib(2),fib(3),+,fib(1),fib(2),+,找出與n相關(guān)的函數(shù),= 1,= 1,= 1,= 1,2n/2 T(n) - 1 = 2n,11,奇妙的黃金分割數(shù),A B,AB BC = BC AB + BC,1,0.618,AB AB + BC + 1 = BC BC,BC,AB,+1,Xn+1 = Xn + Xn-1,12,使用雙子星遞歸函數(shù)實現(xiàn)該算法：,#include void f2(int x,int y); void f1( int x, int y) if (x 200) return; else x =

5、x +y; y = x -y; x = x - y; printf(%d, x); f2(x,y); ,void f2(int x,int y) y = x + y; f1(x,y); void main() f1(0,1); ,13,Fibonacci 數(shù)列的通項公式,1/1 = 1, 2/1 = 2, 3/2 = 15, 5/3 = 1666., 8/5 = 16, 13/8 = 1625 21/13 = 161538.,黃金分割數(shù),T(n) = O(1.618 n),14,Fibonacci 數(shù)列的矩陣表達,X,=,1+1 1+0 1+0 1+0,X,=,2+1 2+0 1+1 1+0,

6、X,=,5 3 3 2,n,=,fib(n+1) fib(n) fib(n) fib(n-1),How come?,15,Fibonacci 數(shù)列的矩陣表達,X,=,1+1 1+0 1+0 1+0,X,=,2+1 2+0 1+1 1+0,X,=,5 3 3 2,n,=,fib(n+1) fib(n) fib(n) fib(n-1),How come?,16,Fibonacci 數(shù)列的矩陣表達,X,=,X,+,=,+,F2 0 F1 0,BC,n,=,fib(n+1) fib(n) fib(n) fib(n-1),17,Recursive powering（遞歸乘方法）,n,n次矩陣乘法,算法復

7、雜度 = O (n),=,n/2,n/2,x,+ ,n/2/2,n/2/2,x,+ ,總共要多少層遞歸？,=,log2n,算法復雜度 = O (logn),18,Recursive powering（遞歸乘方法）,n,n次矩陣乘法,算法復雜度 = O (n),=,n/2,n/2,x,+ ,n/2/2,n/2/2,x,+ ,總共要多少層遞歸？,=,log2n,算法復雜度 = O (logn),19,Fibonacci 數(shù)列算法的優(yōu)化 參考閱讀：MIT教程第三講,T(n) = O ( 1.618n) = O( n ) = O( logn ),fib(110)： 1022 次運算 111 次運算 7

8、 次運算,20,算法設(shè)計技術(shù),貪心法：試圖通過局部最優(yōu)達到全局最優(yōu) 分治法：劃分成小問題，各個求解 回溯法：對多種可能性逐步試探，失敗時回來選其它可能性 動態(tài)規(guī)劃法：多路經(jīng)的求解方式 分枝界限法：上下界+廣度優(yōu)先,21,算法與問題求解,問題： 為貧困地區(qū)兒童募捐： 10，000元。 解決方案： A：向遇到的每一個人盡可能的鼓動募捐，直到完成任務(wù)。 B：鼓動10個朋友，每人去 募捐1000元。 鼓動10個朋友，每人去 募捐100元 鼓動10個朋友，每人捐10元。,22,分治算法要點：,要能夠確定可以解決的 簡單問題(base case) 要能夠找到分解化簡（recursive decomposi

9、tion）問題的方法,23,線性表（順序表）,定義 基本操作 算法復雜度分析,24,“線性表”簡稱為表，是零個或多個元素的有窮序列，表示成 A =（a0, a2, . , ai -1, ai , ai+1, , an -1）（n1） 表中所含元素的個數(shù)稱為表的“長度”。 以二元組表示： L= ，其中D= a1,a2, a3, . an 表示元素集合 S= R R=, , 表示關(guān)系集,a1,圖頂點：表示數(shù)據(jù) 示 邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系,an,線性表的形式化定義,25,說明,同一線性表中的元素必須是同一類型的； 在線性表中只有三類元素： 第一個元素，最后一個元素（結(jié)尾標記），其他元素； 下

10、面的聲明語句是什么意思？ char *str = “”; char a20 = “hello!”;,26,線性表的順序存儲實現(xiàn),為了存儲線性表，至少要保存下列信息：1）線性表中的數(shù)據(jù)元素本身； 2）線性表中數(shù)據(jù)元素的順序關(guān)系； 3）線性表中起始位置； 4）線性表的結(jié)尾標記；,在計算機內(nèi)部可以采用不同的方式來存儲一個線性表，其中最簡單的方式就是采用順序存儲結(jié)構(gòu)。即通過物理存儲上的相鄰關(guān)系來來表述元素間的順序關(guān)系。 采用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表,27,用數(shù)組存儲線性表時元素的地址可以通過起始的基地址在加上偏移量來得到。,Offset = sizeof(e) * subscript,線性表

11、的順序存儲實現(xiàn)（續(xù)）,Base + Offset = location,28,an-1,Loc(a0)+(n-1)*k,an-1,n-1,ai,Loc(a0)+i*k,ai,i,a1,Loc(a0)+k,a1,1,a0,Loc(a0),a0,0,數(shù)據(jù)元素,存儲地址,數(shù)據(jù)元素,下標變量（編號）,直接存取,29,在C 語言中定義線性表,定義1： #define MAXNUM 100 DataType elementMAXNUM; int n; /* 實際元素個數(shù)n MAXNUM */ 定義2： struct SeqList DataType elementMAXNUM; int n; /* 實際元

12、素個數(shù)n MAXNUM */ ; 定義3：鏈表,順序表,30,順序表常用操作：,創(chuàng)建操作： 靜態(tài)聲明： DataType buffMAXNUM; 動態(tài)申請： DtatType *p = (DataType)malloc(MAXNUM * sizeof(DataType); 下標訪問操作：pi; 插入、刪除操作 查找與排序,31,順序表的插入算法框架 int insert_seq( SeqList *plist, int p, DataType x ) 判斷表是否會溢出； 判斷 0pn; 從元素kn-1至 kp順序下移一位； /*第n個元素的下標是n-1*/ 在位置p處插入x； ,32,插入排序

13、,基本思想：每步將一個待排序的記錄，按其排序碼大小插到前面已經(jīng)排序的字序列的合適位置，直到全部插入排序完為止。,x,順次選取一個元素,插入到合適位置,33,插入排序的細分類,如何插入到已排好序的序列中？ 直接插入（從后向前找位置后插入） O(n2) 二分法插入（按二分法找位置后插入） O(nlog2n) 表插入排序（按鏈表查找位置后插入） O(n2),34,直接插入排序,基本思想： 假定前面m 個元素已經(jīng)排序； 取第(m+1) 個元素，插入到前面的適當位置； 一直重復，到m=n 為止。 （初始情況下，m = 1）,35,第一趟： 23， 起始只有一個記錄 11, 23 11 第二趟： 11，2

14、3， 11，23，55 55 第三趟： 11，23，55， 11，23，55，97 97 第四趟： 11，23，55，97， 11，19，23，55，97 19 第五趟： 11，19，23，55，97， 11，19，23，55，80，97 80,示例：23，11，55，97，19，80,36,數(shù)組數(shù)據(jù)插入,37,將操作分離成 獨立的函數(shù),38,在算法中使用結(jié)構(gòu)體作為數(shù)據(jù)對象,typedef int KeyType; typedef int DataType; typedef struct KeyType key; /* 排序碼字段 */ DataType info; /* 記錄的其他字段 */

15、 RecordNode; typedef struct int n; /* n為文件中的記錄個數(shù)，nMAXNUM */ RecordNode *record; SortObject;,（周二上機題）,39,直接插入排序算法復雜度評價,極端情況下： 最小比較次數(shù)每個記錄僅比較一次 最大比較次數(shù)每個記錄比較已排好序的記錄長度,40,直接插入排序算法評價2,最小移動次數(shù) 最大移動次數(shù),41,直接插入排序算法評價3,初始數(shù)據(jù)狀態(tài)相關(guān)： 文件初態(tài)不同時，直接插入排序所耗費的時間有很大差異。 若文件初態(tài)為正序，則算法的時間復雜度為O(n) 若初態(tài)為反序，則時間復雜度為O(n2),42,直接插入排序算法評價

16、4 平均復雜度,插入記錄Ri-1，有i種可能的插入位置，即插入到第0，1，i-1位置上，假設(shè)每種情況發(fā)生的概率是相等的，均為 pj = 1/i (j=0,1,i-1) 比較次數(shù)為Cj=j+1(j=0,i-2,i-2)，則插入記錄Ri-1的平均比較次數(shù)為,43,直接插入排序算法評價5 平均復雜度,直接插入排序的 總的比較次數(shù)為：,44,直接插入排序算法評價,直接插入排序算法的平均移動次數(shù)與平均比較次數(shù)同級，也是O(n2) 直接插入排序的平均時間復雜度為T(n) = O(n2) 算法中引入了一個附加的記錄空間temp，因此輔助空間為S(n) = O(1) 直接插入排序是穩(wěn)定的,45,二分法插入排序

17、,特點：在直接插入排序的基礎(chǔ)上減少比較的次數(shù)，即在插入Ri時改用二分法比較找插入位置，便得到二分法插入排序 限制：必須采用順序存儲方式。,46,(highlow ，查找結(jié)束，插入位置為low 或high+1 ),( 4236 ),( 4253 ),47,二分法插入排序算法,void binSort(SortObject * pvector) int i, j, left, mid, right;RecordNode temp;for( i = 1; i n; i+ ) temp = pvector- recordi; left = 0; right = i 1; while (left rec

18、ordmid.key) right = mid-1;,else left = mid+1; /while for(j=i-1; j=left; j-) pvector-recordj+1 = pvector-recordj; if(left != i) pvector-recordleft = temp; / for / binSort,48,二分法插入排序方法性能分析,當n較大時，比直接插入排序的最大比較次數(shù)少得多。但大于直接插入排序的最小比較次數(shù) 算法的移動次數(shù)與直接插入排序算法的相同 最壞的情況為n2/2 最好的情況為n 平均移動次數(shù)為O(n2) 二分法插入排序算法的平均時間復雜度為T(

19、n)= O(n2) 二分插入排序法是穩(wěn)定的排序算法,在檢索時采用leftright結(jié)束，left、right的修改原則是：temp.key recordmid.key，保證排序是穩(wěn)定的。,49,結(jié)論,移動次數(shù)與直接插入排序相同，最壞的情況為n2/2，最好的情況為n，平均移動次數(shù)為O(n2) 二分法插入排序算法的平均時間復雜度為 T(n)= O(n2) 二分法插入排序是穩(wěn)定的,50,線性表的抽象數(shù)據(jù)類型,ADT List is operations List createNullList ( void ) 創(chuàng)建并且返回一個空線性表。 int insertPre ( List list, posi

20、tion p, DataType x ) 在list中p位置前插入值為x的元素，并返回插入成功與否的標志。 int insertPost ( List list, position p, DataType x ) 在list中p位置后插入值為x的元素，并返回插入成功與否的標志。 int deleteV (List list, DataType x ) 在list中刪除一個值為x的元素，并返回插入成功與否的標志。 int deleteP (List list, position p ) 在list中刪除位置為p的元素，并返回插入成功與否的標志。 Position locate ( List li

21、st, DataType x ) 在list中查找值為x的元素的位置。 int isNull ( List list ) 判別list是否為空線性表。 end ADT List,51,ListEmpty( L ) 判定線性表是否為空表。 初始條件：線性表L已存在。 操作結(jié)果：若 L 為空表，則返回 TRUE，否則返回 FALSE。 ListLength( L ) 求得線性表的長度，即線性表中所含數(shù)據(jù)元素的個數(shù)。 初始條件：線性表 L 已存在。 操作結(jié)果：返回 L 中元素個數(shù)。 PriorElem( L, cur_e, &pre_e ) 初始條件：線性表 L 已存在。 操作結(jié)果：若 cur_e

22、是 L 中的數(shù)據(jù)元素，則用 pre_e 返回它的前驅(qū)， 否則操作失敗，pre_e 無定義。 若 cur_e 是線性表 L 中第一個數(shù)據(jù)元素，則它的前驅(qū) pre_e 為空元素。 NextElem( L, cur_e, &next_e ) 初始條件：線性表 L 已存在。 操作結(jié)果：若 cur_e 是 L 中的數(shù)據(jù)元素，則用 next_e 返回它的后繼， 否則操作失敗，next_e 無定義。 若 cur_e 是線性表 L 中最后一個數(shù)據(jù)元素，則它的后繼 next_e 為空元素。 GetElem( L, i, &e ) 初始條件：線性表 L 已存在，1iLengthList(L)。 操作結(jié)果：用 e 返回 L 中第 i 個元素的值。 此操作的結(jié)果是求得線性表 L 中和位序 i 相對應(yīng)的數(shù)據(jù)元素，因此，只有當 i 的值在線性表的長度范圍內(nèi)才有意義。 LocateElem( L, e, compare( ) ) 初始條件：線性表 L 已存在，compare( ) 是元素判定函數(shù)。 操作結(jié)果：返回 L 中第1個與 e 滿足關(guān)系 compare( ) 的元素的位序。 若這樣的元素不存在，則返回值為0。,線性表的抽象數(shù)據(jù)類型（引用型操作）,52,線性表的抽象數(shù)據(jù)類型（加工型操作）,ClearList( &L ) 初始條件：線性表 L 已存在。 操作結(jié)果：將 L