_時間復雜性-在線瀏覽
2025-03-10 21:54本頁面
【正文】 ， 使得對于所有的 n = n0 ， 3n+5 = c h(n)。 這樣，根據(jù)大 O 法的定義有 g(n)=O(h(n)) 。因此， f(n)= O(n) 是一個緊貼漸進界。 4 物料管理 INTRO 3/21/2023 4 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研復習大綱 _SJTU 算法和算法分析 上例采用的是 均勻時間耗費 。 如循環(huán)語句，條件： O(1) + THEN OR ELSE 后的語句的時間耗費之和。 時間復雜性的級別的判斷： 級別越低越好。if Lim f(n)/g(n) = c。 f(n)、 g(n) 同 級別。if Lim f(n)/g(n) = 0。 f(n) 級別低 。if Lim f(n)/g(n) = ∞。 g(n) 級別低 。 logn 級別低。 n∞ n∞ n∞ n∞ O(logn) 和 O (n1/2) ？？？ 5 物料管理 INTRO 3/21/2023 5 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研復習大綱 _SJTU 算法和算法分析 大 Ω 表示法： 在 n 為任何數(shù)時，所以， T(n) = Ω (n2) 所以， T(n) = Ω (n3) 同理： T(n) = 5n2。 Ω:找盡可能高的下界。定義；如果存在著正的常數(shù) c c2 和自然數(shù) n0，當 n = n0 時；有 C1 g(n) = f (n) = C2 g(n) 成立，則稱 f( n ) = Θ (g( n )) 。例 設(shè) T(n) = (n+1)2 = Θ ( n2) 6 物料管理 INTRO 3/21/2023 6 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研復習大綱 _SJTU 算法和算法分析 1 。 兩段程序那個好一些，那個差一些 ( 從算法的時間復雜性角度考慮 ) A. for ( i = 0 。 ++ i ) a 〔 i 〕 = i。 B. for ( i = 0 。 ++ i ) { if ( i = = n1 ) a [n1 〕 = 1。 } 解：程序 A 執(zhí)行的語句次數(shù)為 n 次，而程序 B 執(zhí)行的語句次數(shù)為 2 n 次 , 故而程序 B 更好一些。 2 。 if ( n = 1 ) m = 1。 return m。 3 、將下列算法的時間復雜性的級別，按由低到高的順序排成一列； O(n 4 ), O(1), O(n 3 ), O( n n 1/2 ), O( logn), O( nlogn), O(n 1/2 ), O(n 2 ), O(2 n ) 解：由低到高的順序為： O(1), O(logn), O(n1/2), O(n*logn), O(n*n1/2), O(n2), O(n3), O(n4), O(2n), 8 物料管理 INTRO 3/21/2023 8 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研復習大綱 _SJTU 算法和算法分析 4 、下面的算法為計算 x 的 n 次冪 的值 (y = x^n) ，求其時間復雜性的級別，注意 x 和 n 都是正整數(shù)： 。 scanf(“ %d” , x)。 y = x。 n = n1 } printf(“ %d” , y )。s c a n f(“ % d” , n )。t = 1 。 t = t * 2。 y = 1。 y ＝ y * y 。
教學課件相關(guān)推薦
鄂ICP備17016276號-1