计算机算法分析方法.ppt

第二讲算法分析的一般方法一、(健壮性)、“关键操作”是什么?内排:(“比较类”)待排序元素之间的“比较”次数;待排序元素的“移动”次数。查找:待查找值x与数据元素之间的“比较”次数。矩阵乘法:矩阵元之间的乘法/“关键操作”数,随“问题规模”而变化的规律nnlogn2nn5**********nf(n)。不同算法不同的输入规模nAiT(n)n=10n=30n=60366“比较”(VARa;n);FORi:=1TOn-1[k:=i;FORj:=i+1TOnDOIFa[j]<a[k]THENk:=j;IFk<>iTHENa[k]a[i]]ENDP;T(n)=n-1i=1=(n-i)i=1n=1/2n(n-1)n1j=i+,f,g:NR+。(2)若存在正整数c和n0,使得对于所有nn0,都有:f(n)cg(n)则称g(n)是f(n)的下界,记为:f(n)=(g(n))(1)若存在正整数c和n0,使得对于所有nn0,都有:f(n)cg(n)则称g(n)是f(n)的上界,记为:f(n)=O(g(n))5(3)若存在正整数c1、c2和n0,使得对于所有的nn0,都有:c1g(n)f(n)c2g(n)则称g(n)是f(n)的精确界,记为:f(n)=(g(n))6注:1)g(n)与f(n)的最高次项相比,相差一个系数2)一般地,T(n)=amnm+am-1nm-1++a1n+a0nm(|am|+|am-1|++|a1|+|a0|)=cnm(其中:c=|am|+|am-1|++|a1|+|a0|)T(n)=O(nm)3)O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)<O(nn):I是问题规模为n的输入集合,iI是问题的一个输入。ti(n)是输入i下,算法A的“关键操作”数。则,算法A的最坏复杂度:WA(n)=max{ti(n)}iI8例“顺序表查找”(a,n,x):INTEGER;a[n+1]:=x;i:=1;WHILEa[i]<>xDOi:=i+1;IFi=n+1THENRETURN(0)ELSERETURN(1)ENDF;失败查找最坏特性WAu(n)=n+1失败!:I是问题规模为n的输入集合,iI是问题的一个输入。ti(n)是输入i下,算法A的“关键操作”数。Pi(n)是输入i出现在I中的概率。则,算法A的平均复杂度:AVA(n)=Pi(n)ti(n)iI例“顺序表查找”算法的平均复杂度:设:“失败”概率为q(0q1),而且假设“成功”查找时,各种输入“等概”,即:psi(n)=(1-q)/n10