第1章 算法引论

《第1章 算法引论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法引论课程目标算法理论研究的是算法的设计和分析技术，前者是指面对一个问题，如何设计一个有效的算法；后者是指对已有算法，如何评价或判断其优劣。提纲算法的基本概念算法的基本概念为什么要学习算法算法分析算法及其重要特性数学预备知识算法的描述方法数据结构算法设计的一般过程重要的问题类型枚举法（蛮力法）为什么要学习算法对程序设计的研究可以分为四个层次：学科核心：用计算机求解任何问题都离不开程序设计，而程序工具TuborC,VC++,.Net,….设计的核心是算法设计。引例：烤蛋糕配料语言Cobol,Fortran,Pascal,C,….魔法般配料

2、：input的指示有限能（软件）（硬件）力方法学食谱：algorithm面向过程，面向对象，面向架构食谱烤箱蛋糕：output器具面包师算法快速排序，折半查找，迪杰斯特拉实例：更换漏气的轮胎制造自制橱柜蛋糕查电话号码等1提升能力：学习算法还能够提高人们分析问题的能力。算法的基本概念算法可以看作是解决问题的一类特殊方法——它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。Knuth：为什么要学习算法“将知识表述为一种算法……比起简单地按照常规去理解事物，用算法及其重要特性算法将其形式化会使我们获得更加深刻的理解。”算法的描述方法推动发展：算法研究始终

3、是推动计算机技术发展的关键。算法设计的一般过程1.检索技术：大规模数据2.压缩与解压缩：多媒体重要的问题类型3.信息安全与数据加密：电子商务算法及其重要特性算法的基本概念算法（Algorithm）：通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，为什么要学习算法是指令的有限序列。算法及其重要特性⑴输入：一个算法有零个或多个输入⑵输出：一个算法有一个或多个输出算法的描述方法⑶有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束。算法设计的一般过程⑷确定性：算法中给出的每一个计算步，必须是精确地定义的，重要的问题类

4、型无二义性的。⑸可行性：算法中要执行的每一个计算步都是可以在有限时间内做完的。算法的描述方法⑴自然语言细节的程度和抽象例：求两个正整数a和b的最大公约数（辗转相除法）：食谱取365克粉1.a÷b，令r为所得余数（0≤r

5、差，描述算法的具体细节，很难观察算法的灵活性不如自然语言，严密整体逻辑。性不如程序设计语言a←bb←rFr=0T输出a辗转相除法的伪代码描述⑷伪代码1.Readm,n;伪代码（Pseudocode）是介于自然语言和程序设计语言2.循环直到n=0之间的描述语言，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。2.1r=m%n;2.2m=n;2.3n=r;伪代码不是一种实际的编程语言，但在表达能力上类3.输出m;似于编程语言，同时极小化了程序语言中的技术细节，是比较合适的描述算法的方法，被称为“算法语言”算法的基本概念算法设计的一般过程理解问题为什么

6、要学习算法预测所有可能的输入算法及其重要特性确定：精确解还是近似解算法的描述方法确定数据结构算法设计技术算法设计的一般过程设计并描述算法重要的问题类型跟踪算法分析算法的效率不满意满意根据算法编写代码3算法的基本概念重要的问题类型为什么要学习算法计算领域感兴趣的问题（问题重要）(1).查找问题算法及其重要特性(2).排序问题算法的描述方法(3).图问题算法设计的一般过程(4).组合优化问题重要的问题类型(5).几何问题提纲算法分析对算法有效性的度量：时间和空间，即当给出合法输算法的基本概念入时，为了得到输出，该算法所需要的时间和空间算法分析

7、200180x2/8数学预备1603*x2140x+101202*logx数据结构100806040200261014182226303438渐进符号•时间:用来表示算法的渐进运行时间的记号是用定义域为自然数N={0,1,2,…}的函-当问题规模为n时，基本操作重复执行的次数数来定义的。例：f(n)=n2+3n+5大O符号（经常使用）•关心大规模的输入数据:定义令f(n)和g(n)是两个函数，如果存在一个自然数n0和一个正常数-c，对于任意n≥n0，都有f(n)≤c×g(n)，则称f(n)=O(g(n))。在小输入数据上讨论算法一般没有意义•增长的阶:执