(3)f（n）=n ； g（n）=log2n
(由洛比塔法则) f ( n) n n lim lim lim 2 n g ( n) n [log( n)] n 2 log( n).1/ ln 2 n lim 2 n 2 /(ln 2)
n M 0, N 0, 当n N , M 2 [log( n)] n M .[log(n)]2 n (log 2 ( n))

可以理解为：f(N)的上界是N2级别的。
(2)f(N)=N-1, f(N)=O(N)

可以理解为：f(N)的上界是N级别的。
O的性质



(1)O(f)+O(g)=O(max(f,g)) (2)O(f)+O(g)=O(f+g) (3)O(f)O(g)=O(f.g) (4)如果g(N)=O(f(N))， 则O(f)+O(g)=O(f) (5)O(C.f(N))=O(f(N))，C是一个正常数 (6)f(N)=O(f)
当N>100, 2N2+11N-10 3N2 任意给定的>0, 当N>3/，有3N2< .N3 取N0=max(100, 3/ +1),当NN0, 2N2+11N-10 < 3N2 < .N3
返回
如何确定两个函数之间的关系
对于下列各组函数f(n) 和g(n) ，确定 f（n）= O(g(n)) 或 f（n）=Ω(g(n)) 或 f（n）=θ(g(n)) 并简述理由。 （1）f（n）= log(n2) ； g（n）=log(n)+5 （2） f（n）= log(n2) ； g（n）=n1/2 （3） f（n）=n ； g（n）=log2n
返回
常见的算法时间复杂度
O(1) O(log(n)) O( n ) O(n) O(n.log(n)) O(n )
2
O(n ) O(2 ) O(3 ) O(n !) O(n )
3 n n n
第九章
算法设计与分析
本章学习的主要内容
第9.1节 第9.2节 第9.3节 第9.4节 第9.5节 第9.5节

渐进复杂性 分治法 贪心法 动态规划法 回溯法 分支限界法
第9.1节 渐进复杂性

假设T(n)是算法A的复杂性函数。 通常T(n)有比较多的项，

例如：T(n)=3n2+nlog(n)+7
（2）f（n）= log(n2) ； g（n）=n1/2
f ( n) log(n 2 ) 2log(n) lim lim lim n g ( n) n n n n (2 / ln 2)2 n (由洛比塔法则) lim 0 n n 2
log(n ) 0, N 0, 当n N , | 0 | n log( n 2 ) ; log( n 2 ) . n n log( n 2 ) O ( n )

人们希望将T(n)简化，提出了渐进复杂 性的概念。
渐进意义下的记号


O渐进的定义(上界)
渐进的定义(下界) 渐进的定义 o渐进的定义 如何确定两个函数之间的关系 常见的算法时间复杂度
O渐进的定义(上界)


如果存在正的常数C和自然数N0，使得当N N0 时有f(N)C.g(N)，则称函数f(N)当N充分大时 有上界，且g(N)是它的一个上界, 记为f(N)＝ O(g(N))。 例如： (1)f(N)=2N2+11N-10, g(N)=N2 常数C = 3， N0 = 11，当N> N0 , f(N) 3g(N), 因此2N2+11N-10 =O(N2)

渐进的定义(下界)


如果存在正的常数C和自然数N0，使得当N N0 时有f(N) C.g(N)，则称函数f(N)当N充分大 时有下界，且g(N)是它的一个下界，记为f(N) ＝ (g(N))。 例如：f(N)=2N2+11N-10 g(N)= N2, f(N)= (g(N))= (N2) 常数C = 1， N0 = 1，当N> N0 , f(N) c.g(N), 因此2N2+11N-10 = (N2) 返回
性质(2) O(f)+O(g)=O(f+g)的证明
证明：设F(N)=O(f)，G(N)=O(g)，则根据O的 定义有: 存在常数C1和自然数N1，使得当N N1，有 F(N)C1.f(N) 存在常数C2和自然数N2，使得当N N2，有 G(N)C2.g(N) 令C3=max{C1, C2}, 返回 F(N)C1.f(N) C3.f(N) G(N)C2.g(N) C3.g(N) 当N max{N1,N2}, F(N)+G(N) C3.(f(N)+g(N)) F(N)+G(N)=O(f+g), 即O(f)+O(g)=O(f&#；g（n）=log(n)+5 2 f (n) log(n ) 2log(n) lim lim lim 2 n g (n) n log(n) 5 n log(n) 5
log(n 2 ) 0, N 0, 当n N , | 2 | log(n) 5 log(n 2 ) 2 2 log(n) 5 (2 )(log( n) 5) log( n 2 ) (2 )(log( n) 5) log(n 2 ) (log( n) 5)
结论：
f ( n) (1) lim 0, f (n) O( g (n)) n g ( n) f ( n) (2) lim c, f (n) ( g (n)) n g ( n) f ( n) (3) lim , f (n) ( g (n)) n g ( n)
渐进的定义

f(N)= (g(N))当且仅当 f(N)=O(g(N))且f(N)= (g(N))， 我们称f(N)与g(N)同阶。 例如：2N2+11N-10= (N2)
返回
o渐进的定义


如果对于任意给定的>0，都存在N0，使得 当NN0时有f(N)/g(N)< ，则称函数f(N)当 N充分大时的阶比g(N)低，记f(N)=o(g(N)) 例如：2N2+11N-10=o(N3)