【精品】算法复杂性分析.doc

《【精品】算法复杂性分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法复杂性分析比较两对算法的效率3复杂性的计j递归方程解的渐近阶的求法1619递归方程纽.解的渐进阶的求法——套用公式法23递归方程纽•解的渐进阶的求法——弟分方程法25递归方程纽•解的渐进阶的求法——母函数法29复杂性的渐近性态及其阶6复杂性渐近阶的重要性10算法复杂性渐近阶的分析12递归方程纽解的渐进阶的求法——代入法递归方程纽解的渐进阶的求法——迭代法比较两对算法的效率考虑问题仁12知不重复且已经按从小到大排好的m个整数的数组A[1..m](为简单起见。还设k是一个确定的非负整数)。对于给定的整数c,要求寻找一个下标i,使得A[i]=c；若找

2、不到，则返冋一个0。问题1的一个简单的算法是：从头到尾扫描数纽A。照此，或者扫到A的第i个分量,经检测满足A[i]=c；或者扫到A的最后一个分量，经检测仍不满足A[i]=c3我们用一个函数Search來表达这个算法：FunctionSearch(c:integer):integer;VarJJnteger;BeginJT；｛初始化｝｛在还没有到达A的最后一个分量且等于c的分量还没有找到时，查找下一个分量并且进行检测｝While(A[i]

3、分量的下标为j｝elseSearch:=0;｛在数组屮找不到等丁•c的分量｝End;容易看出，在最坏的情况下，这个算法要检测A的所有m个分量才能判断在A中找不到等于c的分量。解决问题1的另一个算法是利用□知条件中A已排好序的性质。首先拿A的中间分量A[m/2]与c比较，如果A[m/2]=c,则解已找到。如果A[m/2]>c,则c只可能在A[1],A[2],..,A[m/2-1]之中，因而下一•步只要在A[1],A[2],..,A[m/2-1]中继续查找；如果A[m/2]

4、一步只要在A[m/2+1],A[m/2+2],・.,A[m]中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，照此重复下去，总有一•个时候，或者找到一个i使得A[i]=c,或者找不到满足条件的数纽•元素。这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续杳找的特征，我们称为二分杳找算法。它可以用函数B_Search來表达：FunctionB_Search(c:integer)integer;VarL,UJ:integer;｛U和L分别是要查找的数组的下标的上界和下界｝Found:b

5、oolean;BeginL:=1;U:=m;｛初始化数组下标的上下界｝Found:=false;｛当前要查找的范圉是A[L]..A[U]O｝｛当等丁c的分量还没有找到且U>=L时，继续查找｝While(notFound)and(U>=L)doBeginl:=(U+L)div2;｛找数组的中间分量｝Ifc=A[l]thenFound:=Tureelseifc>A[l]thenL:=l+1elseU:=l-1;End;:>mSearch与Search比较IfFoundthenB_Search:=1elseB_Search:=0;End;容易理解，在最坏

6、的情况下最多只要测A中的k+1(k=logm,S里的log以2为底，下同)个元素，就能判断出c是否在A中。算法Search和B_Search解决的是同一个问题，但在最坏的情况下(所给定的c不在A中)，两个算法所需要检测的元素个数却大不相同，前者要m=2k个，后者只要k+1个°可见算法B^Search比算法Search高效得多。以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即时间复杂性不同。上图是运行这两种算法的时间曲线。该图农明，当m适当大(m>m0)W算去B_Search比算法Search省时，而口当m更大时

7、，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时I'可不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该収算法运行的实例吋间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而口在不实际运行该算法的情况下就能分析出它所需耍的时间和空间。复杂性的计量算法的复杂性是算法运行所需要的计算机

8、资源的量,需要的时间资源的量称作时间复杂性，需要的空间(即存储器)资源的量称作空间复杂性。这个量应该集中反映算法屮所采用的