線性表(一順序表)

1、XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING任課教師：馬彥卓任課教師：馬彥卓數(shù)據(jù)結(jié)構(gòu)與算法分析用計(jì)算機(jī)解決實(shí)際問題的學(xué)問用計(jì)算機(jī)解決實(shí)際問題的學(xué)問XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING思考問題 順序表用C語言應(yīng)該怎么表達(dá)？該方

2、法是把邏輯上相鄰的該方法是把邏輯上相鄰的結(jié)點(diǎn)存貯在物理位置上相結(jié)點(diǎn)存貯在物理位置上相鄰的存貯單元里。鄰的存貯單元里。由此得到的存貯表示稱為由此得到的存貯表示稱為順序存順序存儲(chǔ)結(jié)構(gòu)儲(chǔ)結(jié)構(gòu)。主要應(yīng)用于線性數(shù)據(jù)結(jié)構(gòu)主要應(yīng)用于線性數(shù)據(jù)結(jié)構(gòu)線性表線性表可以通過不同的可以通過不同的存儲(chǔ)方式存儲(chǔ)存儲(chǔ)方式存儲(chǔ). .順序表順序表鏈表鏈表散列表散列表XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING內(nèi)容內(nèi)容1.1.線性表線性表的基本概念的

3、基本概念2.2.線性表線性表的順序存儲(chǔ)結(jié)構(gòu)及其運(yùn)算的順序存儲(chǔ)結(jié)構(gòu)及其運(yùn)算3.3.線性表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其運(yùn)算的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其運(yùn)算注：教材注：教材第第2 2章章4.4.線性表線性表存儲(chǔ)結(jié)構(gòu)的選擇依據(jù)存儲(chǔ)結(jié)構(gòu)的選擇依據(jù)2 2線性表線性表XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING1.1.線性表的基本概念線性表的基本概念一種邏輯結(jié)構(gòu)一種邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)定義邏輯結(jié)構(gòu)定義l 線性表是由線性表是由n n（n0n0）個(gè)

4、數(shù)據(jù)元素個(gè)數(shù)據(jù)元素a a1 1,a,a2 2,a an n構(gòu)成的有限序列。其構(gòu)成的有限序列。其中，數(shù)據(jù)元素的個(gè)數(shù)中，數(shù)據(jù)元素的個(gè)數(shù)n n定義為表的長度。當(dāng)定義為表的長度。當(dāng)n n=0=0時(shí)稱為空表，通常將時(shí)稱為空表，通常將非空的線性表（非空的線性表（n0n0）記作記作：（：（a a1 1,a,a2 2,a,an n）。）。l 數(shù)據(jù)元素?cái)?shù)據(jù)元素a ai i的具體含義，在不同的情況下可以不同的具體含義，在不同的情況下可以不同。l 同一線性表中的元素必定具有相同的特性同一線性表中的元素必定具有相同的特性。1234XidianXidian University UniversitySCHOOL OF

5、TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING1.1.線性表的基本概念線性表的基本概念一種邏輯結(jié)構(gòu)一種邏輯結(jié)構(gòu)邏輯特征邏輯特征l對(duì)于非空的線性表，有且僅有一個(gè)對(duì)于非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)開始結(jié)點(diǎn)a a1 1，有且僅有一個(gè)有且僅有一個(gè)終端結(jié)終端結(jié)點(diǎn)點(diǎn)a an n。l當(dāng)當(dāng)i i=1,2,n=1,2,n 1 1時(shí)，時(shí)，a ai i有且僅有一個(gè)有且僅有一個(gè)直接后繼直接后繼a ai+1i+1；當(dāng)當(dāng)i i=2,3,n=2,3,n時(shí)，時(shí)，a ai i有且僅有一個(gè)有且僅有一個(gè)直接前趨直接前趨a ai i 1

