數(shù)據(jù)結(jié)構(gòu)緒論課件-資料下載頁
2024-08-31 09:01本頁面
【導(dǎo)讀】第1卷和第3卷中有詳細的描述。瑞士科學(xué)家Wirth在其著作中這樣描述：。例1：計算機管理圖書目錄問題。例2：人機對弈問題。通過以上例子可以看出，這些問題不。目表，對弈樹等帶結(jié)構(gòu)的數(shù)據(jù)來描述。數(shù)據(jù)結(jié)構(gòu)要解決的問題：分析實際問。題，從中抽象出一個適當?shù)臄?shù)學(xué)模型；加以考慮和處理。項又稱為字段或域。數(shù)據(jù)元素之間的邏輯關(guān)系，即邏。數(shù)據(jù)在機內(nèi)的存儲形式，即存儲。由此問題相關(guān)的一定輸入，計算機。一系列運算，是指令的有窮序列。本書將采用類C語言描述算法。類C語言是標準C語言的簡化，與標準C. 的執(zhí)行并給出表示出錯信息的字符串。問題的規(guī)模大小有關(guān)。中所有語句執(zhí)行次數(shù)之和。的極限情況，一般簡稱為時間復(fù)雜性。的字頭，f為函數(shù)形式，如T=O。當T為多項式時,可只取其最高次。解：以上三條單個語句均執(zhí)行1次，計算下面求累加和程序段的時間復(fù)雜性
【正文】 =2n2+n+1 =O(n2) 返 例 ? 計算下面求累加和程序段的時間復(fù)雜性 for(i=1。in。i++) (n次） for(i=1。i=n。i++) （ n*n次 ） if a[j]a[i] (n*n次 ） { t=a[i]。 a[i]=a[j]。 a[j]=t } (3n2次 ） ? 解： T(n)=3n2+n =O(n2) 小 結(jié) ? 本章介紹了貫穿全書的基本概念和 基本思想。 – 數(shù)據(jù) – 數(shù)據(jù)結(jié)構(gòu) ? 邏輯結(jié)構(gòu) ? 物理結(jié)構(gòu) – 算法 – 算法的時間復(fù)雜性 返回 習(xí)題與練習(xí) ? 一、名詞解釋 數(shù)據(jù) 數(shù)據(jù)項 數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)邏輯結(jié)構(gòu) 數(shù)據(jù)物理結(jié)構(gòu) 算法 算法的時間復(fù)雜性 有關(guān)時間復(fù)雜度的幾個常用量 ? 二、簡答 – 1. 算法分析的目的是什么？ – 2. 什么是算法的最壞和平均時間復(fù)雜性？ ? 三、分析下列算法的時間復(fù)雜性 : – 1． sum=0。 for (i=1。i=n。i++) { sum=sum+i。 } – 2． i=1。 while(i=n) i=i*10。 – 3． sum=0。 for(i=0。in。i++) for(j=0。jn。j++) sum=sum+Array[i][j]。 返回
高考資料相關(guān)推薦
鄂ICP備17016276號-1