算法复杂性分析

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

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

2、题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扌：

3、到A的第i个分量,经检测满足A[i]=c；或者扫到A的最后一・个分量，经检测仍不满足A[i]=co我们用一个函数Search来表达这个算法：FunctionSearch(c:integer):integer;VarJinteger;BeginJT；｛初始化｝｛在还没有到达A的最后一个分量月•等于c的分量还没有找到时，查找下一个分量并且进行检测｝While(A[i]

4、｛在数组屮找不到等于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]

5、一种情形，都把下一步需要继续査找的范围縮小了一半。再拿这一半的子数组的屮间分量与c比较，照此重复下去，总有一个时候，或者找到一个i使得A[i]=c,或者找不到满足条件的数组元素。这个新算法因为有反复把供査找的数组分成两半，然后在其屮一半继续査找的特征，我们称为二分查找算法。它可以用函数B_Search來表达：FunctionB_Search(c:integer):integer;VarL,U,I:integer;｛U和L分别是要查找的数组的下标的上界和下界｝Found:boolean;BeginL:=1;U:=m;｛初始化数组下标的上下界｝Found:=false;｛当前要查找

6、的范围是A[L]..A[U]。｝｛当等于c的分量还没有找到且U>=L时，继续查找｝While(notFound)and(U>=L)doBeginl:=(U+L)div2;｛找数组的屮间分量｝〈查找时间AmSearch-WB_Search比较Ifc=A[l]thenFound:=Tureelseifc>A[l]thenL:=l+1elseU:=l-1;End;IfFoundthenB_Search:=1elseB_Search:=0;End;容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个元素，就能判断出c是否在A中。算法Search和

7、B_Search解决的是同一・个问题，但在最坏的情况下(所给定的c不在A中)，两个算法所需要检测的元索个数却大不相同，前者要口=2*个，后者只要k+1个。可见算法B_Search比算法Search高效得多。以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随Z不同，即时间复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大(m>m0)lht算去B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。不过，应该指出：川实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间为运行该算法的实际计算机性能有关。换句话说，这

8、个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该収算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量氓纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。复杂性的计量算法的复杂性是算法运彳亍所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间(即存储器)资源的量称作空间复朵性。这