算法引論ppt課件-文庫(kù)吧資料
2025-05-05 03:59本頁(yè)面
【正文】 b. 所以 11l n ( 1 ) 1 l nninni?? ? ? ??換底公式 1l o g ( 1 ) 1 l o g1l o g l o gninne i e?? ? ? ??11 ( lo g )nini????所以 亦即 x11 2 n x11 2 n+1 11 ( l o g )nin n ni????南京理工大學(xué) ( ) ( ( ) ) ( ) ( ( ) ) f N O g N f N o g N? ? ?( ) ( ( ) ) ( ) ( ( ) ) f N o g N f N O g N? ? ?(4) ( ) ( ( ) ) ( ) ( ( ) ) f N o g N g N f N? ? ? ?√ √ x 南京理工大學(xué) 估計(jì)算法的時(shí)間復(fù)雜度 ? 計(jì)算迭代次數(shù) ? 使用遞歸方程 ? 頻度分析 南京理工大學(xué) 計(jì)算迭代次數(shù) ? 通常，程序的運(yùn)行時(shí)間和程序的迭代次數(shù)成比例。 ? 使用 O時(shí)，希望估計(jì)的上界的階越小越好。 ? 理想情況下，希望能夠使用 Θ表示算法的時(shí)間復(fù)雜性。 ? 定義 4( o ) ：對(duì)于任意給定的 ε 0 ，存在正整數(shù) n0 ，使得當(dāng) n ≥ n0 時(shí)，有 f (n) / g(n) ≤ε ，則稱(chēng)函數(shù) f (n) 在 n 充分大時(shí)的階比 g(n) 低，記為 f (n) = o(g(n)) 。 ? 下界的階越高，則評(píng)估精度越高，也就越有價(jià)值。 南京理工大學(xué) Ω ? 定義 2(Ω)： 如果存在正的常數(shù) C 和自然數(shù) n0 ， 使得當(dāng) n ≥ n0時(shí)， 有 f(n)≥Cf (n)) = O(f (n))。g)。 – O( f )上界的階 越低 則評(píng)估越有價(jià)值。同樣有an2+nlog(n)+c = O(n2) 南京理工大學(xué) 小結(jié) ? 在進(jìn)行階的運(yùn)算時(shí)， 常系數(shù) 、 低的階 以及 常數(shù)項(xiàng) 可以忽略。同樣有 n2+nlog(n) = O(n2) ? 例： f(n)＝ an2+nlog(n) ， g(n)＝ n2。因?yàn)椋捍嬖?n0 ＝ 1， C=1，當(dāng)n≥ n0時(shí)，有 n2≤Cn3 , 所以： n2 = O(n3) ? 例： f(n)＝ n2 ， g(n)＝ n2。g(n)，則稱(chēng)函數(shù) f (n) 在 n 充分大時(shí)有上有界，且 g(n) 是它的一個(gè)上界，記做 f (n) = O(g(n)) ，并稱(chēng) f (n) 的階不高于 g(n) 的階。 南京理工大學(xué) 4種階： O, Ω, Θ,和 o ? 假設(shè)： f (n) 和 g(n) 是定義在正數(shù)集上的正函數(shù)。我們可以盡可能的選擇簡(jiǎn)單的 T*(n)，然后使用 T*(n)來(lái)替代 T(n) 作為 n → ∞ 的復(fù)雜度度量。為此 ,如果存在一個(gè) T*(n) ，使得當(dāng) n → ∞ 時(shí)有 (T(n) ? T*(n)) /T(n) → 0, 就稱(chēng) T*(n)是 T(n)當(dāng) n → ∞ 的漸近性態(tài)，或稱(chēng) T*(n)是給定算法在 n →∞ 時(shí)的漸近復(fù)雜度。 ? 不僅僅關(guān)注小規(guī)模輸入下的，而且還關(guān)注在大規(guī)模輸入下的情形 。 ? 希望算法的描述不僅獨(dú)立于機(jī)器，并且可以以任何語(yǔ)言來(lái)加以描述，包括自然語(yǔ)言。 南京理工大學(xué) 使用算法的絕對(duì)運(yùn)行時(shí)間來(lái)度量其時(shí)間復(fù)雜度？ － NO ? 一個(gè)編程實(shí)現(xiàn)了的算法的具體運(yùn)行時(shí)間，不僅僅和算法本身相關(guān)，還和很多其他因素密切相關(guān)：機(jī)器性能、編程語(yǔ)言、編譯器、編程技巧等等。39。通常可以考慮 3 種情形下的時(shí)間復(fù)雜度：最壞情形、最好情形以及平均情形。 ? 至此，就有： 1( , ) ( , )k iiiT n I t e n I?? ?南京理工大學(xué) 分析 ? T(n,I)給出的是在問(wèn)題規(guī)模為 n ，輸入為 I 時(shí)的時(shí)間復(fù)雜度。 ? 對(duì)于給定的算法 A，已經(jīng)知道用到的元運(yùn)算 Oi 的執(zhí)行次數(shù)為 ei , i = 1,...,k。例如，算術(shù)運(yùn)算、比較、邏輯、賦值等。 南京理工大學(xué) T=T(n,I)的具體化 ? 假設(shè)計(jì)算機(jī)提供 k 種元運(yùn)算，分別記為 O1, O2,…,O k。通常，我們讓 A隱藏在復(fù)雜度函數(shù)名中，所以有 T=T(n,I)和 S=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1