10算法分析【荐】.ppt

An Introduction to Database Systenm 算法 常数阶 Θ(1) 对数阶 Θ(log2n) 线性阶 Θ(n) 线性对数阶 Θ(nlog2n) 平方阶 Θ(n2) 立方阶 Θ(n3) k次方阶 Θ(nk) 指数阶 Θ(2n) 规则1：循环 循环次数乘以循环体需要的时间 规则3：顺序语句 各语句执行时间之和 for(i = 0; i n; i++) a[i] = 0; for(i = 0; i n; i++) for(j = 0; j n; j++) a[i] += a[j] + i+ j; 规则4：if/else if(condition) s1; else s2; 时间小于测试condition的时间和S1和S2中最大的时间之和 算法分析 忽略掉函数进入和返回需要的时间 T(n) = n+2n+1 =3n+1 算法分析 int locate(SqList L, int x){ i=1, j=L.length; while(i=j){ p=(i + j ) / 2 if(L.elem[p-1] = = x) return p; } if(L.elem[p-1] x) i=p+1; else j=p-1; } return 0 算法分析 语句i=1, j=L.length需要的时间为2 执行一次while需要的时间为7 p=(i + j ) / 2; if(L.elem[p-1] = = x) return p; if(L.elem[p-1] x) i=p+1; else j=p-1; } while(i=j){ 算法分析 while要执行多少次？ a1 a2 a3 a4 a5 a6 a7 i=1, j=7, p=4 i=5, j=7, p=6 i=7, j=7, p=7 找到 i=8, j=7 没找到 算法分析 j – i = n - 1 j – i = (n - 1) / 2 j – i = (n - 1) / 22 ……. j – i = (n - 1) / 2x = 1 x = log2(n - 1) 循环次数= log2(n - 1) + 2 算法分析 T(n)= 2 + 7(log2(n - 1) + 2) =7log2(n-1)+ 16 算法比较 两个算法哪个速度快呢？ T1(n) =3n+1 T2(n)= 7log2(n-1)+ 16 算法比较 46 61 20 45 58 19 45 55 18 44 52 17 43 49 16 43 46 15 42 41 40 39 T2 43 40 37 34 T1 14 13 12 11 n 42 31 10 37 28 9 35 25 8 34 22 7 32 19 6 30 16 5 27 23 16 16 T2 13 10 7 4 T1 4 3 2 1 n 算法比较 T1(n) T2(n) ??? 3n + 1 7log2(n-1)+ 16 ???? 时间复杂度 T(n)=O(f(n))，如果存在正常数c和n0，当nn0 ，T(n)≤cf(n) O(f(n))叫做T(n)的 渐近上界( Asymptotic Upper Bound) O(f(n))是一个无穷集合，其元素为函数 例如，O( n2)，n2是集合中的一个代表，集合中任何一个函数f，有cf ≤n2 时间复杂度 T1(n) =3n+1 ≤3n + n ≤4n c=4，n0 = 1 T1(n) =O(n) T1(n) =3n+1 时间复杂度 T2(n)= 7log2(n-1)+ 16 T2(n)= O(log2(n)) c=8, n0=216 T2(n) = 7log2(n-1)+ 16 ≤7log2(n) + 16 ≤7log2(n) + log2(n) n≥216 ≤8log2(n) 时间复杂度 T(n)=Ω(g(n))，如果存在正常数c和n0，当nn0 ，T(n)≥cg(n) Ω(g(n))叫做T(n)的渐近下界(Asymptotic Lower Bound) T1(n)=Ω(n) T2(n)= Ω(log2n) 时间复杂度 T(n)=Θ