复杂性函数的阶渐近复杂性当输入规模趋于极限情形时（相当大）的复杂性表示复杂性阶的三个记号 T(n)=@(f(n)若存在c1,c,>0，和正整数n≥1，1使得当nzn.时，总有T(n)≤c,*f(n)且T(n)≥c2*f(n)成立，即T(n)=O(f(n))与T(n)=2(f(n))都成立。给出了算法时间复杂度的上界和下界e.g.T(n)=3n3+2n2, c,=5, 取c2=3, no=1, f(n)=n3则当n≥n（=1)时，有3n3+2n2≤5n3及3n3+2n2≥3n3（无穷多个），:T(n)=@(n3)6
复杂性函数的阶 ◼ 渐近复杂性 当输入规模趋于极限情形时(相当大)的复杂性 表示复杂性阶的三个记号 T(n)=(f(n)) ➢ 若存在c1 ,c2>0，和正整数n0≥1，使得当n≥n0时，总有 T(n)≤c1 *f(n)且T(n)≥c2 *f(n)成立，即T(n)=O(f(n))与 T(n)=Ω(f(n))都成立。 ➢ 给出了算法时间复杂度的上界和下界 ➢ e.g.T(n)= 3n3+2n2 ，c1=5，取c2=3，n0=1，f(n)=n3 ， 则当n≥n0 (=1)时，有3n3+2n2≤5n3及3n3+2n2≥3n3（无 穷多个），∴T(n)= (n3 ) 6
多项式时间与指数时间1设每秒可做某基本运算109次，n=60算法1算法2算法3算法4算法5算法6n?n3n5复杂度2n3nn运算时6*10-8s3.66世纪3.6*10-°s2.16*10-4s1.3*1013世纪0.013min两个结论多项式时间的算法互相之间虽有差距，一般可接受指数量级时间的算法对于较大的n无实用价值1
多项式时间与指数时间 ◼ 设每秒可做某基本运算109次，n=60 ◼ 两个结论 多项式时间的算法互相之间虽有差距，一般可接受 指数量级时间的算法对于较大的n无实用价值 7 算法1 算法2 算法3 算法4 算法5 算法6 复杂度 n n 2 n 3 n 5 2 n 3 n 运算时 6*10-8s 3.6*10-6s 2.16*10-4s 0.013min 3.66世纪 1.3*1013世纪
和的估计与界限直接求和的界限 Zh=1 k ≤ E=1n ≤n?8
和的估计与界限 ◼ 直接求和的界限 σ𝒌=𝟏 𝒏 𝒌 ≤ σ𝒌=𝟏 𝒏 𝒏 ≤ 𝒏 𝟐 8
和的估计与界限直接求和的界限- Eh=1ak ≤ n max (ak)1≤k≤nC
和的估计与界限 ◼ 直接求和的界限 σ𝒌=𝟏 𝒏 𝒂𝒌 ≤ 𝒏 max 𝟏≤𝒌≤𝒏 {𝒂𝒌} 9
和的估计与界限直接求和的界限ak+1有口对于所有k≥0,≤r<1,求=1ak上界aka1≤r→a≤aoraoa2≤r →α2 ≤air ≤aor2a1ak+1≤r → ak+1 ≤akr ≤aorkakZK=1ak ≤ ZR=1aork = ao ZR=1rk ≤ 10
和的估计与界限 ◼ 直接求和的界限 对于所有𝒌 ≥ 𝟎，有𝒂𝒌+𝟏 𝒂𝒌 ≤ 𝒓 < 𝟏，求σ𝒌=𝟏 𝒏 𝒂𝒌上界 ➢ 𝒂𝟏 𝒂𝟎 ≤ 𝒓 → 𝒂𝟏 ≤ 𝒂𝟎𝒓 ➢ 𝒂𝟐 𝒂𝟏 ≤ 𝒓 → 𝒂𝟐 ≤ 𝒂𝟏𝒓 ≤ 𝒂𝟎𝒓 𝟐 ➢ . ➢ 𝒂𝒌+𝟏 𝒂𝒌 ≤ 𝒓 → 𝒂𝒌+𝟏 ≤ 𝒂𝒌𝒓 ≤ 𝒂𝟎𝒓 𝒌 ➢ σ𝒌=𝟏 𝒏 𝒂𝒌 ≤ σ𝒌=𝟏 𝒏 𝒂𝟎𝒓 𝒌 = 𝒂𝟎 σ𝒌=𝟏 𝒏 𝒓 𝒌 ≤ 𝒂𝟎 𝟏−𝒓 10