第1章-算法引论.ppt

1、2020年7月7日星期二,1,联系方式: 办公地点:信息学院二层软件工程系204 办公电话:2020年7月7日星期二,2,学习算法的理由： 一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。 George Forsythe 计算机科学家到来以前我们做什么1968 算法是计算机科学的基石。学习算法的理由是非常充分的。没有算法，计算机程序将不复存在，另一个学习算法的理由是可以用它来开发人们的分析能力。 算法可以看作是解决问题的一类特殊方法它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。 因此，无论是否涉及计算机，特定的算法设计技术都能看作

2、是问题求解的有效策略。,2020年7月7日星期二,3,计算机专业的学生： 程序=算法+数据结构 算法让我们上一个更高的台阶 算法的魅力：思考,2020年7月7日星期二,4,对学生的要求: 坚持!坚持就是胜利! 看懂每一道讲授的题目、完成作业、完成实习题目。 上课：不旷课、不迟到。 作业：每章两个算法设计题，提交作业本。 实习：第二章第六章，每章一个算法实现题目，将程序的源代码的压缩文件，提交到202.117.179.110（作业管理系统王湘桃计算机13班）,2020年7月7日星期二,5,主要内容介绍,第1章算法引论 第2章递归与分治策略 第3章动态规划 第4章贪心算法 第5章回溯法 第6章分支

3、限界法,2020年7月7日星期二,6,主要内容介绍（续）,第7章概率算法 第9章NP完全性理论与近似算法,2020年7月7日星期二,7,第1章 算法引论,1.1算法与程序 1.2表达算法的抽象机制 1.3算法复杂性分析,本章主要知识点：,2020年7月7日星期二,8,1.1算法与程序,输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。,是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。,是满足下述性质的指令序列。,算法：,程序：,

4、2020年7月7日星期二,9,1.1算法与程序,求：非负整数M和N的最大公约数， 记为：Gcd(m,n) 方法一：欧几里得算法 Gcd(m,n)=Gcd(n, m mod n) Gcd(60,24)=Gcd(24,12)=Gcd(12,0)=12,2020年7月7日星期二,10,1.1算法与程序,方法二：连续整数检测算法 （1）将 min(m,n) 的值赋给t。 （2）m除以t，如果余数为0，进入第3步，否则，进入第4步。 （3）n除以t，如果余数为0，返回t值，结束，否则，进入第4步。 （4）t=t-1 ，返回第2步。,2020年7月7日星期二,11,1.1算法与程序,方法三：中学里计算Gc

5、d(m,n)的过程（用数学定义的方法） （1）找到m的所有质因数。 （2）找到n的所有质因数。 （3）找到（1），（2）中的公因数。 （4）求公因数的积，该乘积为m、n的最大公约数。,2020年7月7日星期二,12,1.1算法与程序,理解问题 在设计一个算法前，我们需要做的第一件事就是完全理解所给出的问题，仔细阅读问题的描述，如有任何疑惑就把疑问提出来，手工处理一些小例子，考虑一下特殊情况，有必要的话再继续提出疑问。 严格确定算法需要处理的实例范围是非常重要的。如果不这样做，算法可能会对大多数的输入正确处理，但遇到某些“边界值”的时候就出错。 记住，一个正确的算法不仅应该能处理大多数的情况，而

6、且应该能正确处理“所有”合法的输入。,2020年7月7日星期二,13,1.1算法与程序,了解计算机设备的性能 今天使用的大多数算法仍然要运行于冯诺依曼计算机上。这个体系结构的重点在于随机存取机。它最主要的设想是：指令逐条运行，每次执行一步操作。相应地，设计运行于这种机器上的算法，称为顺序算法。 一些更新式的计算机可以在同一时间执行多条操作，即并行计算，能够利用这种计算性能优势的算法称为并行算法。 尽管如此，在可预见的未来，学习RAM模型下算法设计和分析的经典技术仍然是算法学的基石。,2020年7月7日星期二,14,1.1算法与程序,在精确解法和近似解法间做选择 精确的解法称为精确算法。 近似的

