數(shù)據(jù)結(jié)構(gòu)ppt教案(清華大學(xué))ds-資料下載頁
2025-10-10 19:45本頁面
【正文】 法中所有語句的頻度之和是 矩陣階數(shù) n的函數(shù) T(n) = 3n3 + 5n2 + 4n +2 ? 一般地，稱 n 是問題的規(guī)模。則時(shí)間復(fù)雜度 T(n) 是問題規(guī)模 n 的函數(shù)。 ? 當(dāng) n趨于無窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度 T(n) = O(n3) ─ 大 O表示法 61 ? 加法規(guī)則 針對(duì)并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) ? 各種函數(shù)的增長趨勢(shì) c log2n n nlog2n n2 n3 2n 3n n! 62 T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2) 變量計(jì)數(shù) for ( int i = 0。 i n。 i++ ) for ( int j = 0。 j n。 j++ ) y ++。 T1 (n) = O(1) T2(n) = O(n) T3(n) = O(n2) x = 0。 y = 0。 for ( int k = 0。 k n。 k ++ ) x ++。 63 ? 乘法規(guī)則 針對(duì)嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)) ? 漸進(jìn)的空間復(fù)雜度 S (n) = O(f (n)) ? 兩個(gè)并列循環(huán)的例子 64 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。 } 漸進(jìn)時(shí)間復(fù)雜度為 O(max (m*n, m)) 65 起泡排序 void bubbleSort (int a[ ], int n ) { //對(duì)表 a[ ] 逐趟比較 , n 是表當(dāng)前長度 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。 } //一趟比較 } } 66 漸進(jìn)時(shí)間復(fù)雜度 O(f (n)*g (n)) = O(n2) ??????11 21ni)n( ni)(n?BubblrSort 外層循環(huán) n1 趟 內(nèi)層循環(huán) ni 次比較 67 ? 有時(shí) , 算法的時(shí)間復(fù)雜度不僅依賴于問題規(guī)模 n，還與輸入實(shí)例的初始排列有關(guān)。 ? 在數(shù)組 A[n] 中查找給定值 k 的算法： int i = n1。 while (i = 0 amp。amp。 A[i] != k) i。 return i。 ? 算法的語句 i 的頻度不僅與 n 有關(guān)，還與 A[ ] 中各元素的取值 以及 k 的取值 有關(guān)。 68 ? 例：設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為 100n2 和 2n，問：要使前者快于后者， n 至少要取多大？ 解答： 問題是找出滿足 100n2 = 2n 的最小的 n。用試探法： n = 13時(shí)， 100n2 = 16900 2n = 8192 n = 14時(shí)， 100n2 = 19600 2n = 16384 n = 15時(shí)， 100n2 = 22500 2n = 32764 取 n = 15 滿足要求。 69 出錯(cuò)處理問題舉例 ? 試編寫一個(gè)函數(shù)計(jì)算 n!*2n 的值，結(jié)果存放于數(shù)組 A[n] 的第 i 個(gè)數(shù)組元素中 (0 ? i ? n) ? 若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為 maxInt，則當(dāng) i arraySize 或者對(duì)于某一個(gè) k ( 0 ? k ? n )，使得 k!*2k maxInt 時(shí)，應(yīng)按出錯(cuò)處理。 70 可有如下幾種不同的出錯(cuò)處理方式： ① 用 cerr 及 exit (1) 語句來終止執(zhí)行并報(bào)告錯(cuò)誤； ② 用返回整數(shù)函數(shù)值 0, 1 來實(shí)現(xiàn)算法 ， 以區(qū)別是正常返回還是錯(cuò)誤返回； ③ 在函數(shù)的參數(shù)表設(shè)置一個(gè) 引用型 的整型變量來區(qū)別是正常返回還是某中錯(cuò)誤返回 。 ④ 拋出異常 。 71 include define n 100 define maxInt 0x7fffffff bool calc (int T[ ], int n) { int i, value = 1。 if ( n != 0 ) { for (i = 1。 i n。 i++) { value *= i * 2。 if (value maxInt / n / 2) return false。 } //直接判斷 i!*2i MaxInt 是危險(xiǎn)的 value *= n * 2。 } 72 T[n] = value。 //n!*2n ? T[n] return true。 } void main ( ) { int A[n], i。 for (i = 0。 i n。 i++) if (!calc (A, i)) { cout failed at i endl。 break。 } }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1