6、 1。l線性表中結(jié)點(diǎn)之間的線性表中結(jié)點(diǎn)之間的邏輯關(guān)系邏輯關(guān)系即是上述的鄰接關(guān)系即是上述的鄰接關(guān)系；l線性表是一個(gè)線性表是一個(gè)線性結(jié)構(gòu)線性結(jié)構(gòu)。1234XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING1.1.線性表的基本概念線性表的基本概念基本運(yùn)算基本運(yùn)算基本運(yùn)算基本運(yùn)算l構(gòu)造一個(gè)空構(gòu)造一個(gè)空表表 CREATLISTCREATLIST(&L)(&L)l置空表置空表 SETNULL(LSETNULL(L)

7、 )l求長度求長度 LENGTH(LLENGTH(L) )l取結(jié)點(diǎn)取結(jié)點(diǎn) GET(GET(L,iL,i) )l定位定位 LOCATE(LOCATE(L,xL,x) )l插入插入 INSERT(INSERT(L,x,iL,x,i) )l刪除刪除 DELETE(DELETE(L,iL,i) )l取直接前趨取直接前趨 PRIOR(PRIOR(L,aiL,ai) )l取直接后繼取直接后繼 NEXT(NEXT(L,aiL,ai) )1234示例：刪除重復(fù)結(jié)點(diǎn) PURGE(L)XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS EN

8、GINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING1.1.線性表的基本概念線性表的基本概念基本運(yùn)算基本運(yùn)算例：刪除多余重復(fù)結(jié)點(diǎn)例：刪除多余重復(fù)結(jié)點(diǎn) 注意其中的邊緣情況處理注意其中的邊緣情況處理void PURGE(Linear_list L) /* 刪除線性表中重復(fù)出現(xiàn)的多余結(jié)點(diǎn)刪除線性表中重復(fù)出現(xiàn)的多余結(jié)點(diǎn) */ int i=1,j,x,y; while (iLENGTH(L) /*每次循環(huán)使當(dāng)前第每次循環(huán)使當(dāng)前第i結(jié)點(diǎn)是無重復(fù)值的結(jié)點(diǎn)結(jié)點(diǎn)是無重復(fù)值的結(jié)點(diǎn)*/ x=GET(L,i); /* 取當(dāng)前第取當(dāng)前第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) */ j=i+1; w

9、hile (jlast)=maxsize-1) printf (“overflow”);return (0); /* 表空間溢出表空間溢出 */ else if (i(L-last)+2) printf (“error”);return (0); /* 非法位置非法位置 */ else for (j=L-last; j=i-1;j-) L-dataj+1= L-dataj; /* 結(jié)點(diǎn)后移結(jié)點(diǎn)后移 */ L-datai-1=x; /* 插入插入x，存在存在( L).datai 1中中 */ L-last=L-last+1; /* 終端結(jié)點(diǎn)下標(biāo)加終端結(jié)點(diǎn)下標(biāo)加1 */ return (1); /

10、* INSERT */注意注意當(dāng)當(dāng) i=n+1 時(shí)，時(shí)，for循環(huán)循環(huán)不執(zhí)行，也即不需要將任何結(jié)點(diǎn)后移。不執(zhí)行，也即不需要將任何結(jié)點(diǎn)后移。2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表基本運(yùn)算：刪除表基本運(yùn)算：刪除 刪除前 刪除 刪除后(移動(dòng)) 0 a1 a1 a1 1 a2 a2 a2 i2 ai1 ai1 ai1 i1 ai ai+1 i ai+

11、1 ai+1 ai+2 last an-1 an-1 an last n-1 an an maxsize1 刪除運(yùn)算刪除運(yùn)算直接移動(dòng)數(shù)據(jù)元素直接移動(dòng)數(shù)據(jù)元素基本運(yùn)算基本運(yùn)算2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表基本運(yùn)算：刪除表基本運(yùn)算：刪除int DELETE (sequenlist L, int i) /* 從順序表中刪除第從順序表中刪除第

12、i個(gè)位置上的元素個(gè)位置上的元素 */ int j; if (iL-last+1) printf (“error”);return (0); /* 非法位置非法位置 */ else for (j=i;jlast; j+) /*第第i個(gè)結(jié)點(diǎn)下標(biāo)值是個(gè)結(jié)點(diǎn)下標(biāo)值是i 1*/ L-data(j-1)=L-dataj; /* 結(jié)點(diǎn)前移結(jié)點(diǎn)前移 */ L-last-; /* 表長減表長減1 */ return (1); /* DELETE */2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHO

