算法ppt课件.ppt

Tel:0571-88394222 QQ;106159278,计算方法,Tel:0571-88394222 QQ;106159278,时间复杂度空间复杂度递归排序方法,Tel:0571-88394222 QQ;106159278,算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,算法,Tel:0571-88394222 QQ;106159278,算法（algorithm）是指令的集合，是为解决特定问题而规定的一系列操作。它是明确 定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。一个算法通 常来说具有以下五个特性：,Tel:0571-88394222 QQ;106159278,算法设计要求,输入：一个算法应以待解决的问题的信息作为输入。输出：输入对应指令集处理后得到的信息。可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时 间内完成。有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此 整个算法也是在有限时间内可以结束的。确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定 输入开始，多次执行同一指令集结果总是相同的 简单的说，算法就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是算法的逻辑形式，后者是算法的代码形式。,Tel:0571-88394222 QQ;106159278,时间复杂性,在计算机资源中，最重要的就是时间与空间。评价一个算法性能的好坏，实际上就是评 价算法的资源占用问题。直接对源程序的分析，不考虑运行时的情况。,Tel:0571-88394222 QQ;106159278,简单选择排序,令 A0,n-1为有 n 个数据元素的数组，我们的目标是将数组 A 排序为一个非降序的有序 数组。使用简单选择排序来解决这个问题的算法是：首先在 n 个元素中找到最小元素，将其 放在 A0中，然后在剩下的 n-1 个元素中找到最小的放到 A1中，这个过程不断进行下去，直到在最后 2 个元素中找到小的并将其放到 An-2中。图 2-2 说明了对具有 7 个整数的数组使用简单选择排序的过程。,Tel:0571-88394222 QQ;106159278,Tel:0571-88394222 QQ;106159278,Tel:0571-88394222 QQ;106159278,算法 selectSort输入：整型数组 a0,n-1 输出：按非降序排列的数组 a0,n-1 代码：public void selectSort(int a)int n=a.length;for(int k=0;kn-1;k+)/end of forint min=k;for(int i=k+1;in;i+)if(aiamin)min=i;if(k!=min)int temp=ak;ak=amin;amin=temp;/end of if,Tel:0571-88394222 QQ;106159278,通过对算法的分析可以看出，这个算法执行的比较次数为同时也可以看出数据元素交换的次数在 0 到 n-1 之间，而每次交换需要使用 3 条赋值语 句，因此数据元素的赋值在 0 到 3(n-1)之间。,Tel:0571-88394222 QQ;106159278,首先我们说一个算法对于某个输入要用 x 秒运行是没有意义的。这是因为影响实际运行 时间的因素不仅有算法本身，还有其他诸多因素。例如算法是在什么机器上运行的，不同的 机器其运算速度是不一样的；除了硬件的影响，操作系统以及使用的高级语言、编译系统都 会对算法的实际运行时间造成影响。因此在对算法的运行时间做出分析时我们应该避免这些 因素的影响，为此我们可以假设一些基本操作都是可以在一个常数时间内完成的。例如逻辑运算、赋值运算等都是基本操作。这样算法执行基本操作的次数可以反映算法的运行时间，在后面提到算法的运行时间时都是指运行基本操作的次数。其次，即使能够排除软硬件的影响，对同一个算法而言，如果问题的规模不同，那么实 际的运算时间也会有很大差异。例如在算法 2-1 中，如果算法分别对 100 个整数排序以及对109个整数排序，其实际运行时间的差异是非常大的。假设算法中进行一比较需要 10-8秒，那么对 100 个数进行排序大概需要 100*99/2*10-8=0.0000495 秒，而对 109个数排序则需要109*(109-1)/2*10-8=158.5 年。为此在分析算法的运行时间时我们必须将问题的规模（通常用 n来表示）也考虑进去。显然算法执行基本操作的次数是关于规模n的非负函数，我们把它记 为T(n)。,Tel:0571-88394222 QQ;106159278,下面给出了一些常用的作为问题规模的例子：在排序和查找问题中，用数组或表中元素的个数作为问题的规模；在图的相关问题中，用图中的点或（和）边的数目；在计算几何问题中，用顶点、边、线段或多边形的数目；在矩阵运算中，用矩阵的维数；在数论问题中，通常将表示输入数的比特数来表示输入大小。,Tel:0571-88394222 QQ;106159278,通过以上的分析我们可以看出：我们评价算法的运行时间是通过分析在一定规模下算法执行基本操作的次数来反映的，并且由于我们只对大规模问题的运行时间感兴趣，所以是使 用算法的渐进时间复杂度 T(n)来度量算法的时间性能的。、符号分别定义了时间复 杂度的上界、下界以及精确阶。,Tel:0571-88394222 QQ;106159278,空间复杂性,算法的空间复杂性同样是由算法运行时使用的空间来评价的。我们把算法使用的空间定义为：为了求解问题的实例而执行的操作所需要的存储空间的数目，但是它不包括用来存储 输入实例的空间。同样前面对于评价算法时间复杂性的讨论都可以用于对算法的空间复杂性的讨论。并且 在这里有这样一个观察结论：算法的空间复杂性是以时间复杂性为上界的。这是因为在算法 中每访问一次存储空间都是需要使用一定时间的，即使每次访问的都是不同的存储空间，空 间的大小也不会超过基本操作次数常数倍，因此算法的空间复杂性是以时间复杂性为上界 的。如果使用S(n)与T(n)分别表示算法的空间复杂度和时间复杂度，则有S(n)=(T(n)。例如在算法2-1 中，为了算法的执行，我们使用了常数个中间变量，每个变量的存储空间都是常数大小，所以在算法2-1 中：S(n)=(1)=(1)=(1),Tel:0571-88394222 QQ;106159278,算法与程序比较,(1)程序是算法在计算机程序设计语言中的具体实现。通常定义一个算法必须提供足够细节,才能转化为程序。(多个程序表示同一算法)(2)算法的有穷性意味着不是所有程序都是算法.例如;操作系统是一个程序不是算法,但把操作系统各种任务看成单独问题,每个问题是由特定算法实现,得到输出结果便终止。(3)算法和程序是相互独立的。,Tel:0571-88394222 QQ;106159278,算法的评价,1.算法评价目的:选择合适算法或对已有的算法进行改进。2.通常设计一个好的算法应考虑：(1)正确性首要条件(2)运行时间:算法的时间复杂度(即:执行一个简单操作所需时 间与操作次数的乘积)。(3)占用存储空间:算法的空间复杂度(含存储算法本身,算法输 入输出数据和算法运行过程中临时占用空间)。(4)简单性:算法易于理解,易于编码及调试。3.算法的时间复杂度和空间复杂度S(n)=O(f(n)一般用数量级来表示。,Tel:0571-88394222 QQ;106159278,时间复杂度(Time Complexity),算法在计算机中运行时间受很多因素(与计算机系统的软硬件环境有关)的影响。通常利用语句频度和渐进时间复杂度衡量时间复杂度。1.语句频度指该语句被执行的次数。(1)任何算法都可分解为简单操作(如赋值、比较、移位等)来执行.(2)假设执行每条语句所需时间为单位时间,则算法运行时间转化为所有语句执行次数,即语句频度之和（频度统计法）。2.一般情况下,语句频度是问题规模n的函数,用T(n)表示,若有某个辅助函数f(n)使：则称f(n)与 T(n)同阶,记作:T(n)=O(f(n)O(f(n)表示时间复杂度(或称渐进时间复杂度),f(n)是最大语频,Tel:0571-88394222 QQ;106159278,时间复杂度(Time Complexity),3.算法分析的几个方法：(1)执行一些简单的输入,输出或赋值语句时,可近似认为需要O(1)时间.(2)对于顺序结构,需要依次执行一系列语句所需时间可采用累加求和的方式进行估计(3)对于选择结构,如if语句。它的时间主要消耗在执行then子句或else子句时所用的时间，但if语句判断条件本身也消耗O(1)的时间(4)对于循环语句,它的时间主要耗费在执行循环体以及循环条件的检验上,可采用乘法计算出算法的语频,从而得到算法时间复杂度。(5)对于较为复杂算法,采用先分解为几个容易估计的部分,然后利用求和方法计算出整个算法的时间复杂度。,Tel:0571-88394222 QQ;106159278,时间复杂度综合考虑,1.由于算法时间复杂度考虑的只是问题规模n的增长率,在难以精确计算语句频度的情况下,只需求出关于n的增长率或阶数即可。2.有时算法时间复杂度与算法处理的输入数据集有关,算法的时间复杂度难以确定。这时一般采用算法在最坏的情况下复杂度作为时间复杂度。例如：在排序算法中,要求从小到大排序.若给定输入集为从大到小最坏情况,时间复杂度为T(n)=O(n2)若不作特别说明,以后各章均为最坏情况时间复杂度。3.在分析时间复杂度是,随着问题规模n的增大，各种时间复杂度存在下列大小关系：,数量级的大小顺序：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)(n!),Tel:0571-88394222 QQ;106159278,递归问题,递归是在计算机科学、数学等领域运用非常广泛的一种方法。使用递归的方法解决问题，一般具有这样的特征：我们在寻求一个复杂问题的解时，不能立即给出答案，然而从一个规 模较小的相同问题的答案开始，却可以较为容易的求解复杂的问题。,Tel:0571-88394222 QQ;106159278,递归的概念,递归（recursion）是指在定义自身的同时又出现了对自身的引用。如果一个算法直接 或间接地调用自己，则称这个算法是一个递归算法。任何一个有意义的递归算法总是由两部分组成：递归调用与递归终止条件。下面我们来 看一个递归算法的简单例子。）。,Tel:0571-88394222 QQ;106159278,Tel:0571-88394222 QQ;106159278,在算法 5-1 中第 2 行是判断是否满足递归终止条件，如果满足则执行第 3 行，否则进行 递归调用执行第 5 行。在这里可以看到递归调用与递归终止条件在递归算法中缺一不可，如 果没有递归终止条件那么递归将会无休止的进行下去；而没有递归调用，则递归算法就不成 其为递归算法。因此在编写递归算法时一定要注意这两个方面的内容。下面我们再看一个递 归算法的例子。,Tel:0571-88394222 QQ;106159278,例 5-2计算以 x 为底的 n 次幂，其中 n 为非负整数。计算整数次幂可以简单的使用一个循环迭代 n 次，每让 x 乘以自身即可。但是这样算法的时间复杂度为(n)，效率较低。下面我们设计一个新的算法，可以使得时间复杂度为(log n)。因为xn可以写成如下形式：,Tel:0571-88394222 QQ;106159278,这显然是一个递归定义，其中当 n 为 0 时是递归终止条件；否则如果 n 大于 0，则需要进行递归调用，只不过在进行递归调用时需要分两种不同情况分别进行处理。算法 5-2 实现 了这一过程。,Tel:0571-88394222 QQ;106159278,Tel:0571-88394222 QQ;106159278,如果将乘法作为基本操作，则算法 5-2 的时间复杂度函数可以如下表示：,Tel:0571-88394222 QQ;106159278,这是一个非常简单的递推关系的求解问题，因为每进行一次调用，n 变为原来的一半，因此总共的递归调用次数为(log n)，因此T(n)=T(n/2)+1=(T(n/4)+1)+1=(T(n/8)+1)+1)+1=(T(1)+1)+1)+1=(log n),Tel:0571-88394222 QQ;106159278,在实际应用中使用递归可以解决以下多方面的问题：问题本身的定义就是递归的，例如许多数学定义就是递归的。问题本身虽然不是递归 定义的，但是它所用到的数据结构是递归的，例如链表、树就可以看成是递归定义的数据结 构。问题的解法满足递归的性质,Tel:0571-88394222 QQ;106159278,递归的实现与堆栈,我们 知道在递归算法中会递归调用自身，因此在递归算法的执行过程中会多次进行自我调用。那 么这个调用过程是如何实现的呢?为了说明自身的递归调用，我们先看任意两个函数通常在一个函数执行过程中需要调用另一个函数时，在运行被调用函数之前系统通常需 要完成如下工作：对调用函数的运行现场进行保护，主要是参数与返回地址等信息的保 存；创建被调用函数的运行环境；将程序控制转移到被调用函数的入口。在被调用函 数执行结束之后，返回调用函数之前，系统同样需要完成 3 件工作：保存被调函数的返 回结果；释放被调用函数的数据区；依照保存的调用函数的返回地址将程序控制转移 到调用函数。,Tel:0571-88394222 QQ;106159278,如果上述函数调用的过程中发生了新的调用，即被调函数在执行完成之前又调用了其他函数，此时构成了多个函数的嵌套调用。当发生嵌套调用时按照后调用先返回的原则处理，如此则形成了一个保存函数运行时环境变量的“后进先出”的使用过程，因此整个函数调用期 间的相关信息的保存需要使用一个堆栈来实现。系统将整个程序运行时需要的数据空间安排 在一个堆栈中，每当调用一个函数时就为它在栈顶分配一个存储区，每当从一个函数返回时 就释放它的存储区。一个递归算法的实现实际上就是多个相同函数的嵌套调用。,Tel:0571-88394222 QQ;106159278,下面我们用算法 5-1：factorial 来说明递归的实现过程。假设 n=3，那么递归调用的过程 如图 5-1 所示。,Tel:0571-88394222 QQ;106159278,练习,链表找环(探测环形链表)O(n)DFS(经过一个点就标记,标记2次的即可判定为环)半素数只要一个数能被分解成两个素数，那么这个数就是半素数 素数 从 2 到 ceil(sqrt(N)取余数探查,Tel:0571-88394222 QQ;106159278,1)写一个函数计算当参数为n时的值 1+2+3+4+5+6+7.+n2)用一个函数实现两个函数的功能n为如：fn1(n)=n/2!+n/3!+n/4!+n/5!+n/6!fn2(n)=n/5!+n/6!+n/7!+n/8!+n/9!,Tel:0571-88394222 QQ;106159278,联系方式,杭州和盈科技公司Address:潮王路238号银地大厦2F,