递归与分治策略

《递归与分治策略》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章算法概述学习要点理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法。算法定义：是一个有穷规则的集合。这些规则规定了解决某一问题的一个运算序列。算法应该具有五个特性：有限性、确定性、输入、输出、可行性。1.1算法与程序算法的五个特性输入：算法开始执行执行之前指定初始值（有零个或多个输入输出：产生与输入相关的量（至少有一个）。确定性：每一条规则都是明确、无二义的。有限性：求解问题的运算序列，必须在有限的计算步后停止。可行性

2、：每一计算步都是基本的、可实现的。1.计算序列：若对于I的每一个输入x,由状态函数f定义一个计算序列：y0,y1,y2,……其中：y0=x;yk+1=f(yk)(k0)。若一个计算序列在第k步终止，且k是使yK处于接受状态的最小整数，则称yk是由x产生的输出。2.算法的另一种描述：一个算法是对于I中所有输入x,都能在有穷步内终止的一个计算序列。计算序列与算法Qf0y1f1y2xIykfk-1程序程序是算法用某种程序设计语言的具体体现程序=算法+数据结构程序可以不满足算法的性质(4)有限性。例如：操作

3、系统，是一个在无限循环中执行的程序，因而不是一个算法。问题求解过程证明正确性分析算法设计程序优不正确正确修改理解问题精确解或近似解选择数据结构算法设计策略设计算法不佳1.2算法复杂性分析（1）计算机资源：时间、空间复杂性：所需资源多少算法复杂性：算法运行时所需资源的量算法复杂性分析目的：分析问题复杂性、算法是否可行，选择最好算法时间复杂性：所需时间资源的量T(n)空间复杂性：所需空间资源的量S(n)其中n是问题的规模（输入大小）算法复杂性分析（2）时间复杂性细化--3种典型的复杂性：最坏、最好、平均复杂性记T(I)为输入I

4、时的问题的算法复杂性算法的时间复杂性（1）最坏情况下的时间复杂性Tmax(n)=max{T(I)

5、size(I)=n}（2）最好情况下的时间复杂性Tmin(n)=min{T(I)

6、size(I)=n}（3）平均情况下的时间复杂性Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。算法渐近复杂性假定当n时,T(n);取t(n)，使(T(n)-t(n))/T(n)0，当n;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主

7、项。它比T(n)简单。几个复杂性参照函数CLognlog2nnnlognn2n32nn!增长的阶不同的计算过程在消耗计算资源的速率上可能存在着巨大差异，描述这种差异的一种方法是用增长的阶的记法，以便我们理解在输入变大时，某一计算过程所需资源的粗略度量情况。令n是一个参数，它能作为问题规模的一种度量，令f(n)是一个计算过程在处理规模为n的问题时所需要的资源量。我们称f(n)具有Δ(g(n))，记为f(n)=Δ(g(n))，其中Δ是O、、o、等。若干符号及其意义：O(f)，(f)，(f)，o(f)在下面的讨论中，对所

8、有n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)

9、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}（2）渐近下界记号(g(n))={f(n)

10、存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}（3）高阶记号oo(g(n))={f(n)

11、对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)

12、存在正常数c1,c2

13、和n0使得对所有nn0有：c1g(n)f(n)c2g(n)}复杂性阶符号的理解举例称f(n)具有(g(n))，记为f(n)=(g(n))，如果存在与n无关的整数c1和c2，使得：c1g(n)f(n)c2g(n)对于任何足够大的n都成立。举例求n！递归算法f(n)f(n)=1，1，2，6，24，…，nf(n-1)，…f(n){if(n==0

14、

15、n==1)return1;returnn*f(n-1);}求阶乘的递归算法时间和空间需求增长都是(n)；但对于迭代的算法，时间增长为(n)，空间增长为(1)（常数）

16、。增长的阶对于线性的过程，问题规模扩大一倍，资源增长一倍；对于指数增长的过程，问题规模加1，资源就增大一个常数倍；对于对数增长的过程，问题规模增大一倍，所需资源增长一个常数各记号在等式和不等式中的意义f(n)=(g(n))的确切意义是：f(n)(g(n))。一般情况下，等式和不等式中的渐近记号(