13、OL OF TELECOMMUNICATIONS ENGINEERING 插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為 EIS= 線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為 EDE=2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表基本運(yùn)算：性能分析表基本運(yùn)算：性能分析插入刪除插入刪除算法分析算法分析1)+i -(np1+n1=iii)-n(qn1=ii2134 假設(shè)在線性表的任何位置上插入或刪除元素的概率相等，則假設(shè)在線性表的任何位置上插入或刪除元素的

14、概率相等，則pi=1/n+1，qi=1/n，故故 EIS= EDE=2n=1)+i -n(1+n11+n1=i21-n=i)-n(n1n1=iXidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例思考題：思考題：學(xué)生學(xué)籍檔案學(xué)生學(xué)籍檔案 問題表述及要求：問題表述及要求： 現(xiàn)有若干學(xué)生的學(xué)籍檔案信息，現(xiàn)有若干學(xué)生的學(xué)籍檔案信息，要求編寫一個(gè)應(yīng)

15、用軟件對(duì)其進(jìn)行日要求編寫一個(gè)應(yīng)用軟件對(duì)其進(jìn)行日常管理，以實(shí)現(xiàn)學(xué)生檔案信息的插常管理，以實(shí)現(xiàn)學(xué)生檔案信息的插入和刪除，并能根據(jù)學(xué)號(hào)查詢。入和刪除，并能根據(jù)學(xué)號(hào)查詢。學(xué)號(hào)學(xué)號(hào)姓姓 名名性別性別籍貫籍貫2222010010安安 紅紅女女上海上海2222002002劉建東劉建東男男天津天津2222001001王王 麗麗女女昆明昆明2222031031張立平張立平男男重慶重慶提示：提示： 將所有學(xué)生的檔案信息存放在一個(gè)順序表中，表中的每一個(gè)結(jié)點(diǎn)是將所有學(xué)生的檔案信息存放在一個(gè)順序表中，表中的每一個(gè)結(jié)點(diǎn)是一個(gè)學(xué)生的檔案信息；一個(gè)學(xué)生的檔案信息； 假設(shè)每個(gè)學(xué)生的數(shù)據(jù)包括以下內(nèi)容：學(xué)號(hào)、姓假設(shè)每個(gè)學(xué)生的數(shù)據(jù)包

16、括以下內(nèi)容：學(xué)號(hào)、姓 名、性別、籍貫；名、性別、籍貫； 表中結(jié)點(diǎn)按學(xué)生姓名的字典順序排列。表中結(jié)點(diǎn)按學(xué)生姓名的字典順序排列。2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 解答：解答： 數(shù)據(jù)定義數(shù)據(jù)定義 #define M 100 /* 順序表的最大長度順序表的最大長度 */ typedef struct /* 學(xué)生數(shù)據(jù)結(jié)點(diǎn)

17、類型學(xué)生數(shù)據(jù)結(jié)點(diǎn)類型 */ int number; char name20; char sex; char addr20; node; typedef struct /* 學(xué)生學(xué)籍表類型學(xué)生學(xué)籍表類型 */ node stuM; int last; /* 最后一個(gè)學(xué)生數(shù)據(jù)在表中的位置最后一個(gè)學(xué)生數(shù)據(jù)在表中的位置 */ sequenlist; sequenlist *L;2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEE

18、RING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 建立：從鍵盤輸入學(xué)生的學(xué)籍檔案信息，并存入順序表建立：從鍵盤輸入學(xué)生的學(xué)籍檔案信息，并存入順序表sequentlist* Creat () int i=0; sequentlist* L; node student; L=(sequentlist* )malloc( sizeof( sequentlist); /分配順序表空間分配順序表空間 L-last=-1; /建空建空表表 printf(“請(qǐng)輸入學(xué)生學(xué)籍檔案信息（以輸入學(xué)號(hào)請(qǐng)輸入學(xué)生學(xué)籍檔案信息（以輸入學(xué)號(hào)0結(jié)束）結(jié)束）n”); while (1

19、) printf(“輸入學(xué)號(hào)：輸入學(xué)號(hào)：”); scanf(“%d”, &student.number); if (0=student.number) /此處應(yīng)增加上溢異常情況處理此處應(yīng)增加上溢異常情況處理 break; printf(“輸入姓名輸入姓名 性別性別 地址：地址：”); scanf(“%s %c %s”, , &student.sex, &student.addr); L-stui+=student; L-last+; return L; /Creat2134XidianXidian University UniversitySCH

20、OOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 插入：按姓名的字典順序?qū)W(xué)生數(shù)據(jù)插入到檔案中插入：按姓名的字典順序?qū)W(xué)生數(shù)據(jù)插入到檔案中 void Input(sequentlist *L, node student) int i, j, n=0; /此處應(yīng)增加上此處應(yīng)增加上溢溢異常情況處理異常情況處理 for (i=0;ilast;i+) if (strcmp(, L-stui.

21、name)last;j=i;j-) L-stuj+1=L-stuj; L-stui=student; L-last+; return; /Input2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 刪除：根據(jù)輸入的學(xué)生學(xué)號(hào)刪除相應(yīng)數(shù)據(jù)刪除：根據(jù)輸入的學(xué)生學(xué)號(hào)刪除相應(yīng)數(shù)據(jù) int Delete(sequenlist *L, in

22、t n) int i, j; for (i=0; ilast; i+) if (L-stui.number=n) break; if (iL-last) printf(“Not found!n”); return (0); else for (j=i+1; jlast; j+) L-stuj-1=L-stuj; L-last-; reture (1); /Delete2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEER

