数据结构与算法绪论概念(2)

1.4算法和算法分析算法的基本概念算法效率的度量常用算法•穷举法•递推法与迭代法•递归法•逐步求精法•分治法•回溯法•动态规划法•贪心法22一、算法的概念算法：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。具有下列特性：有穷性：执行有穷步结束，每步有穷时间内完成。确定性：每条指令有确切含义，唯一执行路径，相同输入--相同结果。可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，它们是在算法所需的初始量或被加工的对象的表示。这些输入取自特定的对象集合。输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。33二、算法设计的要求设计一个“好”的算法应达到以下目标：正确性。也称有效性，是指算法能满足具体问题的要求。亦即对任何合法的输入，算法都会得出正确的结果。可读性。指算法被理解的难易程度。主要阅读与交流,其次机器执行。可读性实质上强调的是：越简单的东西越美。健壮性（鲁棒性）。是指对非法输入的抵抗能力。它强调的是，如果输入非法数据，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。高效(低时间复杂度与空间复杂度）。时间复杂度是指算法的运行的时间消耗，同一个问题，不同的算法可能有不同的时间复杂度。空间复杂度是指算法运行所需的存储空间的多少。44三、算法效率的度量算法执行时间度量两种方法：(1)事后统计方法不同算法--相同数据运行缺点：统计量依赖于计算机硬件、软件等环境因素,容易掩盖算法本身的优劣。一般采用下一方法。(2)事前分析估算方法一个用高级语言编写程序运行消耗时间取决于：a.算法策略b.问题规模c.语言d.编译程序所产生的机器代码的质量e.机器执行指令速度去掉与计算机硬件、软件有关因素,可以认为所用只依赖于问题的规模(n),即问题规模的函数。55度量方法时间复杂度指算法中包含简单操作的次数，一般不必精确计算出算法的时间复杂度，只是大致计算出相应的数量级。如：O（1）、O（logn)、O（n)、O()一般,记T(n)=O(f(n))---与f(n)增长率相同2n66度量方法基本操作的原操作--最深层循环内的原操作重复执行次数--频度我们用算法中的各语句的语句频度之和表示算法的时间复杂度例:(a){++x;s=0;}O(1)(b)for(i=1;in;++i){++x;s+=x;}O(n)(c)for(j=1;j=n;++j)for(k=1;k=n;++k){++x;s+=x;}O(n2)常量阶线性阶平方阶77时间复杂度的渐近表示常用的上界函数有:log(n),,,n!,......下面给出几种常见的函数的比较关系：即当n充分大时，下列关系成立：O(a)O(logn)O(n)O(nlogn)O()...O()O()O(n!)O()上面，n为自变量，a和m为常数mnnamnna2nnn88算法的时间复杂度的分类多项式时间复杂度算法：渐近函数为多项式，或变化率不超过多项式。指数时间复杂度算法：渐近函数变化率超过多项式，这类算法也称NP（nondeterministicpolynomial）-困难的算法。99[例](1/2)求出数组a中各数的大小次序号，存入数组b中的对应位置。例如，若a[]={4,2,3,9,6,8,7},则程序结束后，数组b内容为b[]={3,1,2,7,4,6,5},表示4，2，3，9，6，8，7的大小次序分别为3，1，2，7，4，6，5.voidOrderNumbers(int*a,intn,int*b){inti,j;for(i=0;in;i++)b[i]=1;…………………(1)：nfor(i=0;in-1;i++)…………………………(2)：n-1for(j=i+1;jn;j++)……………………….(3)：if(a[i]a[j])……………………………….(4)：b[j]++;…………………………………..(5)：elseb[i]++;return;}10)1(niin10)1(niin10)1(niin1010[例](2/2)总的语句频度最大为：n+(n-1)+3=2n-1+3(n-1)n/2=3/2+n/2–1=O()10)1(niin2n2n1111算法空间复杂度空间复杂度（Spacecomplexity）是算法所需的存储空间的度量。记为：S(n)=O(f(n))。主要考虑在算法运行过程中临时占用的存储空间的大小。1212四、常用算法1、穷举法穷举法(枚举法/试探法)的基本思想是：分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。[例]解不定方程。不定方程（组）是指独立方程个数少于变量个数而导致方程有多解。如，2x+3y=20是一个不定方程（设x,y为正整数）。解这个方程，就是求出所有的解。不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表示找到一组解。具体的程序片断如下。for(i=0;i=20;i++)for(j=0;j=20;j++)if(2*i+3*j==20)cout\ni,j;13132、递推法与迭代法递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解。1414（1）递推法递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。把这种由前面的子解得出后面的子解的规则称为递推关系。例如，对于Fibonacci数列：112358132134…设f(n)表示数列中第n项，则有：f(1)=1f(2)=1f(k)=f(k-1)+f(k-2)1515递推法实现Fibonacci数列intFibonacci(intn){intf1,f2,f3;intk;f1=1;f2=1;if(n==1)return1;if(n==2)return1;for(k=3;k=n;k++){f3=f1+f2;f1=f2;f2=f3;}returnf3;}非递归1616递推法运用的关键寻找递推关系：递推关系有解析和非解析两种。（1）解析递推关系是指能用一般数学公式描述的关系，也称递推公式。（2）非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个递推过程。递推关系必须有始基（最小子解）。如上例中，f1=1,f2=21717（2）迭代法迭代法和递推法类似，也是递增求解。不同：递推法每步得到的解都是相对于对应问题规模的完整解。迭代法中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）。当误差达到可接受的范围时，则认为“近似解”就是需要的结果。1818例：求a的平方根设：=x，把x看做未知数，则问题转化为解方程：x2=ax2-1=a-1x=1+(a-1)/(1+x)当x是准确解时，代入上式，左右两边相等。若x是近似值，则左右两边不等，当x的误差越小，则左右两边相差越小。继续迭代：x=1+(a-1)/(1+1+(a-1)/(1+x))……当左右两边相差足够小，则可认为当前x就是可接受的近似解。可按如下递推式：x0=1=1+(a-1)/(1+)anx1nx1919例：求a的平方根(迭代法)floatSqrt(floata){floatprecision=0.0001;//定义解的精度floatx,x0;x=1;do{x0=x;x=1+(a-1)/(x+1);}while(x-x0precision||x0-xprecision);//当最近两个近似解的差的绝对值小于给定精度时结束returnx;}20203、递归（1）递归与递归程序的概念递归(Recursion)用来解决一类可归纳描述的问题，或说可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决，可以分为两大部分：一些特殊（基础）情况，有直接的解法，即始基；这部分与原问题“相似”，可用类似（与整个问题的解法类似）的方法解决（即递归），但比原问题的规模小。21213、递归（续1）递归问题在数学中很常见。例如，计算阶乘：F(0)=1F(n)=n!=n*F(n-1)当n0在该式中，f(n-1)的计算与原问题f(n)的计算“相似”，只是规模较小。例如，算术求和：S(0)=0S(n)=k=S(n-1)+nnk022223、递归（续2）阶乘的计算，可通过下列的递归程序：longFact(intn){if(n=0)return1;//第一部份，始基elsereturnn*Fact(n-1);//第二部份，用实参n-1递归调用}2323（2）递归程序设计要点（续3）划分问题、寻找递归：许多问题，并没有明显的递归解法，这就需要寻找递归方案。首先要试着看能否把问题的处理分为两大类情况。一类情况是可以直接解决（不需要递归，为基本情况），另一类情况可按与原问题的解法（即现在正使用的解法）类似的解法进行（称为递归情况）。设计函数、确定参数：使用递归，必须设计为子程序（函数或过程）的形式。子程序的参数尤为重要，决定着递归的实现。递归子程序中的参数，除了应具有一般子程序所需要的参数外，还需要递归参数。设置边界、控制递归：递归中，第一类情况（非递归的情况）就起到循环条件的作用，这是因为，满足第一类情况时，就不递归调用了，本次调用即可结束。把第一类情况的判别条件称为递归控制条件。24244、逐步求精简单地讲，逐步求精方法，是一种逐步“划分”的方法，即将问题的解决，先用几个大/粗的模块的组合表示。对这些模块，先不考虑它们的内部实现，只规定其功能。然后再按类似方法继续划分这些模块，直到它们都变为程序设计语句。在这种划分中，应遵循下列规则：保证模块的粒度应逐步变小。粒度越大/粗，“说明性”越强，越远离程序设计语言，但越容易给出（设计）；保证当前正确。对每次划分，若假定各模块都可正确实现，则它们的当前组合（即划分方式）是整个问题的正确实现；对逐步求精的描述，一般采用“伪码”。所谓伪码，是指不完全的程序代码，它一般以程序设计语言(典型的是C/Pascal之类的结构化程序设计语言)的流程控制语句（如while,for,if等）为主体，夹杂自然语言的描述。2525[例]求矩阵的鞍点考虑求矩阵鞍点的问题。所谓矩阵鞍点，是指满足这样条件的矩阵元素：它是所在行上的最小元素，同时是所在列上的最大元素。可以证明，一个矩阵可以有多个鞍点，但它们的值均相等。显然，求鞍点的一个直接的方法是，检查矩阵中每个元素是否为鞍点，用伪码描述为（设矩阵名为a，有n行m列，元素下标从0起）：for(i=0;in;i++)for(j=0;jm;j++){判断a[i][j]是否为鞍点；if(a[i][j]是鞍点)输出a[i][j];}2626[例]求矩阵的鞍点(续1)这里，关键问题是判断a[i][j]是否为鞍点，所以关键是细化模块“判断a[i][j]是否为鞍点”。解决该问题，先检查a[i][j]是否为i行上的最小者，若是，则继续检查其是否为j列上最大者，若是，则为鞍点。其他情况都不是鞍点。该过程的伪码描述为：isSaddle=0;检查a[i][j]是否为i行上最小者；if(是){检查a[i][j]是否为j列上最大者；if(是)isSaddle=1;}2727[例]求矩阵的鞍点（续2）这段程序结束后，isSaddle为非0时表示a[i][j]为鞍点，否则不是鞍点。在这里，有两个模块需要细化：a)检查a[i][j]是否为i行上最小者，这可以先找出i行上最小者的下标，然后与a[i][j]比较即可：kk=0;for(k=1;km;k++)if(a[i][k]a[i][kk])kk=k;