[計(jì)算機(jī)]2005241095-ch-資料下載頁(yè)
2025-10-10 03:38本頁(yè)面
【正文】 ++i) for (j=1。 j=n。 ++j){ c[i][j]=0。 for (k=1。 k=n。 ++k) c[i][j]=c[i][j]+a[i][k]*b[k][j]。 } 原操作 基本操作的重復(fù)執(zhí)行次數(shù)： n3 例 : 矩陣相乘算法 矩陣相乘算法的時(shí)間量度記作： T(n)=O(n3) 稱 O(n3)為該算法的 (漸近 )時(shí)間復(fù)雜度 。 asymptotic time plexity 它表示： 當(dāng) n較大時(shí)， T(n)與 n3成正比； 當(dāng) n較大時(shí)， T(n)與 n3是同一數(shù)量級(jí)的； 隨著 n的增長(zhǎng)， T(n)和 n3的增長(zhǎng)率相同。 T(n) = O( f (n) ) 其中： n —— 問題的規(guī)模，如：矩陣的階，線性表的長(zhǎng)度，樹中的結(jié)點(diǎn)數(shù)，圖中的頂點(diǎn)數(shù)等。 算法的時(shí)間復(fù)雜度 f(n)—— n 的某個(gè)函數(shù)，通常表示算法中基本操作的重復(fù)執(zhí)行次數(shù) 。 O(1) O(n) O(n2) O(n3) 常量階 線性階 平方階 立方階 指數(shù)階 對(duì)數(shù)階 O(2n) O(log2n) O(n?log2n) O(f(n)+g(n))=O(max(f(n),g(n))) O(cf(n))=O(f(n)) 運(yùn)算法則： 當(dāng) n充分大時(shí)， log2nnn?log2nn2n32n 常見函數(shù)的增長(zhǎng)率 時(shí)間復(fù)雜度的估算 為了估算給定算法的時(shí)間復(fù)雜度，需要求出算法中基本操作的重復(fù)執(zhí)行次數(shù) 。多數(shù)情況下，基本操作是最深層循環(huán)體中的原操作，其重復(fù)執(zhí)行次數(shù)和包含它的 語(yǔ)句的頻度 相同。 語(yǔ)句的重復(fù)執(zhí)行次數(shù) for (i=2。 i=n。 ++i) for (j=2。 j=i1。 ++j){ ++x。 a[i][j]=x。} 例 語(yǔ)句 ++x 的頻度： 1+2+… +(n2) = (n1)(n2)/2 T(n) = O((n1)(n2)/2) ? 1 2 (n1)(n2)/2 n2 lim n?? = ? 1 2 3 2 n2 n+1) = O(n2) = O( 時(shí)間復(fù)雜度的估算 提示一：多數(shù)情況下，可以把算法中語(yǔ)句的最高頻度的量級(jí)作為算法的時(shí)間復(fù)雜度。 提示二：如果算法的時(shí)間復(fù)雜度隨數(shù)據(jù)集的不同而不同，一般依據(jù)最壞的情況進(jìn)行估算；也可在某個(gè)約定（如等概率）下討論算法的平均時(shí)間復(fù)雜度。 提示三：對(duì)于較復(fù)雜的算法，可以將它分割成容易估算的幾個(gè)部分分別進(jìn)行估算，然后利用大 O的求和法則得到整個(gè)算法的時(shí)間復(fù)雜度。 提示四：?jiǎn)栴}的規(guī)模有時(shí)需用兩個(gè)參數(shù) 描述，如 m?n 矩陣的處理，兩個(gè)有序線性 表的合并等。此時(shí)算法的時(shí)間復(fù)雜度 T(m,n)=O(f(m,n)) 時(shí)間復(fù)雜度的估算 例 : 起泡排序算法 void bubble_sort( int a[ ], int n ) { // 將 a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列 for ( i=n1,change=TRUE。 i=1amp。amp。change。 i ) { change=false。 for ( j=0。 ji。 ++j ) if ( a[j]a[j+1] ) { a[j]?a[j+1]。 change=TRUE。 } } }// bubble_sort 起泡排序算法分析 排序算法基本操作： 關(guān)鍵字的比較，記錄的移動(dòng) （記錄的交換） 最小比較次數(shù)： n1 最大比較次數(shù)： 最小交換次數(shù)： 最大交換次數(shù)： 0 (n1)+(n2)+… +1=n(n1)/2 n(n1)/2 最壞情況下的時(shí)間復(fù)雜度： O(n2) 算法的 空間復(fù)雜度 (space plexity)是算法所需存儲(chǔ)空間的量度，記作 它表示： 隨著問題規(guī)模 n 的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與函數(shù) f(n)的增長(zhǎng)率相同。 S(n) = O( f (n) ) 算法的存儲(chǔ)空間需求 空間復(fù)雜度分析的重點(diǎn)是輔助變量所占空間 —— 輔助存儲(chǔ)量（附加空間） 。 若所需輔助存儲(chǔ)量為常數(shù)，則稱相應(yīng)算法為 原地工作 。 算法的存儲(chǔ)量包括 : 1． 輸入數(shù)據(jù)所占空間 2． 程序本身所占空間 3． 輔助變量所占空間 ，掌握其 基本概念。 C 語(yǔ)言的特點(diǎn)和算法書寫 規(guī)范。 本章學(xué)習(xí)要點(diǎn) 算法時(shí)間復(fù)雜度的基本技術(shù)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1