23、ING2. .線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 查詢：根據(jù)輸入的學(xué)生姓名查詢學(xué)生的檔案信息查詢：根據(jù)輸入的學(xué)生姓名查詢學(xué)生的檔案信息int Locate(sequenlist *L, char *string) int i; for (i=0; ilast; i+) if (strcmp(L-, string)=0) printf(“n Number:%6d”,L-stui.number); printf(“n Name:%s”,L-); printf(“n Sex:%c”,L-stui.sex); printf(

24、“n Address:%s”,L-stui.address); return (1); if (iL-last) printf(“Not found!n”; return (0); /Locate2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 輸出：輸出所有學(xué)生的檔案信息輸出：輸出所有學(xué)生的檔案信息void Output(s

25、equenlist *L) int i; printf(“Number Name Sex Addressn”); for (i=0; ilast; i+) printf(“%6d %s”,L-stui.number,L-); printf(“%c %sn”,L-stui.sex,L-stui.address); /Output2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順

26、序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表實(shí)際應(yīng)用舉例表實(shí)際應(yīng)用舉例 主函數(shù)主函數(shù)void Main() /請(qǐng)大家自己請(qǐng)大家自己補(bǔ)充補(bǔ)充 /Main2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING2.2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)順序順序表性能分析表性能分析順序表的優(yōu)缺點(diǎn)順序表的優(yōu)缺點(diǎn)缺點(diǎn)缺點(diǎn)u 在做插入或刪除運(yùn)算時(shí)，需移動(dòng)大量元素在做插入或刪除運(yùn)算時(shí)，需移動(dòng)大量元素；u 線性表按最大空間預(yù)先分配

27、線性表按最大空間預(yù)先分配；u 表的容量難以擴(kuò)充表的容量難以擴(kuò)充。優(yōu)點(diǎn)優(yōu)點(diǎn)u 隨機(jī)存取表中任意元素隨機(jī)存取表中任意元素；u 存儲(chǔ)位置可用一個(gè)簡單直觀的公式表示；存儲(chǔ)位置可用一個(gè)簡單直觀的公式表示；u 存儲(chǔ)密度高。存儲(chǔ)密度高。2134XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING思考問題思考問題順序表建表需要使用順序表建表需要使用malloc和和free函數(shù)么？函數(shù)么？解答：順序表建表時(shí)也要解答：順序表建表時(shí)也要分配空

28、間分配空間兩種方式：兩種方式：定義為局部變量定義為局部變量 或者或者 malloc和和free typedef int datatype; #define maxsize 1024 typedef struct datatype datamaxsize; int last; sequenlist;XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING思考問題思考問題int InitList(sequenlist * L)

