计算机算法分析与设计论文

信息技术学院算法设计与分析课程考查论文题目0-1背包问题的算法设计策略对比与分析专业软件工程班级2007级软件工程学号071164019姓名马进杰任课教师刘维群完成日期2010年6月20日0-1背包问题的算法设计策略对比与分析0引言对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法=程序》，可见算法在计算机科学界与计算机应用界的地位。1算法复杂性分析的方法介绍算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。让我们从比较两对具体算法的效率开始。1.1比较两对算法的效率考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A[1..m]（为简单起见。还设m=2k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得A[i]=c；若找不到，则返回一个0。问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足A[i]=c；或者扫到A的最后一个分量，经检测仍不满足A[i]=c。我们用一个函数Search来表达这个算法：FunctionSearch(c:integer):integer;VarJ:integer;BeginJ:=1;{初始化}{在还没有到达A的最后一个分量且等于c的分量还没有找到时，查找下一个分量并且进行检测}While(A[i]c)and(jm)doj:=j+1;IfA[j]=cthensearch:=j{在数组A中找到等于c的分量，且此分量的下标为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]c，则c只可能在A[m/2+1],A[m/2+2],..,A[m]之中，因而下一步只要在A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得A[i]=c，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于c的分量，后一种情况则找不到。这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数B_Search来表达：FunctionB_Search(c:integer):integer;VarL,U,I：integer;{U和L分别是要查找的数组的下标的上界和下界}Found：boolean;BeginL:=1;U:=m;{初始化数组下标的上下界}Found:=false;{当前要查找的范围是A[L]..A[U]。}{当等于c的分量还没有找到且U=L时，继续查找}While(notFound)and(U=L)doBeginI:=(U+L)div2;{找数组的中间分量}Ifc=A[I]thenFound:=TureelseifcA[I]thenL:=I+1elseU:=I-1;End;IfFoundthenB_Search:=1elseB_Search:=0;End;容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大（mm0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。1.2复杂性的计量算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：C=F(N,I,A)其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，那么应该有：T=T(N,I,A)(2.1)和S=S(N,I,A)(2.2)通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为T=T(N,I)和S=S(N,I)由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些，所以下文将主要地讨论时间复杂性。下面以T(N,I)为例，将复杂性函数具体化。根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2,..,Ok；再设这些元运算每执行一次所需要的时间分别为t1,t2,..,tk。对于给定的算法A，设经过统计，用到元运算Oi的次数为ei，i=1,2,..,k，很明显，对于每一个i，1=i=k，ei是N和I的函数，即ei=ei(N,I)。那么有：(2.3)其中ti，i=1,2,..,k,是与N,I无关的常数。显然，我们不可能对规模N的每一种合法的输入I都去统计ei(N,I),i=1,2,…,k。因此T(N,I)的表达式还得进一步简化，或者说，我们只能在规模为N的某些或某类有代表性的合法输入中统计相应的ei,i=1,2,…,k，评价时间复杂性。下面只考虑三种情况的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为Tmax(N)、Tmin(N)和Tavg(N)。在数学上有：(2.4)(2.5)(2.6)其中，DN是规模为N的合法输入的集合；I*是DN中一个使T(N,I*)达到Tmax(N)的合法输入，是DN中一个使T(N,)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。1.3复杂性的渐近性态及其阶随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结构又十分复杂的问题的求解算法，其复杂性分析应如何简化的问题。我们先要引入复杂性渐近性态的概念。设T(N)是在第二段中所定义的关于算法A的复杂性函数。一般说来，当N单调增加且趋于∞时,T(N)也将单调增加趋于∞。对于T(N)，如果存在T’(N)，使得当N→∞时有：(T(N)-T’(N))/T(N)→0那么，我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近复杂性而与T(N)相区别，因为在数学上，T’(N)是T(N)当N→∞时的渐近表达式。直观上，T’(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如当T(N)=3N2+4Nlog2N+7时，T’(N)的一个答案是3N2，因为这时有：显然3N2比3N2+4Nlog2N+7简单得多。由于当N→∞时T(N)渐近于T’(N)，我们有理由用T’(N)来替代T(N)作为算法A在N→∞时的复杂性的度量。而且由于于T’(N)明显地比T(N)简单，这种替代明显地是对复杂性分析的一种简化。进一步，考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T’(N)的阶就够了，不必关心包含在T’(N)中的常数因子。所以，我们常常又对T’(N)的分析进--步简化，即假设算法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时间。综上所述，我们已经给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要引入五个渐近意义下的记号：Ο、Ω、θ、ο和ω。以下设f(N)和g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N