[工學]數(shù)據(jù)結構課件c版第一章(參考版)
2024-10-22 00:03本頁面
【正文】 用試探法： n = 13時， 100n2 = 16900 2n = 8192 n = 14時， 100n2 = 19600 2n = 16384 n = 15時， 100n2 = 22500 2n = 32764 取 n = 15 滿足要求。通常，只有完成同一功能的幾個算法之間才具有可比性。 a[j] = tmp。 j) //ni次比較 if (a[j1] a[j]) { int tmp = a[j1]。 i++) { //n1趟 for (int j = n1。 } 漸進時間復雜度為 O(max (m*n, m)) Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 例：起泡排序 void bubbleSort (int a[ ], int n ) { //對表 a[ ] 逐趟比較 , n 是表當前長度 for (int i = 1。 i m。 j++) sum[i] += x[i][j]。 //數(shù)據(jù)累加 for (int j = 0。 i m。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 例：兩個并列循環(huán)的例子 void exam (float x[ ][ ], int m, int n) { float sum [ ]。 j++ ) y ++。 i++ ) T3(n) = O(n2) for ( int j = 0。 for ( int i = 0。 k n。 y = 0。則時間復雜度 T(n) 是問題規(guī)模 n 的函數(shù)。 1 1 1 } 0 1 0 總程序步數(shù) 3n+4 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ? 算法的漸進分析 算法的漸進分析直接與它所求解的問題的規(guī)模 n相關，通常將問題規(guī)模作為分析的參數(shù)，求算法的時間和空間開銷與問題規(guī)模 n的關系。 i++) 2 n+1 2(n+1) s = s + a[i]。 1 1 1 for (int i = 0。 } Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 注意 ： 一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。 i++) count += 3。 } 執(zhí)行結束得程序步數(shù) count = 3*n+4 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 為統(tǒng)計程序步，程序的簡化形式： void sum (float a[ ], int n) { for (int i = 0。 //針對 for 的最后一次 count++。 count++。 i++) { count += 2。 //count 統(tǒng)計執(zhí)行語句條數(shù) for (int i = 0。 } Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 在求累加和程序中加入 count 語句 float sum (float a[ ], int n) { float s = 。 i++) s = s + a[i]。 for (int i = 0。 ? b) 建表，列出各語句的程序步。 表達式：程序步數(shù)為 1。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ?空間復雜度度量 ?存儲空間的固定部分 程序指令代碼的空間，常數(shù)、簡單變量、定長成分 (如數(shù)組元素、結構成分、對象的數(shù)據(jù)成員等 )變量所占空間 ?可變部分 尺寸與實例特性有關的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過 new和delete命令動態(tài)使用空間 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ? 時間復雜度度量 ? 程序步的概念 程序步：語法上或語義上有意義的一段指令序 列，而且這段指令序列的執(zhí)行時間與問題規(guī)模 無關。記為 S(n)。當 n??時的時間復雜性，稱為漸進時間復雜性。 Data Structure— Ch1 Introduction 2021/11/10
教學課件相關推薦
鄂ICP備17016276號-1