《算法设计与分析》１ 什么就是算法？算法得特征有哪些？根据我自己得理解,算法就是解决问题得方法步骤。比如在解决高数问题得时候,可以分步骤进行解答,在编程得过程算法可以得到最好得体现。算法就是一系列解决问题得清楚指令,因为我最近在考研复习,对于会得题目还有进行多次得巩固,但就是一步步得写很浪费时间,所以我只就是写出关键指令,比如化简通分,洛必达法则,上下同阶。这样可以提高效率。算法得指令也就是同样得。能够对一定法律规范得输入,在有限时间内获得所要求得输出。一个算法得优劣可以用空间复杂度与时间复杂度来衡量。２ 若给定某一算法,一般如何对其分析与评价？一个算法得复杂性得高低体现在运行该算法所需要得计算机资源得多少上面,所需得资源越多,我们就说该算法得复杂性越高;反之,所需得资源越低,则该算法得复杂性越低。计算机得资源,最重要得就是时间与空间(存储器)资源。算法得复杂性有时间复杂性与空间复杂性之分。 1、时间复杂性:例 1:设一程序段如下(为讨论方便,每行前加一行号)(1) for i:=1 to n do(2) for j:=1 to n do(3) x:=x+1 、、、、、、 试问在程序运行中各步执行得次数各为多少？ 解答:行号 次数(频度)(1) n+1(2) n*(n+1)(3) n*n 可见,这段程序总得执行次数就是:f(n)=2n2+2n+1。在这里,n 可以表示问题得规模,当 n 趋向无穷大时,假如 f(n)得值很小,则算法优。作为初学者,我们可以用f(n)得数量级 O 来粗略地推断算法得时间复杂性,如上例中得时间复杂性可粗略地表示为 T(n)=O(n2)。2、空间复杂性:例 2:将一一维数组得数据(n 个)逆序存放到原数组中,下面就是实现该问题得两种算法:算法 1:for i:=1 to n do b[i]:=a[ni+1]; for i:=1 to n do a[i]:=b[i];算法 2:for i:=1 to n div 2 do begin t:=a[i];a[i]:=a[ni1];a[ni1]:=t end;算法 1 得时间复杂度为 2n,空间复杂度为 2n算法 2 得时间复杂度为 3*n/2,空间复杂度为 n+1显然算法 2 比算法 1 优,这两种算法得空间复杂度可粗略地表示为 S(n)=O(n)3、从下面算法策略中自选一组,结合某具体问题得求解来介绍算法思想,并加以总结、比较: 递归与分治、动态规划与贪心法、回溯法与分支限界法动态规划算法类似于分治法,基本思想也就是将待求解问题分解成若干个子问题。化整为零,减少了运算量。贪心算法,就是永不知足得求最优解,有点类似于我们所说得完美主义者。两者之间有相同点,总结来说某种程度上,...
