algorithm-chapter-(編輯修改稿)
2025-08-20 09:08 本頁面
【文章內容簡介】 余項只是 它的幾十萬分之一，對 T(n) 影響很小，可忽略不計。 于是， T(n) 可表示為： T*(n) = 3 , c 0 【 定義 】 T*(n) —— 算法的漸近時間復雜性（時間效率） 【 思考 】 兩個算法比較時，為什么常數 c 不重要？ *( ) ( )l i m 0()nT n T nTn??? ?漸進符號 ?算法效率的主要指標是基本操作次數的增長次數。 ?為了對這些增長次數進行比較和歸類，計算機科學家們使用了 3種符號： ?O（讀 “ O”）：上界 ?Ω（讀 ” omega”）：下界 ?Θ（讀 ” theta”）：近似 符號 O ? 定義 1 對于足夠大的 n， t(n)的上界由 g(n)的常數倍來確定，即： ? 記為 t(n) ∈ O(g(n)) t(n) ≤ cg(n)， c為常數 n ∈ O(n2) 100n+5 ∈ O(n2) n(n1)/2 ∈ O(n2) 符號 Ω ? 定義 2 對于足夠大的 n， t(n)的下界由 g(n)的常數倍來確定，即： ? 記為 t(n) ∈ Ω(g(n)) t(n) ≥ cg(n)， c為常數 n3∈ Ω (n2) n(n+1)∈ Ω (n2) 4n2+5 ∈ Ω (n2) 下界符號 【 證明 】 證 1： 據定義選： 證 2： 據定義選： ?下界符號 Ω T(n)∈ Ω(g(n)) 定義： 存在正數 c 和非負整數 n0 , 使下式成立 ( n 足夠大 ) 2( ) ( ) , ( ) ( )T n c g n T n O n??21 0 0 5 ( )n O n??210 0 5 10 0( ()) 1 11 0015n n n nnT n n? ? ? ? ? ??當20 5 , 1 0 1 ( ) , g n nnc ? ??2( ) 110 0 5 10 0 5 ( ) 10 5 01 5n n n nnT n n? ? ? ? ? ??當20 1 , 1 0 5 ( ) , g n nnc ? ??0 : ( ) ( )n n T n c g n??2( ) ( ) , ( ) ( )T n c g n T n O n??n0n()Tn規(guī)模 T(n) n0 之前的情況不重要 ()cg n下界 ( ) ( ( ) )T n g n??最優(yōu)效率分析 0符號 Θ ? 定義 3 對于足夠大的 n， t(n)的上界和下界由 g(n)的常數倍來確定，即： ? 記為 t(n) ∈ Θ(g(n)) c2g(n) ≤ t(n) ≤ c1g(n)， c1,c2為常數 n2+3n+2∈ Θ (n2) n(n1)/2∈ Θ (n2) 4n2+5 ∈ Θ (n2) 【 證明 】 上界： 下界： ( 1 ) ( )n n n? ? ?2 2 2 210 . 5 ( 1 ) 0 . 5 0 . 5 0 . 5 ()n n n n n c On n? ?? ? ??2222220 . 5 ( 1 ) 0 . 5 0 . 50 . 5 0 . 5 0 . 5(( 2 )0 . 2 )5n n n nn n nnnnc n???????????100. 5 , 1?? , 2??漸進符號的有用特性 ?定理 如果 t1(n) ∈ O(g1(n))并且 t2(n) ∈ O(g2(n))，則 t1(n)+ t2(n) ∈ O(max{(g1(n), g2(n)}) ?對于符號 Ω和 Θ，該定理也成立。 ?該定理表明： 當算法由兩個連續(xù)執(zhí)行部分組成時，該算法的整體效率由具有較大增長次數的那部分所決定。 性質 4 理解 某些算法由兩個以上的部分組成。該算法整體效率由具有最大增長率的部分決定（效率最差）。 例： 數組元素的查找算法（先排序后查找） 1. 對數組元素排序 2. 2. 順序查找有序數組 T1 (n) = (n1) ∈ Θ(n2) T2(n) = n ∈ Θ(n) 算法的整體效率： T(n) ∈ Θ(n2) 利用極限比較增長次數 前兩種情況意味著 t(n) ∈ O(g(n)) 后兩種情況意味著 t(n) ∈ Ω(g(n)) 第二種情況意味著 t(n) ∈ Θ(g(n)) 【 例 】 比較 (n1) 和 n2 的增長率 或證明： (n1)∈ Θ(n2) 22220 . 5 ( 1 ) 1 1 1 1lim lim lim( 1 )2 2 20 . 5 ( 1 ) ( )n n nn n n nn n nn n n? ? ? ? ? ???? ? ? ?? ? ? ?【 例 2】 2l o g nn比 較 和 的 增 長 次 數2222log ( log ) 39。li m li m( ) 39。1logli m li m 02 l g1o2nnnnnnennnne? ? ? ?? ? ? ??? ? ?常 數— —
規(guī)章制度相關推薦
鄂ICP備17016276號-1