0-1背包问题的算法设计策略对比与分析报告

《0-1背包问题的算法设计策略对比与分析报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析课程论文算法设计与分析大作业班级：电子154姓名：吴志勇学号：1049731503279任课老师：李瑞芳日期：2015.12.25共12页第11页算法设计与分析课程论文0-1背包问题的算法设计策略对比与分析0引言对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机

2、专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。1算法复杂性分析的方法介绍算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间与空间（即存储器）资源。因此，算法的复杂性有时

3、间复杂性T(n)与空间复杂性S(n)之分。算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性，N,I和A表示问题的规模、算法的输入和算法本身规模，则有如下表达式：C=F(N,I,A)T=F(N，I,A)S=F(N，I,A)其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中，因此表达式中一般不写A。即：C=F(N,I)T=F(N,I)S=F(N,I)算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例：算法

4、的时间复杂性一般分为三种情况：最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,Ω，θ，和o。O表示渐近上界Ω表示渐近下界：θ表示同阶即：f(n)=O(g(n))且f(n)=Ω（g(n)）2常见的算法分析设计策略介绍2.1递归与分治策略分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原

5、问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。递归算法举例：共12页第11页算法设计与分析课程论文Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：第n个Fibonacci数可递归地计算如下：intfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}从上看出：递归算法的有点为：结构清晰，可读性强

6、，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点为：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。分治算法：一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为

7、P

8、=n的问题所需的计算时间，则有：通过迭代法求得方程的解：算法举例：二分搜索技术：给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出

9、一特定元素x。据此容易设计出二。搜索算法：templateintBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x