7、解法称为近似算法。（无法求得精确解求平方根问题或由于某些问题固有的复杂性，用已知的精确算法来解决该问题会慢得无法接受旅行售货员问题）,2020年7月7日星期二,15,1.1算法与程序,确定适当的数据结构 算法和数据结构是计算机编程的重要基础。 程序=算法+数据结构,2020年7月7日星期二,16,1.1算法与程序,算法设计技术 什么是算法设计技术？是用算法解题的一般性方法。用于解决不同计算领域的多种问题。 在给新问题设计算法时，能够给予指导，另外，算法设计技术可以按照内在设计理念对算法进行分类，设计技术使我们能够以一种自然的方式对算法进行分类和研究。,2020年7月7日星期二,17,1.1算法

8、与程序,详细表述算法的方法 用文字和伪代码描述。 文字表述有逻辑缺陷。 伪代码是自然语言和类编程语言组成的混合结构。,2020年7月7日星期二,18,1.1算法与程序,证明算法的正确性 必须证明算法的正确性，就是说，我们必须证明对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。 证明正确性的一般方法是使用数学归纳法。 为了表明算法是不正确的，只需提供一个算法不能正确处理的输入实例。 对于近似算法来说，常常试图证明该算法所产生的误差不超出我们预定的范围。,2020年7月7日星期二,19,1.1算法与程序,分析算法 算法有两种效率：时间效率和空间效率。 时间效率显示算法运行得有

9、多快。 空间效率显示算法需要多少额外的存储空间。 算法的另外两个特性：简单性和一般性。 一般性有两层意思：算法解决问题的一般性和算法所接受输入的一般性。,2020年7月7日星期二,20,1.1算法与程序,为算法写代码 对算法进行编程既是挑战也是机遇。挑战在于，在把算法转变为程序的过程中，可能会发生错误或者效率非常低。（大多数计算机科学家坚信，除非计算机程序的正确性在数学上得到了完全严格的证明，否则，我们不能认为程序是正确的。） 运行中的程序为我们提供了一个分析它内在算法的额外机会。这也是我们要把算法变成程序的另一个原因。,2020年7月7日星期二,21,1.1算法与程序,1理解问题 、2了解计

10、算机设备的性能 3在精确解和近似解间作出选择 4描述算法的方法、5证明算法的正确性 6算法设计技术、7确定适当的数据结构 8分析算法、9为算法写代码 最后，让我们再强调一下算法设计与实现的主要含义：作为一个规律，一个好的算法是反复努力和重新修正的结果。,2020年7月7日星期二,22,1.从机器语言到高级语言的抽象,1.2表达算法的抽象机制,高级程序设计语言的主要好处是：,（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。,（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程

11、序员的工作；,（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；,2020年7月7日星期二,23,2.抽象数据类型,1.2表达算法的抽象机制,抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。,抽象数据类型带给算法设计的好处有：,（1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类

12、型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。,2020年7月7日星期二,24,1.3算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量， 需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：

13、 T=T(N,I)和S=S(N,I) 。 （通常，让A隐含在复杂性函数名当中）,2020年7月7日星期二,25,1.3算法复杂性分析,分析框架： 有两种算法效率：时间效率和空间效率。 时间效率：指出正在讨论的算法运行得有多快。 空间效率：算法需要的额外空间。,2020年7月7日星期二,26,1.3算法复杂性分析,输入规模的度量 几乎所有的算法，对于规模更大的输入都需要运行更长的时间。使用一个以算法输入规模N为参数的函数，来研究算法效率是非常合乎逻辑的。 选择输入规模的合适度量，要受到所讨论算法的操作细节的影响。例如：对于一个拼写检查算法，如何度量其输入规模呢？如果算法对于输入的每一个独立字符都

