數(shù)據(jù)結(jié)構(gòu)緒論課件(已改無錯(cuò)字)
2022-10-13 09:01:33 本頁面
【正文】 T(n)=O(f(n))。 其中 ， 大寫字母 O為 Order(數(shù)量級(jí) ) 的字頭 ， f(n)為函數(shù)形式 ， 如 T(n)=O(n2)。 ? 當(dāng) T(n)為多項(xiàng)式時(shí) ,可只取其最高次 冪項(xiàng) ,且它的系數(shù)也可略去不寫。 ? 一般地，對(duì)于足夠大的 n，常用的時(shí) 間復(fù)雜性存在以下順序： O(1) O(logn) O(n) O(n*logn) O(n2) O(n3)… O(2n)O(3n)… O(n!) 其中 ,O(1)為常數(shù)數(shù)量級(jí) ,即算法的 時(shí)間復(fù)雜性與輸入規(guī)模 n無關(guān)。 ? 算法的運(yùn)行時(shí)間往往還與具體輸入的數(shù)據(jù)有關(guān)，通常用以下兩種方法來確定一個(gè)算法的運(yùn)算時(shí)間： ? 1. 平均時(shí)間復(fù)雜性：研究同樣的 n值時(shí)各種可能的輸入，取它們運(yùn)算時(shí)間的平均值。 ? 2. 最壞時(shí)間復(fù)雜性：研究各種輸入中運(yùn)算最慢的一種情況下的運(yùn)算時(shí)間。 返回 算法復(fù)雜性的分析 ? 空間復(fù)雜度的計(jì)算 一維數(shù)組 a[n]：空間復(fù)雜度為 o(n) 二維數(shù)組 a[m][n]：空間復(fù)雜度為o(m*n) 應(yīng)用舉例與分析 ? 例 ：計(jì)算下面交換 i和 j內(nèi)容程序段 的時(shí)間復(fù)雜性 。 temp=i。 i=j。 j=temp。 ? 解：以上三條單個(gè)語句均執(zhí)行 1次， 該程序段的執(zhí)行時(shí)間是一個(gè)與問題 n無關(guān)的常數(shù)，因此，算法的時(shí)間復(fù) 雜度為常數(shù)階 ,記作 T(n)=O(1). 例 ? 計(jì)算下面求累加和程序段的時(shí)間復(fù)雜性 （ 1） sum= 0。 (1次） （ 2） for(i=1。i=n。i++) （ n次 ） （ 3） for(j=1。j=n。j++) (n2次 ） （ 4） sum++； (n2次 ） ? 解： T(n)
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1