例设 f)=,n2-3证明fm)=(n2) 证若存在正数c,d使得 13 C d 那么1/2,n≥1;c≤1/14,n≥7 取c=1/14,d=1/2,m0=7 例设八m)=-6n3,证明fm)≠6(n 证要使6n3≤cn2,则6n≤e, 即n≤c/6,与c是常数矛盾
11 例 设 证明 f(n)=Θ(n2) 证 若存在正数 c,d 使得 那么 d≥1/2 ,n≥1; c≤1/14, n≥7 取 c=1/14, d=1/2, n0=7 例 设 f(n)=6n3, 证明 f(n)≠ Θ(n2) 证 要使 6n3≤cn2，则 6n≤c , 即 n≤c/6, 与 c 是常数矛盾 3 , 21 ( ) 2 f n = n − n , 3 2 1 d n c ≤ − ≤
大O表示法的常用计算规则 今加法规则 sT(m)=71(m)+72(m)=o(1(m)+O(2(m)= O(max(f1(n),f2() 今乘法规则 7(m)=71(m)×72(m)=o(1()×O(2(m O(升1(m)×2(m)
12 大O表示法的常用计算规则 加法规则 \T(n) = T1(n)+ T2(n) = O(f1(n)) + O(f2(n))= O(max(f1(n), f2(n))) 乘法规则 \T(n) = T1(n)×T2(n) = O(f1(n))×O(f2(n))= O(f1(n)×f2(n))
50 nlogn 30 20 10 ogn 餐888 ee 78910 Figure 2.24 plot of various functions
13
多项式时间的算法与指数时间的算法 多项式时间的算法 时间复杂度函数为O(p(m)的算法,其中p(m)是n的多项式 指数时间的算法 不存在多项式p(m)使得该算法的时间复杂度为O(p(m) 时间复杂 问题规模 度函数 10 20 60 n 10-52*10-53*105 4÷105 5*10-5 6*105 10 4*1049*10416÷10 25*104 36*10 1038*10327*10364*10 125*103 216÷103 101 3.2 24.3 17分 52分 13.0分 2n 001秒1.0秒17.9分127天357年360世纪 3".059秒58分6年385世纪2+10世纪1310世纪14
.059秒 58分 6.5年 3855世纪 2*108世纪 1.3*1013世纪 14 3n 2n .001秒 1.0秒 17.9分 12.7天 35.7年 366世纪 n5 10-1 3.2 24.3 1.7分 5.2分 13.0分 216*10-3 125*10-3 64*10-3 27*10-3 8*10-3 10-3 n3 36*10-4 25*10-4 16*10-4 9*10-4 4*10-4 10-4 n2 6*10-5 5*10-5 4*10-5 3*10-5 2*10－5 10－5 n 10 20 30 40 50 60 时间复杂 问题规模 度函数 多项式时间的算法与指数时间的算法 多项式时间的算法 时间复杂度函数为 O(p(n))的算法，其中 p(n)是 n 的多项式 指数时间的算法 不存在多项式 p(n)使得该算法的时间复杂度为 O(p(n))
时间复杂 1小时可解的问题实例的最大规模 度函数 计算机快100倍的计算机快100倍的计算机 100N1 1000N1 10N 31.6N 4.64N 10N 2.N4 398N4 2n N+6.64 N+997 3 +4.19 N+6.29 15
15 N6 N + 6.29 6 N + 4.19 3 6 n N5 N + 9.97 5 N + 6.64 2 5 n 3.98 N4 n N4 2.5 N4 5 10 N3 n N3 4.64 N3 3 31.6 N2 n N2 10 N2 2 1000 N1 n N1 100 N1 计算机 快100倍的计算机 快1000倍的计算机 时间复杂 1小时可解的问题实例的最大规模 度函数