《算法设计：第一讲——2013.ppt》由会员分享，可在线阅读，更多相关《算法设计：第一讲——2013.ppt（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与复杂度计算算法分析与复杂度计算主讲教师：徐红艳主讲教师：徐红艳u计算机系统中的任何软件（系统软件、应用软件）计算机系统中的任何软件（系统软件、应用软件）都是按照特定的算法来实现的。都是按照特定的算法来实现的。u算法的好坏直接决定所实现软件性能的优劣。算法的好坏直接决定所实现软件性能的优劣。课程简介课程简介u设计软件时需要解决的问题：设计软件时需要解决的问题：（1 1）用什么方法）用什么方法设计设计软件软件（2 2）设计的算法需要什么样的资源）设计的算法需要什么样的资源（3 3）需要多少运行时间）需要多少运行时间（4 4）需要多少存储空间）需要多少存储空间分析分析算法设计与分析是计算机
2、科学与技术的一个核心问题。算法设计与分析是计算机科学与技术的一个核心问题。课程简介课程简介设计设计参考教材：1、王晓东.算法设计与分析（第算法设计与分析（第2版）版）.清华大学出版清华大学出版社社.2、潘彦.算法设计与分析基础（第算法设计与分析基础（第2版）版）.清华大学出清华大学出版社版社.3、郑宗汉.算法设计与分析算法设计与分析.清华大学出版社.课程简介课程简介l课程的侧重点：课程的侧重点：w算法设计算法设计第三章：算法设计的基本工具和优化技术第三章：算法设计的基本工具和优化技术第四章：通用的算法设计基本策略第四章：通用的算法设计基本策略第五章：复杂问题的算法设计策略第五章：复杂问题的算法
3、设计策略第六章：采用不同策略解决相同问题，并进行第六章：采用不同策略解决相同问题，并进行效率分析。效率分析。w算法分析：对设计的算法进行时间和空间复杂度算法分析：对设计的算法进行时间和空间复杂度的分析。的分析。课程简介课程简介 第 一 章 算 法 概 述l人类使用计算机的目的：计算机作为工具，帮助人类使用计算机的目的：计算机作为工具，帮助人类求解问题。人类求解问题。l算法设计的重点：把人类找到的求解问题的方法、算法设计的重点：把人类找到的求解问题的方法、步骤以过程化、形式化和机械化的形式表现出来，步骤以过程化、形式化和机械化的形式表现出来，以便让计算机执行。以便让计算机执行。l算法分析：是对一
4、个算法需要多少计算时间和存算法分析：是对一个算法需要多少计算时间和存储空间作定量的分析储空间作定量的分析 复杂度计算。复杂度计算。1 11 1 用计算机求解问题与算法用计算机求解问题与算法1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤l人在解决问题时有很大的灵活性，对于同一个问题，不同的人有不同的经验，会采用不同的方法，如何用计算机解决一个现实中的问题呢？虽然有很多不同的方法，但基本步骤是相同的。1.问题分析2.数学模型建立3.算法设计与选择4.算法表示5.算法分析6.算法实现7.程序调试8.结果整理文档编制用计算机解决一个现实中的问题步骤：用计算机解决一个现实中的问题步骤：
5、1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤问题分析:准确、完整地理解和描述问题是解决问题的第一步。数学模型建立:用计算机解决实际问题必须有合适的数学模型。算法设计与选择:算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤算法分析:对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。通常将时间和空间的增长率作为衡量的标准。1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤算法表示：
6、算法表示：对于复杂的问题，确定算法后可以通过图形准确表示算法。算法的表示方式很多如：算法流程图、盒图、PAD图和伪码（类似于算法设计语言）等。算法实现：算法实现：根据选用的程序设计语言，编写出计算机能够执行的程序。1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤程序调试：程序调试：算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤结果整理文档编制：编制文档的目的是让人了解结果整理文档编制：编制文档的目的是
7、让人了解你编写的算法。你编写的算法。n在这些步骤中，算法设计是解决问题的核心。其在这些步骤中，算法设计是解决问题的核心。其次是针对设计的算法进行复杂度分析。次是针对设计的算法进行复杂度分析。1 11 11 1 用计算机求解问题的步骤用计算机求解问题的步骤1 11 12 2 算法及其要素和特性算法及其要素和特性l算法的定义：算法的定义：算法是求解某一特定问题的一组有穷规则的集合。l算法的要素：算法的要素：操作：算术运算、关系比较、逻辑运算、数据传送（I/O，赋值等）控制结构：顺序、选择、循环控制（也称迭代）数据结构：数据的逻辑结构及存储结构1 11 12 2 算法及其要素和特性算法及其要素和特性
8、l算法的基本性质：算法的基本性质：目的性：能完成赋予它的功能分步性：由一系列计算机可执行的步骤组成有序性：不可随意改变算法步骤的执行顺序 有限性：算法所包含的步骤是有限的。操作性：算法总是对某些对象进行操作，使其状态改变，完成特定功能。l算法的基本特征算法的基本特征有穷性:一个算法在执行有穷步之后必须结束，而且要求运行这些步骤的时间是人们可以接受的。确定性:在任何条件下，算法都只有一条执行路径。可行性:算法中描述的操作都可以通过已经实现的基本操作运算有限次实现。输入：有零个或多个输入输出：有一个或多个输出1 11 12 2 算法及其要素和特性算法及其要素和特性1 11 13 3 算法设计及基本
9、方法算法设计及基本方法l算法设计的概念：算法设计的概念：其任务是对各类具体问题设计良好的算法。l算法设计应注意的问题算法设计应注意的问题正确性（Correctness）可读性(Readability)健壮性（Rubustness）高效率与低存储量需求l算法设计的基本方法算法设计的基本方法结构化方法“自顶向下,逐步求精”w“自顶向下”是将复杂、大的问题划分为小问题。w“逐步求精”是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。1 11 13 3 算法设计及基本方法算法设计及基本方法面向对象方法w对象=数据+对数据操作的代码实体w面向对象算法设计方法的过程包括以下步骤：在给定的抽象层次上识
10、别类和对象 识别这些对象和类的语义 识别类和对象之间的关系 实现类和对象1 11 13 3 算法设计及基本方法算法设计及基本方法l本书采用的设计方法本书采用的设计方法结构化设计方法结构化设计方法 自顶向下模块化分解过程w把一个较大的算法划分为若干子算法w每一个模块可继续划分为更小的子模块w直到用三种控制结构和具体操作表示算法注：注：运用这种编程方法，考虑问题必须先进行整体运用这种编程方法，考虑问题必须先进行整体分析。分析。1 11 13 3 算法设计及基本方法算法设计及基本方法模块划分的基本要求简单性、独立性和完整性w模块的功能尽可能地单一化、明确化w模块间的联系及相互影响尽可能地小w模块的规
11、模应当足够小，以便于调试1 11 13 3 算法设计及基本方法算法设计及基本方法算法设计的基本方法w抽象：包括算法的抽象和数据抽象。算法抽象是指算法的寻求(或开发)采用逐步求精、逐层分解的方法。数据抽象也指在算法抽象的过程中逐步完善数据结构和引入新的数据及确定关于数据的操作。w枚举：“枚举”一些真实数据w归纳：“归纳”出算法的细节1 11 13 3 算法设计及基本方法算法设计及基本方法121 算法描述简介l算法是对解题过程的精确描述。算法是对解题过程的精确描述。l算法算法 =控制结构+原操作l表示算法的语言主要有：表示算法的语言主要有：自然语言流程图伪代码计算机算法设计语言l本书采用类C语言的
12、伪代码描述，具体细节约定如下：三种基本控制结构的描述三种基本控制结构的描述数据结构说明数据结构说明模块及模块间的接口方式的描述模块及模块间的接口方式的描述其它细节说明其它细节说明 122 本书算法描述约定1 12 23 3 一个简单问题的求解过程一个简单问题的求解过程l问题求解的步骤可以简化为三步问题求解的步骤可以简化为三步问题分析：在对问题进行认真分析的基础上，确认问题的逻辑结构和问题的基本功能，并在数学、物理等问题领域相关知识的基础上建立数学模型。算法设计：找出解决问题的处理步骤 算法分析：对数学模型的建立、数据结构的选择及算法设计工作的评价、总结。【例例】求二个正整数的最大公约数。求二个
13、正整数的最大公约数。l问题分析：此题只需有小学知识，就可有以下建此题只需有小学知识，就可有以下建立以下的数学模型。立以下的数学模型。l数学模型：a a，b0 b0 的整数，求的整数，求c c，c c能整除能整除a a，b b，且且a/ca/c与与b/cb/c互质。互质。l算法设计：通过：通过“枚举尝试枚举尝试”（逐个尝试）就可（逐个尝试）就可以以“试出试出”a,ba,b有哪些是公约数，并将这些公约数有哪些是公约数，并将这些公约数“累乘累乘”，就能得到最大公约数。，就能得到最大公约数。1 12 23 3 一个简单问题的求解过程一个简单问题的求解过程l算法描述如下：zdgyszdgys()()in
14、tint a,b,c,ia,b,c,i;input input（a,ba,b）;c=1 c=1；/变量变量c c是为累乘因数而设置的；是为累乘因数而设置的；for(i=2;i=a and i=b;i+)/“for(i=2;i=a and i=b;i+)/“枚举枚举”可能的公约数可能的公约数 while while (a%ia%i=0 and=0 and b%ib%i=0)=0)/“/“试试”i i是否为公约数是否为公约数 c=c*i;c=c*i;a=a/i;a=a/i;b=b=b/ib/i;print(“%dprint(“%d is maximal common is maximal comm
15、on divisor”,cdivisor”,c););l算法效率分析：由于算法是盲目地尝试可能的因由于算法是盲目地尝试可能的因数，比较操作次数较多，所以算法的效率并不高。数，比较操作次数较多，所以算法的效率并不高。l“问题分析、建模、算法设计要点、算法分析问题分析、建模、算法设计要点、算法分析”是是解决问题的必然过程。解决问题的必然过程。1 12 23 3 一个简单问题的求解过程一个简单问题的求解过程l 下面是算法设计时需要注意的一些问题：下面是算法设计时需要注意的一些问题：通过输入语句增加算法的通用性会忘掉“输出”或在模块间传递处理的数据结果易忽略细节造成“死循环”。出现语序方面的错误，特别
16、是双重循环中指令常有嵌套错误。1 12 23 3 一个简单问题的求解过程一个简单问题的求解过程注意学习和总结。用大脑“运行”算法是学习算法很好的方法。解题时要学会择优。简单说择优要考虑四个方面：可读性、可修改性、时间效率和空间效率。1 12 23 3 一个简单问题的求解过程一个简单问题的求解过程 第 二 章 算 法 分 析 基 础算法分析的重要性1、百钱买百鸡问题、百钱买百鸡问题 问题叙述：问题叙述：“鸡翁一，值钱五；鸡母一，值钱三；鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？各几何？”算法实现（算法实现（算法实现
17、（算法实现（1 1）及分析）及分析）及分析）及分析 算法实现（算法实现（2）及分析）及分析算法分析的重要性2 2、货郎担问题、货郎担问题 问题描述：某售货员要到若干个城市销售货物，问题描述：某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每个城市仅经过一次，最后城市及旅行路线，使每个城市仅经过一次，最后回到原出发城市，而总路程最短。回到原出发城市，而总路程最短。问题分析算法实现算法分析算法分析的重要性l算法效率的衡量标准：算法的复杂度，包括算法的算法效率的衡量标准：算法的复杂度，包括算法的时间复杂度和空间复杂
18、度。时间复杂度和空间复杂度。l算法分析的任务：对设计出的每一个具体的算法算法分析的任务：对设计出的每一个具体的算法,利用数学工具，讨论其复杂度。利用数学工具，讨论其复杂度。2.1.1 算法分析的评价体系l人对算法的维护主要有编写、调试、改正和功能扩充等工作,这就需要在算法设计时注重算法的可可读性读性。l机器对算法的运行效率主要包括时间效率和空间效率。算法在完成功能的前题下最好是占用空间少而且执行时间短。l算法实现时,要考虑算法在运行过程中与使用者进行交互的情况。这就要求,算法的交互部分要具有友好性友好性和健壮性健壮性。l总之，对算算法法的的分分析析和和评评价价，一般应考虑正确性、可维护性、可读
19、性、运算量及占用存储空间等诸多因素。其中评价算法的三条主要标准标准是：(1)算法实现所耗费的时间时间；(2)算法实现所所耗费的存储空间空间，其中 主要考虑辅助存储空间；(3)算法应易于理解理解，易于编码，易于调 试。2.1.1 算法分析的评价体系 1.1.和算法执行时间相关的因素和算法执行时间相关的因素：1）问题中数据存储的数据结构2）算法采用的数学模型 3）算法设计的策略4 4）问题的规模）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度 2.1.2 算法的时间复杂性假定：百钱买百鸡的问题中，其最内部的循环体每执行一次需要1s时间。算法的输入
20、规模和运行时间的阶：算法的输入规模和运行时间的阶：n=100n=10000内循环次数内循环次数时间时间内循环次数内循环次数时间时间算法算法1100万次万次1s10000311d 13h算法算法2714次次714s（10000/5+1)(10000/3+1)6.7s对对n=220个数进行排序，选择排序需个数进行排序，选择排序需64天，天，合并排序需要合并排序需要20秒秒通过上面问题的分析，可以知道：（1）算法的执行时间随着问题规模的增大而增长，增长的速度随不同的算法而不同。（2）没有一个方法能准确的计算出算法的执行时间。原因算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：算法的输入规
21、模和运行时间的阶：算法的输入规模和运行时间的阶：算法的运行时间表示为一个与输入规模n相关的函数f(n)，反映算法的运行时间随着输入规模的增长而增长的情况。若将问题的输入规模设为n，则百钱买百鸡：算法1的时间花费估算：第4行：1 第5行：1+2（n+1)第6行：(n+1)+2(n+1)2 第7行：（n+1）2+2(n+1)3 第8行：14（n+1）3 第9、10、11、12行：不超过4(n+1)3算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：则该算法的时间花费T1(n)算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：算法的输入规模和运行时间
22、的阶：随着n的增大，例如当n=100万时，算法的主要执行时间主要取决于算式中的第一项，而且随着n的增大，第一项的系数对算法的执行时间也变得不重要，于是，可把T1(n)改写为：这时，称 的阶是 百钱买百鸡：算法2的时间花费估算：第4行：1 第5、6行：各2个 2*2=4 第7行：1+2(n/5+1)第8行：（n/5+1）+2(n/5+1)(n/3+1)第9行：3(n/5+1)(n/3+1)第10行：10(n/5+1)(n/3+1)第11、12、13、14行：不超过4(n/5+1)(n/3+1)算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：算法的输入规模
23、和运行时间的阶：这时，称 的阶是 算法的输入规模和运行时间的阶：算法的输入规模和运行时间的阶：把T1*(n)和T2*(n)进行比较，有 当n很大时，c1/c2的作用很小。通常有两种衡量算法效率衡量算法效率的方法:1）事后统计法（有缺点，较少使用）2）事前分析估算法 算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=T(n)=(f(n(f(n)。算法效率的衡量方法算法效率的衡量方法定义定义2.12.1设算法的执行时间为T(n)，如果存在T*(n)，使：称T*(n)为算法的渐进时间复杂度。在算法分析中用渐进时间复杂性来衡量一
24、个算法的时间复杂性。在百钱买百鸡问题中：（1）算法1的时间性为T1*(n)，它的阶是n3（2）算法2的时间性为T2*(n)，它的阶是n2表示时间复杂性的阶为：表表1：不同时间复杂性下不同输入规模的运行时间：不同时间复杂性下不同输入规模的运行时间时间复杂度时间复杂度假定在计算机C1和C2上运行这些算法（1）C2机的速度是C1机的10倍。（2）这些算法在C1机上的运行时间为T，可处理的输入规模是n1（3）在C2机上运行同样时间，可处理的规模扩大为n2表表2：计算机速度提高，不同算法复杂性求解规模的扩大：计算机速度提高，不同算法复杂性求解规模的扩大假定A1,A2,A3,A6是求解同一个问题的6个算法
25、，它们的时间复杂度分别为：时间复杂度时间复杂度前4种时间复杂性：与输入规模与输入规模n的一个确定的幂同阶，计算机运算速度的一个确定的幂同阶，计算机运算速度的提高，可以使阶梯规模以一个常数因子的倍数增的提高，可以使阶梯规模以一个常数因子的倍数增加。通常把这类算法称为加。通常把这类算法称为多项式时间算法多项式时间算法。后2种时间复杂性：称为称为指数时间算法指数时间算法。时间复杂度时间复杂度运行时间的上界，运行时间的上界，O O记号：记号：在百钱买百鸡问题中：（1）算法1执行基本操作的步骤至多为C1*n3，当n的规模增大时，常数C1对运行时间的影响不大，则算法1的运行时间的上界写成：O(n3)（2）
26、同理，算法2的的运行时间的上界写成：O(n2)运行时间的上界，运行时间的上界，O O记号：记号：在一般情况下，当输入规模大于或等于某个阈值n0时，算法运行时间的上界是某个正常数C的g(n)倍，就称算法的运行时间至多至多是O（g(n)。O记号的定义如下：定义：定义：令令N N为自然数集合，为自然数集合，R+R+为正实数集合。函数为正实数集合。函数f f：NR+NR+，函数，函数g g：NR+NR+，若存在自然数，若存在自然数n n0 0和正常数和正常数c c，使得对所有的使得对所有的nnnn0 0 ，都有，都有f(nf(n)cg(ncg(n)，就称函数，就称函数f(nf(n)的阶至多是的阶至多是
27、O(g(nO(g(n)。运行时间的上界，运行时间的上界，O O记号：记号：因此，如果存在 则：即意味着：f(n)=O(g(n)这个定义表明：f(n)的增长至多象g(n)的增长那样快。这时称O(g(n)是f(n)的上界。举举 例例运行时间的下界，运行时间的下界，记号：记号：在百钱买百鸡问题中：（1）第11、12、13、14行，仅在条件成立时才执行，其执行次数未知。（2）假定条件都不成立，这些语句一次也没有执行，该算法的执行时间至少为：算法执行时间计算算法执行时间计算运行时间的下界，运行时间的下界，记号：记号：在一般情况下，当输入规模大于或等于某个阈值n0时，算法运行时间的下界是某个正常数C的g(
28、n)倍，就称算法的运行时间至少至少是 (g(n)。记号的定义如下：定义：定义：令令N N为自然数集合，为自然数集合，R+R+为正实数集合。函数为正实数集合。函数f f：NR+NR+，函数，函数g g：NR+NR+，若存在自然数，若存在自然数n n0 0和正常数和正常数c c，使得对所有的使得对所有的nnnn0 0 ，都有，都有f(n)f(n)cg(ncg(n)，就称函数，就称函数f(nf(n)的阶至少是的阶至少是(g(n(g(n)。运行时间的下界，运行时间的下界，记号：记号：因此，如果存在 则：即意味着：f(n)=(g(n)这个定义表明：f(n)的增长至少象g(n)的增长那样快。这时称 (g(
29、n)是f(n)的下界。举举 例例运行时间的准确界，运行时间的准确界，记号：记号：在百钱买百鸡问题的算法2中：（1）运行时间的上界是13n2，下界是n2。（2）这表明不管输入规模如何变化，该算法的运行时间都介于n2和13n2之间。（3）这时，用记号来表示这种情况，认为这个算法的运行时间是(n2)。（4）记号表明算法的运行时间有一个较准确的界。运行时间的准确界，运行时间的准确界，记号：记号：在一般情况下，当输入规模大于或等于某个阈值n0时，算法运行时间以c1g(n)为其下界，以c2g(n)为其上界，其中（0c1 c2）,就认为算法的运行时间是 (g(n)。记号的定义如下：定义：定义：令令N N为自
30、然数集合，为自然数集合，R+R+为正实数集合。函数为正实数集合。函数f f：NR+NR+，函数，函数g g：NR+NR+，若存在自然数，若存在自然数n n0 0和两个正常和两个正常数数0c1 c2 ，使得对所有的，使得对所有的nnnn0 0 ，都有，都有c c1 1g(n)g(n)f(n)f(n)c c2 2g(n)g(n)，就称函数，就称函数f(nf(n)的阶是的阶是(g(n(g(n)。复杂性类型和复杂性类型和o o记号记号定义：定义：令令N N为自然数集合，为自然数集合，R+R+为正实数集合。函数为正实数集合。函数f f：NR+NR+，函数，函数g g：NR+NR+，若存在自然数，若存在自
31、然数n n0 0和正常和正常c，使，使得对所有的得对所有的nnnn0 0 ，都有，都有f(n)f(n)cg(ncg(n)，就称函数，就称函数f(nf(n)的阶是的阶是o o(g(n(g(n)。复杂性类型和复杂性类型和o o记号记号因此，如果存在 则：即意味着：f(n)=o o(g(n)这个定义表明：随着趋于非常大，f(n)相对于g(n)变得不重要。举举 例例复杂性类型和复杂性类型和o o记号记号因此，如果存在 则：即意味着：f(n)=o o(g(n)这个定义表明：这个定义表明，随着趋于非常大，f(n)相对于g(n)变得不重要。举举 例例复杂性类型和复杂性类型和o o记号记号可以用偏序关系 来表示f(n)=o(g(n)在算法分析中，经常遇到如下一些类型的复杂性，它们的复杂性关系为：