算法引論ppt課件(編輯修改稿)
2025-05-26 03:59 本頁面
【文章內(nèi)容簡介】 分析只要關(guān)心 T*(n)的 階 就可以了 (在 n 充分大時 )，不必關(guān)心其中的常數(shù)因子。 南京理工大學(xué) 4種階： O, Ω, Θ,和 o ? 假設(shè)： f (n) 和 g(n) 是定義在正數(shù)集上的正函數(shù)。 (此假設(shè)的實際意義 ?) ? 定義 1 (O)：如果存在正的常數(shù) C和自然數(shù) n0，使得當(dāng)n≥n0時， 有 f(n)≤Cg(n)，則稱函數(shù) f (n) 在 n 充分大時有上有界，且 g(n) 是它的一個上界，記做 f (n) = O(g(n)) ，并稱 f (n) 的階不高于 g(n) 的階。 南京理工大學(xué) 例子 ? 例： f(n)＝ n2 ， g(n)＝ n3。因為：存在 n0 ＝ 1， C=1，當(dāng)n≥ n0時，有 n2≤Cn3 , 所以： n2 = O(n3) ? 例： f(n)＝ n2 ， g(n)＝ n2。因為：存在 n0 ＝ 1， C=1, n≥ n0時，有 n2≤Cn2 , 所以： n2 = O(n2) ? 例： f(n)＝ n2+nlog(n) ， g(n)＝ n2。同樣有 n2+nlog(n) = O(n2) ? 例： f(n)＝ an2+nlog(n) ， g(n)＝ n2。同樣有 an2+nlog(n) = O(n2) ? 例： f(n)＝ an2+nlog(n)+c ， g(n)＝ n2。同樣有an2+nlog(n)+c = O(n2) 南京理工大學(xué) 小結(jié) ? 在進(jìn)行階的運算時， 常系數(shù) 、 低的階 以及 常數(shù)項 可以忽略。 ? 根據(jù) O的定義，得到的是在問題規(guī)模充分大時，算法復(fù)雜度的一個上界。上界的階 越低 則評估越有價值。 ? 運算規(guī)則 – O( f ) + O(g) = O(max( f , g))。 – O( f )O(g) = O( fg)。 – O(Cf (n)) = O(f (n))。 – f = O( f )。 南京理工大學(xué) Ω ? 定義 2(Ω)： 如果存在正的常數(shù) C 和自然數(shù) n0 ， 使得當(dāng) n ≥ n0時， 有 f(n)≥Cg(n)，則稱函數(shù) f (n) 在 n 充分大時有下有界，且 g(n) 是它的一個下界，記做 f (n) = Ω(g(n)) ，并稱 f (n) 的階不低于 g(n) 的階。 ? 下界的階越高，則評估精度越高，也就越有價值。 南京理工大學(xué) Θ和 o ? 定義 3(Θ)： f (n) = Θ(g(n)) ，當(dāng)且僅當(dāng) f (n) = O(g(n)) ，且 f (n) = Ω(g(n)) ，稱 f (n) 和 g(n) 是同階。 ? 定義 4( o ) ：對于任意給定的 ε 0 ，存在正整數(shù) n0 ，使得當(dāng) n ≥ n0 時，有 f (n) / g(n) ≤ε ，則稱函數(shù) f (n) 在 n 充分大時的階比 g(n) 低，記為 f (n) = o(g(n)) 。 南京理工大學(xué) 小結(jié) ? 進(jìn)行算法的時間復(fù)雜度分析，就是求其 T(n)，并用 O、Ω或是 Θ以盡可能簡單的形式進(jìn)行表示。 ? 理想情況下，希望能夠使用 Θ表示算法的時間復(fù)雜性。退而求其次，可以使用 O或是 Ω。 ? 使用 O時，希望估計的上界的階越小越好。 ? 使用 Ω時，希望估計的下界的階越大越好。 南京理工大學(xué) 算法耗費時間隨問題規(guī)模的變化 Algorithm 1 2 3 4 5 Time function(ms) 33n 46n lg n 13n2 2n Input size(n) Solution time 10 sec. sec. sec. sec. sec. 100 sec. sec. sec. sec. 4?1016 yr. 1,000 sec. sec. 13 sec. hr. 10,000 sec. sec. 22 min. 39 days 100,000 sec. min. days 108 yr. Time allowed Maximum solvable input size (approx.) 1 second 30,000 2,000 280 67 20 1 minute 1,800,000 82,000 2,200 260 26 南京理工大學(xué) 階運算的幾個實例
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1