算法設计201417.docVIP

算法设计与分析 学号： 姓名： 专业：计算机科学与技术 (中国地质大学（武汉）计算机学院，湖北武汉，430074) 一：算法导引 1、算法 1.1算法的定义与特性 算法是一个在有限时间内逐步执行某种任务的过程，是计算机科学和计算机应用的核心，是计算机软件的灵魂。对于某些复杂问题的求解，其求解过程如图1所示。 图1 问题求解过程 上述问题求解过程表明：数据结构+算法=程序。在计算机科学中，算法是使用计算机解一类确定问题的精确、有效方法方法的代名词，它是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，而确定性、能行性、输入、输出、有穷性是算法所具有的五个重要特性。 1.2分析算法 分析算法可以在把算法变成程序实际运行前，知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。在分析算法时，我们约定存储空间没有限制，存储位置是均匀存储的，计算时间可用常数和变数表示。若Fi表示算法中用到的某种运算i的次数，ti该运算执行一次所用的时间算法的执行时间=∑Fi*tiRead A（n） do i=1 to n do j=i+1 to n if A(i)A(j) then A(i)??A(j) continue continue print A(n) 则计算时间f（n）=n c1+ n（n-1）c2/2+n c3 =n2 c2/2+(c1-c2/2+c3)n = n2 c4+ n c5 =O(n2) 常见的多项式限界函数有： O(1)O(logn)O(n)O(n logn)O(n2)O(n3) 常见的指数时间限界函数有： O(2n)O(n!)O(nn) 2、基本数据结构 数据结构+算法=程序，所以要设计一个有效的算法，必须选择或设计适合该问题的有效的数据结构，基本数据结构主要包括线性结构（队列、栈、数组等）与非线性结构（树、图等）。 二：分治法 1、一般方法 分治法中一般方法的基本思想是在问题的输入规模很大时，无法直接求解，则采用将整个问题分成若干个小问题后分而治之。其基本方法包括1）由难到易的校正技术，如方程的迭代求解；2）由粗到精的松弛技术，如用割圆法求圆的面积；3）由大到小的分治技术，主要针对量比较大，能够分解且分解后问题性质不变，如递归方法解汉诺塔问题。 例：汉诺塔 void hannoi(n,A ,B,C) if(n==1) move(A?C) else { Hanoi(n-1,A,C,B) move(A?C) Hanoi(n-1,B,A,C) } T(n)=2T(n-1)+C =2(2T(n-2)+C) +C = 22 T(n-2)+(1+2)C =2n-1 T(1)+(1+21+22+…+2n-2)C =2n-1C+2n-1C =2nC 2、二分检索 分治求解策略分析： 给定一个按非降次序排列的元素数组A（1：n），n=1判断x是否出现，若是，置j，使得x=A（j），若非，j=0。 定义问题的形式描述：I=(n, a1, a2, …,an,x) 问题分解：选取下标k，由此将I分解为3个子问题： I1=(k-1, a1, a2, …,ak-1,x) I2=(1, ak,x) I3=(n-k, ak+1, ak+2, …,an,x) 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则， 若xak，则只在I1中求解，对I3不用求解；若xak，则只在I3中求解，对I1不用求解；I1 、I3上的求解可再次采用分治方法划分后求解（递归过程）。 二分检索算法如下： procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case xA(mid):high←mid-1 xA(mid):low←mid+1 else:j←mid;return endcase repeat end BINSRCH 由于算法执行过程的主体是x与一系列中间元素A(mid)比较，则可用一棵二元比较树描述这一过程，二