算法引論ppt課件(編輯修改稿)
2025-05-26 03:59 本頁面
【文章內容簡介】 分析只要關心 T*(n)的 階 就可以了 (在 n 充分大時 )，不必關心其中的常數因子。 南京理工大學 4種階： O, Ω, Θ,和 o ? 假設： f (n) 和 g(n) 是定義在正數集上的正函數。 (此假設的實際意義 ?) ? 定義 1 (O)：如果存在正的常數 C和自然數 n0，使得當n≥n0時， 有 f(n)≤Cg(n)，則稱函數 f (n) 在 n 充分大時有上有界，且 g(n) 是它的一個上界，記做 f (n) = O(g(n)) ，并稱 f (n) 的階不高于 g(n) 的階。 南京理工大學 例子 ? 例： f(n)＝ n2 ， g(n)＝ n3。因為：存在 n0 ＝ 1， C=1，當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) 南京理工大學 小結 ? 在進行階的運算時， 常系數 、 低的階 以及 常數項 可以忽略。 ? 根據 O的定義，得到的是在問題規(guī)模充分大時，算法復雜度的一個上界。上界的階 越低 則評估越有價值。 ? 運算規(guī)則 – O( f ) + O(g) = O(max( f , g))。 – O( f )O(g) = O( fg)。 – O(Cf (n)) = O(f (n))。 – f = O( f )。 南京理工大學 Ω ? 定義 2(Ω)： 如果存在正的常數 C 和自然數 n0 ， 使得當 n ≥ n0時， 有 f(n)≥Cg(n)，則稱函數 f (n) 在 n 充分大時有下有界，且 g(n) 是它的一個下界，記做 f (n) = Ω(g(n)) ，并稱 f (n) 的階不低于 g(n) 的階。 ? 下界的階越高，則評估精度越高，也就越有價值。 南京理工大學 Θ和 o ? 定義 3(Θ)： f (n) = Θ(g(n)) ，當且僅當 f (n) = O(g(n)) ，且 f (n) = Ω(g(n)) ，稱 f (n) 和 g(n) 是同階。 ? 定義 4( o ) ：對于任意給定的 ε 0 ，存在正整數 n0 ，使得當 n ≥ n0 時，有 f (n) / g(n) ≤ε ，則稱函數 f (n) 在 n 充分大時的階比 g(n) 低，記為 f (n) = o(g(n)) 。 南京理工大學 小結 ? 進行算法的時間復雜度分析，就是求其 T(n)，并用 O、Ω或是 Θ以盡可能簡單的形式進行表示。 ? 理想情況下，希望能夠使用 Θ表示算法的時間復雜性。退而求其次，可以使用 O或是 Ω。 ? 使用 O時，希望估計的上界的階越小越好。 ? 使用 Ω時，希望估計的下界的階越大越好。 南京理工大學 算法耗費時間隨問題規(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 南京理工大學 階運算的幾個實例
教學課件相關推薦
鄂ICP備17016276號-1