數(shù)據(jù)結(jié)構(gòu)緒論-資料下載頁
2025-08-01 15:06本頁面
【正文】 三、算法效率 的衡量方法和準(zhǔn)則 事前分析估算法 事后統(tǒng)計(jì)法 缺點(diǎn)： 1．必須執(zhí)行程序 2．其它因素掩蓋算法本質(zhì) 和算法執(zhí)行時(shí)間相關(guān)的因素： ? 算法選用的策略 ? 問題的規(guī)模（如：求 100以內(nèi)還是 1000以內(nèi)的素?cái)?shù) ). ? 編寫程序的語言 ? 編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 ? 計(jì)算機(jī)執(zhí)行指令的速度 一個(gè) 特定 算法的運(yùn)行工作量 的大小，只依賴于 問題的規(guī)模 （通常用整數(shù)量 n表示），或者說， 它是問題規(guī)模 n的函數(shù)。 假如 ， 隨著問題規(guī)模 n的增長 ， 算法執(zhí)行時(shí)間的增長率 T(n)和 問題規(guī)模 n的的函數(shù) f(n)的增長率相同 ， 則可記作： T(n) = O(f(n)) 稱 T(n) 為算法的 (漸近 )時(shí)間復(fù)雜度 如何 估算 算法的時(shí)間復(fù)雜度呢？ 算法的頻度 : f(n) = n + n*n+ n2 + n2 *n + n3 = 2n3 + 2n2 + n for (i=1。 i=n。 ++i) for (j=1。 j=n。 ++j) { c[i,j] = 0。 for (k=1。 k=n。 ++k) c[i,j] += a[i,k]*b[k,j]。 } 求兩個(gè) n階矩陣的乘積 n n*n n2 n2 *n n3 void s_s(int a[], int n) { for ( i = 0。 i n1。 ++i ) { j = i。 //選擇第 I個(gè)最小元素 for ( k = i+1。 k n。 ++k ) if (a[k] a[j] ) j = k。 if ( j != i ) a[j] ←→ a[i] } // s_s ?常見的時(shí)間復(fù)雜度： O(1)：常量階 O(n)：線性階 O(n2)：平方階 O(logn)：對(duì)數(shù)階 O(2n)：指數(shù)階 算法的 空間復(fù)雜度 S(n) = O(g(n)) 表示隨著問題規(guī)模 n的增大 ， 算法運(yùn)行所需存儲(chǔ)量的增長率 S(n)與 g(n)的增長率相同 。 空間復(fù)雜度 2. 程序本身所占空間； 3. 輔助變量所占空間； 1. 輸入數(shù)據(jù)所占空間 。 算法的存儲(chǔ)量包括： 本章學(xué)習(xí)要點(diǎn) 熟悉各名詞、術(shù)語的含義，掌握基本概念。 理解 ADT的意義。 理解算法五個(gè)要素的確切含義。 掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法。 算法的表示與實(shí)現(xiàn)。 練習(xí)題： ?簡述下列術(shù)語：數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型。 ?簡述抽象數(shù)據(jù)類型的兩個(gè)重要特征以及這兩個(gè)重要特征的意義。 ?簡述四種邏輯結(jié)構(gòu)、兩種主要的數(shù)據(jù)關(guān)系映象。 ?分析一下冒泡排序的時(shí)間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 答案： A 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是 答案： C 對(duì)于給定的 n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有 ⑴ 、 ⑵ 、 ⑶ 、 ⑷ 四種。 答案： ⑴ 集合 ⑵ 線性結(jié)構(gòu) ⑶ 樹結(jié)構(gòu) ⑷ 圖結(jié)構(gòu)
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1