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