14、要做检查，应该使用字符的数量来度量输入规模。如果它的操作是以词为单位的，应该统计输入中词的数量。,2020年7月7日星期二,27,1.3算法复杂性分析,运行时间的度量单位 统计算法每一步操作的执行次数。 基本操作：对总运行时间贡献最大的操作。 算法中的基本操作：通常是算法最内层循环中最费时间的操作。 例如：排序：对关键词的比较。 矩阵相乘：乘法和加法 建立一个算法时间效率的分析框架：对于输入规模为N的算法统计它的基本操作执行次数，来对其效率进行度量。 约定：Cop为特定计算机上一个算法基本操作的执行时间。 C(N)是该算法需要执行基本操作的次数。 对运行在那台计算机上的某个算法程序的运行时间，

15、用以下公式估计： T(N)=CopC(N),2020年7月7日星期二,28,1.3算法复杂性分析,增长次数：一年的秒数=3.1536*107,2020年7月7日星期二,29,1.3算法复杂性分析,渐进符号和基本效率类型 效率分析框架主要关心一个算法的基本操作次数的增长次数，并把它作为算法效率的主要指标。为了对这些增长次数进行比较和归类，计算机科学家使用3种符号：O，。T(n)和G(n)是定义在自然数集合上的任意非负函数。T(n)是一个算法的运行时间（常常用基本操作次数C(n)来表示）。G(n)是一个用来和该操作次数做比较的函数。,2020年7月7日星期二,30,1.3算法复杂性分析,当问题规模

16、增大时，复杂度的极限行为称为算法的渐进时间复杂度。,假设下一代计算机的速度是目前的10倍，下表是计算机加速后在相同的时间内可以解决的问题规模增量。,2020年7月7日星期二,31,1.3算法复杂性分析,基本的效率类型 如果一个算法的运行时间是n3，另一个算法的运行时间是106n2；除非n比106还大，否则，立方算法的表现会超过平方算法。我们的确知道这样一些算法。例如：有一些矩阵乘法算法的渐进效率要好于基于定义的立方算法。然而，因为它们的乘法常量值过大，这些非常精美的算法在绝大多数情况下只具有理论价值。 幸运的是，乘法常量之间通常不会相差那么悬殊。作为一个规律，即使是中等规模的输入，一个属于较优

17、渐进效率类型的算法也会比一个来自于较差类型的算法表现得更好。如果拿效率好于指数级的算法与指数级（或者更糟糕）的算法相比，这个规律会更加明显。,2020年7月7日星期二,32,1.3算法复杂性分析,设T(n)是关于算法A的复杂性函数。一般说来，当N单调增加且趋于时，T(n)也将单调增加趋于 。对于T(n)，如果存在t(n)，使得当n 时有(T(N)-t(n)/T(N) 0，那么，我们就说t(n)是T(n)当n 时的渐进性态。 因为在数学上，t(n)是T(n)当n时的渐进表达式，直观上，t(n)是T(n)中略去低阶项所留下的主项，所以它无疑比T(n)来得简单。 例如：T(n)=3n2+4nlogn

18、+7时， t(n)的一个答案是3n2。,2020年7月7日星期二,33,1.3算法复杂性分析,算法的最差、最优和平均效率 一个算法的最差效率：是指当输入规模为N时，算法在最坏情况下的效率。 一个算法的最优效率：是指当输入规模为N时，算法在最优情况下的效率。 一个算法的平均效率：在“典型”或者“随机”输入的情况下，算法会具有什么样的行为,2020年7月7日星期二,34,1.3算法复杂性分析,最坏情况下的时间复杂性：,最好情况下的时间复杂性：,平均情况下的时间复杂性：,其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*) 达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。,2020年7月7日星期二,35,1.3算法复杂性分析,算法复杂性在渐近意义下的阶：,渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数。,O的定义：如果存在正的常数C和自然数N0，使得当NN0时