[工學]數(shù)據(jù)結構課件c版第一章-資料下載頁
2024-10-19 00:03本頁面
【正文】 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 當 n趨于無窮大時，把時間復雜度的數(shù)量級（階）稱為算法的漸進時間復雜度 T(n) = O(n3) ─ 大 O表示法 ? 加法規(guī)則 針對并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) 各種函數(shù)的增長趨勢 c log2n n nlog2n n2 n3 2n 3n n! Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 例：有如下程序段 x = 0。 y = 0。 T1 (n) = O(1)； for ( int k = 0。 k n。 k ++ ) T2(n) = O(n)； x ++。 for ( int i = 0。 i n。 i++ ) T3(n) = O(n2) for ( int j = 0。 j n。 j++ ) y ++。 T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2) Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ?乘法規(guī)則 針對嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)) 任何非 0正常數(shù)都屬于同一數(shù)量級，記 O(1)。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 例：兩個并列循環(huán)的例子 void exam (float x[ ][ ], int m, int n) { float sum [ ]。 for (int i = 0。 i m。 i++) { //x中各行 sum[i] = 。 //數(shù)據(jù)累加 for (int j = 0。 j n。 j++) sum[i] += x[i][j]。 } for (i = 0。 i m。 i++) //打印各行數(shù)據(jù)和 cout i “ : ” sum [i] endl。 } 漸進時間復雜度為 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 = n1。 i++) { //n1趟 for (int j = n1。 j = i。 j) //ni次比較 if (a[j1] a[j]) { int tmp = a[j1]。 a[j1] = a[j]。 a[j] = tmp。 } //一趟比較 } } Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 漸進時間復雜度 O(f (n)*g (n)) = O(n2) BubblrSort 外層循環(huán) n1 趟 內層循環(huán) ni 次比較 ??????11 21ni)n ( ni)(n?Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ? 空間復雜度的漸進表示法 S (n) = O(f (n)) 計算解決問題所需的輔助存儲空間。通常，只有完成同一功能的幾個算法之間才具有可比性。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 例：設有兩個算法在同一機器上運行，其執(zhí)行時間分別為 100n2 和 2n，問：要使前者快于后者， n 至少要取多大？ 解答： 問題是找出滿足 100n2 2n 的最小的 n。用試探法： n = 13時， 100n2 = 16900 2n = 8192 n = 14時， 100n2 = 19600 2n = 16384 n = 15時， 100n2 = 22500 2n = 32764 取 n = 15 滿足要求。
教學課件相關推薦
鄂ICP備17016276號-1