29、int num, i; printf(please input no.:n); /輸入元素的個(gè)數(shù)輸入元素的個(gè)數(shù) scanf(%d, &num); if (numMAXSIZE) printf(input error!n);return (-1); L = (sequenlist *)malloc( sizeof (sequenlist); /為為L分配內(nèi)存空間分配內(nèi)存空間 if (L=NULL) printf(malloc memory error!);return (-1); printf(please input L ( %d elements):n, num); /輸入數(shù)據(jù)元素內(nèi)

30、容輸入數(shù)據(jù)元素內(nèi)容 for (i=0; idatai); L-last = i-1; return (0);XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING算法復(fù)雜性概念及分析（教材1.31.3節(jié)）算法的優(yōu)劣是由算法復(fù)雜性決定的算法的優(yōu)劣是由算法復(fù)雜性決定的 算法復(fù)雜性越高，算法越差算法復(fù)雜性越高，算法越差算法復(fù)雜性只依賴于以下元素：算法復(fù)雜性只依賴于以下元素： 待解決問題的規(guī)模待解決問題的規(guī)模 算法的輸入算法的輸入

31、 算法本身算法本身考察算法復(fù)雜性一般可以考慮三種情況：考察算法復(fù)雜性一般可以考慮三種情況： 最壞情況最壞情況 最好情況最好情況 平均情況平均情況算法是否關(guān)注復(fù)雜性取決于實(shí)際需算法是否關(guān)注復(fù)雜性取決于實(shí)際需求：求：-只只運(yùn)行一兩次的程序運(yùn)行一兩次的程序, ,不必很高不必很高效效, ,易易于于編程即編程即可。可。-多次多次反復(fù)運(yùn)行的程序反復(fù)運(yùn)行的程序, , 則要求高則要求高效效, ,寧可寧可編程時(shí)候多花費(fèi)時(shí)間編程時(shí)候多花費(fèi)時(shí)間, ,將來將來多次多次運(yùn)行可以節(jié)省大量運(yùn)行可以節(jié)省大量時(shí)間。時(shí)間。TipsTips：XidianXidian University UniversitySCHOOL OF T

32、ELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING算法復(fù)雜性概念及分析由于無法對(duì)規(guī)模由于無法對(duì)規(guī)模N N的每一種輸入的每一種輸入I I都統(tǒng)計(jì)出對(duì)應(yīng)的復(fù)雜性函數(shù)值，因此都統(tǒng)計(jì)出對(duì)應(yīng)的復(fù)雜性函數(shù)值，因此一般只考慮問題規(guī)模一般只考慮問題規(guī)模，即以，即以T T（N N）來評(píng)價(jià)算法）來評(píng)價(jià)算法一般來說一般來說T(N)T(N)隨隨N N單調(diào)增加，且有當(dāng)單調(diào)增加，且有當(dāng)N N時(shí)，時(shí)，T(N)T(N)。如果存在。如果存在(N)(N)，使得當(dāng)，使得當(dāng)N N 時(shí)，有時(shí)，有(T(N)- (T(N)- (N)/T(N) (N)/T

33、(N) 0 0，那么，那么(N)(N)是是T(N)T(N)當(dāng)當(dāng)N N 時(shí)的時(shí)的漸近性態(tài)漸近性態(tài)，或稱，或稱(N)(N)為算法當(dāng)為算法當(dāng)N N 時(shí)的時(shí)的漸近復(fù)漸近復(fù)雜性雜性。 (N)(N)是是T(N)T(N)中略去低階項(xiàng)所留下的主項(xiàng)中略去低階項(xiàng)所留下的主項(xiàng) 由于當(dāng)由于當(dāng)N N時(shí)，時(shí)，T(N)T(N)趨近于趨近于(N)(N) ，所以可用，所以可用(N)(N)代替代替T(N)T(N)作為算法作為算法的復(fù)雜性度量的復(fù)雜性度量進(jìn)一步考慮：比較算法的效率只需要確定其進(jìn)一步考慮：比較算法的效率只需要確定其復(fù)雜性的階復(fù)雜性的階就可以了?？删涂梢粤??？梢灾豢紤]以只考慮(N)(N)的階，而不考慮其常數(shù)因子。的階，

34、而不考慮其常數(shù)因子。XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING算法復(fù)雜性概念及分析定義：定義： 設(shè)設(shè)f(N)f(N)和和g(N)g(N)是定義在正數(shù)集上的正函數(shù)。如果存在常數(shù)是定義在正數(shù)集上的正函數(shù)。如果存在常數(shù)C C和自然數(shù)和自然數(shù)N N0 0，使得當(dāng)使得當(dāng)NNNN0 0時(shí)，有時(shí)，有f(N) f(N) C Cg g(N)(N)，則稱，則稱函數(shù)函數(shù)f(N)f(N)當(dāng)當(dāng)N N充分大時(shí)有上界充分大時(shí)有上界，且且g(

35、N)g(N)是它的一個(gè)是它的一個(gè)上界上界，記為，記為f(N)=O(g(N)f(N)=O(g(N)。這時(shí)我們還說。這時(shí)我們還說f(N)f(N)的階不的階不高于高于g(N)g(N)的階的階。下界下界定義相似，記為定義相似，記為f(N)=f(N)=(g(N)(g(N)。 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)f(n)= O(g(N)f(n)= O(g(N)且且f(N)=f(N)=(g(N)(g(N)，則稱，則稱f(N)f(N)和和g(N)g(N)同階同階，記為，記為f(N)=f(N)=(g(N)(g(N)。 如果對(duì)任意給定的如果對(duì)任意給定的00，都存在正整數(shù)，都存在正整數(shù)N N0 0，使得當(dāng)，使得當(dāng)N N NN0 0時(shí)，

36、有時(shí)，有f(N)/g(N)f(N)/g(N)，則稱，則稱函數(shù)函數(shù)f(N)f(N)當(dāng)當(dāng)N N充分大時(shí)充分大時(shí)的階比的階比g(N)g(N)低低，記為，記為f(N)=O(g(N)f(N)=O(g(N)。XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING算法復(fù)雜性概念及分析空間復(fù)雜性空間復(fù)雜性存儲(chǔ)空間的固定部分：程序指令代碼的空間，常數(shù)、簡單變量、定長成分變量所占空間存儲(chǔ)空間的固定部分：程序指令代碼的空間，常數(shù)、簡單變量、定長

37、成分變量所占空間?？勺儾糠郑撼叽缗c實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用的空可變部分：尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用的空間、在動(dòng)態(tài)內(nèi)存區(qū)所申請(qǐng)和釋放的空間。間、在動(dòng)態(tài)內(nèi)存區(qū)所申請(qǐng)和釋放的空間。時(shí)間復(fù)雜性時(shí)間復(fù)雜性編譯時(shí)間編譯時(shí)間運(yùn)行時(shí)間：程序步驟運(yùn)行時(shí)間：程序步驟通常情況下，我們主要考慮時(shí)間復(fù)雜性通常情況下，我們主要考慮時(shí)間復(fù)雜性XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS EN

38、GINEERING算法復(fù)雜性概念及分析常見的時(shí)間復(fù)雜性按照遞增排序有：常見的時(shí)間復(fù)雜性按照遞增排序有： 常數(shù)階常數(shù)階O(1)O(1) 對(duì)數(shù)階對(duì)數(shù)階O(logO(log2 2n)n) 線性階線性階O(n)O(n) 線性對(duì)數(shù)階線性對(duì)數(shù)階O(nlogO(nlog2 2n)n) 平方階平方階O(nO(n2 2) ) 立方階立方階O(nO(n3 3) ) K K次方階次方階O(O(n nk k) ) 指數(shù)階指數(shù)階O(2O(2n n) )XidianXidian University UniversitySCHOOL OF TELECOMMUNICATIONS ENGINEERINGSCHOOL OF TELECOMMUNICATIONS ENGINEERING算法復(fù)雜性概念及分析常見的時(shí)間復(fù)雜性按照遞增排序有：常見的時(shí)間復(fù)雜性按照遞增排序有：XidianXidian University UniversitySCHOOL OF TELECOMMUNICAT