计算机算法设计与分析-第1章 算法概述

《计算机算法设计与分析-第1章 算法概述》由会员分享，可在线阅读，更多相关《计算机算法设计与分析-第1章 算法概述（68页珍藏版）》请在金锄头文库上搜索。

1、计算机算法设计与分析 Design and Analysis of Computer Algorithms,第一章 算法概述,2,理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C+语言描述算法的方法,学习要点:,3,提纲,一、算法与程序 二、算法复杂性分析 三、用C+语言描述算法的方法,4,提纲,一、算法与程序 二、算法复杂性分析 三、用C+语言描述算法的方法,5,1.1 算法的概念,算法是指解决问题的方法和过程。 算法是对特定问题求解步骤的一种描述，包含操作的有限规则和操作的有限序列。 通俗一点讲，算法就是一

2、个解决问题的公式（数学手册上的公式都是经典算法）、规则、思路、方法和步骤。算法可以用自然语言描述，也可以用流程图描述，但最终要用计算机语言编程，上机实现。,6,算法是若干指令的有穷序列，满足性质： 输入： 有1个或多个满足给定约束条件的量作为算法的输入。 输出： 算法产生至少一个量作为输出。 确定性：组成算法的每条指令是清晰，无歧义的。 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 算法要求其执行时间是有限的 (终止性) 。 程序的执行时间可能是无限的。(例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是

3、一个算法。 ),7,程序,程序是某个算法或过程的在计算机上的一个具体的实现。 程序是依赖于程序设计语言的，甚至依赖于计算机结构的。 算法是脱离具体的计算机结构和程序设计语言的。,8,算法与程序的区别与联系,(1).一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 (2).程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 (3).算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序.,9,算法程序 算法描述：自然语言，流程图，程序设

4、计语言，伪代码 用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。 本书中采用类C+伪代码语言描述算法,10,人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。,11,对算法的学习包括五个方面的内容： 设计算法。 表示算法。 确认算法。 分析算法。 验证算法。,12, 设计算法。算法设计工作是不

5、可能完全自动化的，应学习了解已经被实践证明是有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域； 表示算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点；,13,确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行，得到算法运算的结果； 分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较； 验证算

6、法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和作时空分布图组成。,14,1.2 问题表示,设Input和Output是两个集合。一个问题是一个关系RInputOutput，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。 一个算法面向一类问题，而不是仅求解问题的一个或几个实例。,15,1.2 问题表示,例如，排序（SORT）问题定义如下： Input= ai是实数 output= bi是实数,且b1.bn R=(,)Input， output,a1,.

7、,an= b1,.,bn,16,a0,.,n-1 = 5,2,4,6,1,3 a0,.,n-1 = 5,2,4,6,1,3 a0,.,n-1 = 2,5,4,6,1,3 a0,.,n-1 = 2,4,5,6,1,3 a0,.,n-1 = 2,4,5,6,1,3 a0,.,n-1 = 1,2,4,5,6,3 a0,.,n-1 = 1,2,3,4,5,6,算法的思想：扑克牌游戏,1.3 算法示例插入排序算法,17,算法描述,1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 4. 重

8、复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到该位置中 6. 重复步骤2,18,1.3 算法示例,插入排序算法 template void InsertionSort(Type *a, int n) / 数组a中包含了n个待排序的数. Type key; for (int i = 1; i =0 ,19,1.4 算法的正确性分析,正确的算法：对于每一个输入都最终停止,而且产生正确的输出。 不正确算法： 不停止(在某个输入上) 对所有输入都停止，但对某输入产生不正确结果 近似算法 对所有输入都停止 产生近似正确的解或产生不多的不正确解 算法正确性证明 证明算法对所有

9、输入都停止 证明对每个输入都产生正确结果,调试程序程序正确性证明！ 程序调试只能证明程序有错，不能证明程序无错误!,20,1.4 算法的正确性分析,算法正确性证明的步骤： 初始化 算法在循环的第一步迭代开始之前，应该是正确的。 保持 如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。 终止 当循环结束时，算法也应该是正确的。 分析前面插入排序算法的正确性,21,算法设计与分析的基本方法,1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。,22,2.递归 递归指的是

10、一个过程：函数不断引用自身，直到引用的对象已知 3.穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。,23,4.贪婪法 贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。,24,5.分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。,25,6.动态规

11、划法 动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。,26,7.迭代法 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。,27,提纲,一、算法与程序 二、算法复杂性分析 三、用C+语言描述算法的方法,28,同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法

12、。一个算法的评价主要从时间复杂度和空间复杂度来考虑。,29,二、算法复杂性分析,算法复杂性 = 算法所需要的计算机资源所需资源量越多则复杂性越高，反之所需资源量越少则复杂性越低。其中最为重要的是： 时间复杂性T(n)； 空间复杂性S(n)。 其中n是问题的规模（输入大小）。 示例： 一维数组问题的输入大小数组的长度 矩阵问题的输入大小=矩阵的维数 图论问题的输入大小=图的边数/结点数,30,决定算法复杂性的因素,算法的复杂性取决于 (1)求解问题的规模； (2)具体的输入数据； (3)算法本身的设计。,若令N、I、和A分别表示问题的规模、具体的输入和算法本身，则 C = F(N, I, A)

13、或 C = FA(N, I) = F( N, I),31,时间复杂性的计算,时间复杂性T(N, I)的计算为：,其中： ti为执行抽象计算机的第i种指令一次所需要的时间，这里假定抽象计算机共有k种指令。 ei(N, I)为经过统计后得到的执行抽象计算机的第i种指令的次数。,k T(N, I) = ti ei(N, I) i = 1,32,二、算法复杂性分析,算法分析的目的： 设计算法设计出复杂性尽可能低的算法 选择算法在多种算法中选择其中复杂性最低者,33,2.1 算法时间复杂性,最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n 最好情况下的时间复杂性 Tm

14、in(n) = min T(I) | size(I)=n 平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实例I出现的概率。,34,2.2 时间复杂性计算,为了能够较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。 例如，在考虑两个矩阵相乘时，可以将两个实

15、数之间的乘法运算作为基本运算.,35,2.2 时间复杂性计算,在一般的计算机系统中，基本的运算和操作有以下四类： 算术运算：主要包括加、减、乘、除等运算。 逻辑运算：主要包括“与”、“或”、“非”等运算。 关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。 数据传输：主要包括赋值、输入、输出等操作。 规定其中每条指令所需的时间都为常量。,算法的执行时间= 原子操作的执行次数原子操作的执行时间,36,template void InsertionSort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 / c7 n-1 ,2.2 时间复杂性计算,37,在最好情况下，ti=1, for 1 i n; 在最坏情况下，ti i+1, for 1 i n;,2.2 时间复杂性计算,38,算法的时间复杂度,如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。 最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。 最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n2)。 因而，插入排序不适合对于数据量比