數(shù)據(jù)結(jié)構(gòu)--第一章-緒論(參考版)
2025-01-21 19:01本頁面
【正文】 ? 學(xué)習(xí)方法 ： 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，必須經(jīng)過大量的實(shí)踐，在實(shí)踐中體會構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計的技術(shù)。 } while(ilength || change==true ) } 最壞時間復(fù)雜度 62 算法的空間復(fù)雜度 ? 定義： 用空間復(fù)雜度作為算法所需存儲空間的量度， 記做： S(n)=O(f (n)) 。 change=true。 a[j]=a[j+1]。jlengthi。 do{ change=false 。 例如冒泡排序算法 61 void bubble(int a[], int length) {將 a中整數(shù)數(shù)組重新排序 ， 達(dá)到遞增有序 } int i=0, j, temp。 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)。 j++) x=x+1。 i++) for (j=1。 時間復(fù)雜度為 O(n)， 稱為線性階； （ 3） for (i=1。 i= n。 k++) n3 c[i][j]=c[i][j]+a[i][k]*b[k][j]。 n2 4 for (k=0。i++） n 2 for （ j=0； jn。 56 語句頻度 ? 定義： 語句頻度是指該語句在一個算法中重復(fù)執(zhí)行的次數(shù)。 ? 關(guān)于算法執(zhí)行時間 ? 語句頻度 ? 算法的時間復(fù)雜度 ? 數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度頻率計數(shù) ? 最壞時間復(fù)雜度 ? 算法的空間復(fù)雜度 55 關(guān)于算法執(zhí)行時間 ? 定義 ： 一個算法的執(zhí)行時間大致上等于其所有語句執(zhí)行時間的總和，對于語句的執(zhí)行時間是指該條語句的執(zhí)行次數(shù)和執(zhí)行一次所需時間的乘積。 54 有關(guān)數(shù)量關(guān)系計算 數(shù)量關(guān)系評價體現(xiàn)在時間 ——算法在機(jī)器中所耗費(fèi)時間 。 ? 性能評價 ? 有關(guān)數(shù)量關(guān)系計算 53 性能評價 ? 定義： 對問題規(guī)模與該算法在運(yùn)行時所占的空間 S與所耗費(fèi)的時間 T給出一個數(shù)量關(guān)系的評價 。} 對 C語言作以下描述： ?do –while 語句 do { 循環(huán)體語句 }while (條件表達(dá)式 ） do{i。i++) { k=i+1。 default printf(“錯誤”）； break。] } 對 C語言作以下描述： 48 ?eg： switch (B) {case 0: printf(“請輸入 0”） ； break。 break。 case 判斷值 2: 語句組 2； break。 else k。 if(ab) k++。 if (ab) k++。 （ 2） 串聯(lián)賦值 〈 變量 1〉 =〈 變量 2〉 =〈 變量 3〉 =… =〈 變量 k〉 =〈 表達(dá)式 〉 eg: a=b=c=d= …=k+1。 2） 〈 變量 〉 ++， eg: i++。 } /*函數(shù)名 */ else return b。 41 類描述算法的語言選擇 ? 類語言 ： 類語言是接近于高級語言而又不是嚴(yán)格的高級語言，具有高級語言的一般語句設(shè)施，撇掉語言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。 是算法在計算機(jī)中的實(shí)現(xiàn) 。 } 38 算法描述的工具 ? 概述： 算法 +數(shù)據(jù)結(jié)構(gòu) =程序 ? 算法、語言、程序的關(guān)系 ? 設(shè)計實(shí)現(xiàn)算法過程步驟 ? 類描述算法的語言選擇 39 算法、語言、程序的關(guān)系 1. 算法 ：描述了數(shù)據(jù)對象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）。i++） { scanf(%f, x)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1