數(shù)據(jù)結(jié)構(gòu)--第一章-緒論-資料下載頁
2025-01-18 19:01本頁面
【正文】 不是針對實(shí)際執(zhí)行時間的精確地算出算法執(zhí)行具體時間，而是針對算法中語句的執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。 56 語句頻度 ? 定義： 語句頻度是指該語句在一個算法中重復(fù)執(zhí)行的次數(shù)。 例如： 兩個矩陣相乘 算法語句 對應(yīng)的語句頻度 1 for（ i=0； i n。i++） n 2 for （ j=0； jn。j++） n2 3 {c[i][j]=0。 n2 4 for (k=0。k n。 k++) n3 c[i][j]=c[i][j]+a[i][k]*b[k][j]。 n3 } 總執(zhí)行次數(shù)： Tn=2n3+2n2 +n 57 算法的時間復(fù)雜度 算法的時間復(fù)雜度，即是算法的時間量度記做： T(n)=O(f(n)) 例如給出 X=X+1 （ 1） x=x+1 ；時間復(fù)雜度為 O(1)， 稱為常量階； （ 2） for (i=1。 i= n。 i++) x=x+1。 時間復(fù)雜度為 O(n)， 稱為線性階； （ 3） for (i=1。 i= n。 i++) for (j=1。j= n。 j++) x=x+1。 時間復(fù)雜度為 O(n2), 稱為平方階。 58 常用的時間復(fù)雜度頻率計數(shù) ? 數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度頻率計數(shù)有 7個 : O(1) 常數(shù)型 O(n)線性型 O(n2)平方型 O(n3)立方型 O(2n)指數(shù)型 O(log2n)對數(shù)型 O(nlog2n)二維型 按時間復(fù)雜度由小到大排列的頻率表： 59 常用的時間復(fù)雜度頻率計數(shù) ? 常用的時間復(fù)雜度頻率表： log2n n nlog2n n2 n3 2n 一般講：前3種可實(shí)現(xiàn)，后 3種雖理論上是可實(shí)現(xiàn)的，實(shí)際上只有對 N限制在很小范圍才有意義，當(dāng) N較大時，不可能實(shí)現(xiàn)。 0 1 0 1 1 2 1 2 2 4 8 4 2 4 8 16 64 16 3 8 24 64 512 256 4 16 64 256 5096 65536 5 32 160 1024 32768 2147483648 60 最壞時間復(fù)雜度 ? 定義： 討論算法在最壞情況下的時間復(fù)雜度，即分析最壞情況下以估計出算法執(zhí)行時間的上界。 例如冒泡排序算法 61 void bubble(int a[], int length) {將 a中整數(shù)數(shù)組重新排序 ， 達(dá)到遞增有序 } int i=0, j, temp。 int change 。 do{ change=false 。 for(j=1。jlengthi。j++) if( a[j]a[j+1]) { temp= a[j]。 a[j]=a[j+1]。 a[j+1]=temp。 change=true。 } i=i+1 。 } while(ilength || change==true ) } 最壞時間復(fù)雜度 62 算法的空間復(fù)雜度 ? 定義： 用空間復(fù)雜度作為算法所需存儲空間的量度， 記做： S(n)=O(f (n)) 。 63 關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)課程地位 ? 數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn) ? 關(guān)于本書內(nèi)容編寫說明 64 數(shù)據(jù)結(jié)構(gòu)課程地位 ? 數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖： 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)庫 人工智能 專業(yè)基礎(chǔ)課 操作系統(tǒng) 編譯原理 非線性程序設(shè)計 離散數(shù)學(xué) 語言程序設(shè)計 計算機(jī)原理設(shè)計 65 數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn) ? 教學(xué)目標(biāo) ： 學(xué)會分析數(shù)據(jù)對象的特征，掌握數(shù)據(jù)組織方法和計算機(jī)的表示方法，以便為應(yīng)用所涉及數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時間空間分析的技巧，培養(yǎng)良好的程序設(shè)計技能。 ? 學(xué)習(xí)方法 ： 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，必須經(jīng)過大量的實(shí)踐，在實(shí)踐中體會構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計的技術(shù)。 66 關(guān)于本書內(nèi)容編寫說明 ? 本書基本結(jié)構(gòu) 第一部分：數(shù)據(jù)結(jié)構(gòu)的基本概念 （ 第 1章 ） 第二部分：基本的數(shù)據(jù)結(jié)構(gòu) 包括：線性結(jié)構(gòu) —線性表 、 棧和隊列 、 串 、 數(shù)組與廣義表 （ 第 2—5章 ） 非線性結(jié)構(gòu) —樹 、 圖 （ 第 7章 ） 第三部分：基本技術(shù) 包括：查找技術(shù)與排序技術(shù)（第 10章）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1