《第1章 算法引论精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 算法引论精选文档.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1章章 算法引论算法引论2023/4/91本讲稿第一页，共三十七页联系方式联系方式:办公地点办公地点:信息学院二层软件工程系信息学院二层软件工程系204 办公电话办公电话:029-87091249 2023/4/92本讲稿第二页，共三十七页学习算法的理由：学习算法的理由：一个人接受科技教育得到的最大收获，是那些能够受用一一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。生的一般性智能工具。George Forsythe 计算机科学家到来以计算机科学家到来以前我们做什么前我们做什么1968算法是计算机科学的基石。学习算法的理由是非常充分的。算法是计算机科学的基石。学习算法
2、的理由是非常充分的。没有算法，计算机程序将不复存在，另一个学习算法的理由没有算法，计算机程序将不复存在，另一个学习算法的理由是可以用它来开发人们的分析能力。是可以用它来开发人们的分析能力。算法可以看作是解决问题的一类特殊方法算法可以看作是解决问题的一类特殊方法它虽非问题的答案，它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。但它是经过准确定义的，用来获得答案的过程。因此，无论是否涉及计算机，特定的算法设计技术都能看作因此，无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。是问题求解的有效策略。2023/4/93本讲稿第三页，共三十七页计算机专业的学生：计算机专业的
3、学生：程序程序=算法算法+数据结构数据结构 算法让我们上一个更高的台阶算法让我们上一个更高的台阶算法的魅力：算法的魅力：思考思考 2023/4/94本讲稿第四页，共三十七页对学生的要求对学生的要求:坚持坚持!坚持就是胜利坚持就是胜利!看懂每一看懂每一道讲授的题目、完成作业、完成实道讲授的题目、完成作业、完成实习题目。习题目。上课：不旷课、不迟到。上课：不旷课、不迟到。作业：每章两个算法设计题，提交作业本。作业：每章两个算法设计题，提交作业本。实习：第二章实习：第二章第六章，每章一个算法实现题目，将程序的第六章，每章一个算法实现题目，将程序的源代码的压缩文件，提交到源代码的压缩文件，提交到202
4、.117.179.110（作业管理（作业管理系统系统王湘桃王湘桃计算机计算机13班）班）2023/4/95本讲稿第五页，共三十七页主要内容介绍主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法2023/4/96本讲稿第六页，共三十七页主要内容介绍（续）主要内容介绍（续）第7章概率算法第9章NP完全性理论与近似算法2023/4/97本讲稿第七页，共三十七页第第1 1章章 算法引论算法引论1.1 算法与程序1.2 表达算法的抽象机制1.3算法复杂性分析本章主要知识点：2023/4/98本讲稿第八页，共三十七页1.1算法与程序算法与程序输输 入：有
5、零个或多个外部量作为算法的输入。入：有零个或多个外部量作为算法的输入。输输 出：算法产生至少一个量作为输出。出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。每条指令的时间也有限。是算法用某种程序设计语言的具体实现。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)即有限性。即有限性。是满足下述性质的指令序列。是满足下述性质的指令序列。算法：程序：2023/4/99本讲稿第九页，共三
6、十七页1.1 算法与程序算法与程序 求：非负整数求：非负整数M和和N的最大公约数，的最大公约数，记为：记为：Gcd(m,n)方法一：欧几里得算法方法一：欧几里得算法 Gcd(m,n)=Gcd(n,m mod n)Gcd(60,24)=Gcd(24,12)=Gcd(12,0)=122023/4/910本讲稿第十页，共三十七页1.1算法与程序算法与程序方法二：连续整数检测算法方法二：连续整数检测算法（1）将）将 min(m,n)的值赋给的值赋给t。（2）m除以除以t，如果余数为，如果余数为0，进入第，进入第3步，步，否则，进入第否则，进入第4步。步。（3）n除以除以t，如果余数为，如果余数为0，返
7、回，返回t值，结值，结束，否则，进入第束，否则，进入第4步。步。（4）t=t-1，返回第，返回第2步。步。2023/4/911本讲稿第十一页，共三十七页1.1算法与程序算法与程序方法三：中学里计算方法三：中学里计算Gcd(m,n)的过程（用的过程（用数学定义的方法）数学定义的方法）（1）找到）找到m的所有质因数。的所有质因数。（2）找到）找到n的所有质因数。的所有质因数。（3）找到（）找到（1），（），（2）中的公因数。）中的公因数。（4）求公因数的积，该乘积为）求公因数的积，该乘积为m、n的最的最大公约数。大公约数。2023/4/912本讲稿第十二页，共三十七页1.1算法与程序算法与程序理解
8、问题理解问题 在设计一个算法前，我们需要做的第一件事就在设计一个算法前，我们需要做的第一件事就是完全理解所给出的问题，仔细阅读问题的描述，是完全理解所给出的问题，仔细阅读问题的描述，如有任何疑惑就把疑问提出来，手工处理一些小例如有任何疑惑就把疑问提出来，手工处理一些小例子，考虑一下特殊情况，有必要的话再继续提出疑子，考虑一下特殊情况，有必要的话再继续提出疑问。问。严格确定算法需要处理的实例范围是非常重要严格确定算法需要处理的实例范围是非常重要的。如果不这样做，算法可能会对大多数的输入正的。如果不这样做，算法可能会对大多数的输入正确处理，但遇到某些确处理，但遇到某些“边界值边界值”的时候就出错。
9、的时候就出错。记住，一个正确的算法不仅应该能处理大多数的情况，记住，一个正确的算法不仅应该能处理大多数的情况，而且应该能正确处理而且应该能正确处理“所有所有”合法的输入。合法的输入。2023/4/913本讲稿第十三页，共三十七页1.1算法与程序算法与程序了解计算机设备的性能了解计算机设备的性能 今天使用的大多数算法仍然要运行于冯今天使用的大多数算法仍然要运行于冯诺依曼计诺依曼计算机上。这个体系结构的重点在于随机存取机。它最算机上。这个体系结构的重点在于随机存取机。它最主要的设想是：指令逐条运行，每次执行一步操作。主要的设想是：指令逐条运行，每次执行一步操作。相应地，设计运行于这种机器上的算法，
10、称为顺序算相应地，设计运行于这种机器上的算法，称为顺序算法。法。一些更新式的计算机可以在同一时间执行多条一些更新式的计算机可以在同一时间执行多条操作，即并行计算，能够利用这种计算性能优势的操作，即并行计算，能够利用这种计算性能优势的算法称为并行算法。算法称为并行算法。尽管如此，在可预见的未来，学习尽管如此，在可预见的未来，学习RAM模型下算模型下算法设计和分析的经典技术仍然是算法学的基石。法设计和分析的经典技术仍然是算法学的基石。2023/4/914本讲稿第十四页，共三十七页1.1 算法与程序算法与程序在精确解法和近似解法间做选择在精确解法和近似解法间做选择 精确的解法称为精确算法。精确的解法
11、称为精确算法。近似的解法称为近似算法。（无法求得精确解近似的解法称为近似算法。（无法求得精确解求平方根问题求平方根问题或由于某些问题固有的复杂性，用已或由于某些问题固有的复杂性，用已知的精确算法来解决该问题会慢得无法接受知的精确算法来解决该问题会慢得无法接受旅行售旅行售货员问题货员问题）2023/4/915本讲稿第十五页，共三十七页1.1算法与程序算法与程序确定适当的数据结构确定适当的数据结构 算法和数据结构是计算机编程的重要基础。算法和数据结构是计算机编程的重要基础。程序程序=算法算法+数据结构数据结构2023/4/916本讲稿第十六页，共三十七页1.1 算法与程序算法与程序算法设计技术算法
12、设计技术 什么是算法设计技术？是用算法解什么是算法设计技术？是用算法解题的一般性方法。用于解决不同计算领题的一般性方法。用于解决不同计算领域的多种问题。域的多种问题。在给新问题设计算法时，能够给予在给新问题设计算法时，能够给予指导，另外，算法设计技术可以按照内指导，另外，算法设计技术可以按照内在设计理念对算法进行分类，设计技术在设计理念对算法进行分类，设计技术使我们能够以一种自然的方式对算法进使我们能够以一种自然的方式对算法进行分类和研究。行分类和研究。2023/4/917本讲稿第十七页，共三十七页1.1算法与程序算法与程序详细表述算法的方法详细表述算法的方法 用文字和伪代码描述。用文字和伪代
13、码描述。文字表述有逻辑缺陷。文字表述有逻辑缺陷。伪代码是自然语言和类编程语言组成的混合伪代码是自然语言和类编程语言组成的混合结构。结构。2023/4/918本讲稿第十八页，共三十七页1.1算法与程序算法与程序证明算法的正确性证明算法的正确性 必须证明算法的正确性，就是说，我们必须证明必须证明算法的正确性，就是说，我们必须证明对于每一个合法的输入，该算法都会在有限的时间对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。内输出一个满足要求的结果。证明正确性的一般方法是使用数学归纳法。证明正确性的一般方法是使用数学归纳法。为了表明算法是不正确的，只需提供一个算法为了表明算法是不正
14、确的，只需提供一个算法不能正确处理的输入实例。不能正确处理的输入实例。对于近似算法来说，常常试图证明该算法所产生对于近似算法来说，常常试图证明该算法所产生的误差不超出我们预定的范围。的误差不超出我们预定的范围。2023/4/919本讲稿第十九页，共三十七页1.1 算法与程序算法与程序分析算法分析算法 算法有两种效率：时间效率和空间效率。算法有两种效率：时间效率和空间效率。时间效率显示算法运行得有多快。时间效率显示算法运行得有多快。空间效率显示算法需要多少额外的存储空间。空间效率显示算法需要多少额外的存储空间。算法的另外两个特性：简单性和一般性。算法的另外两个特性：简单性和一般性。一般性有两层意
15、思：算法解决问题的一般性和算法一般性有两层意思：算法解决问题的一般性和算法所接受输入的一般性。所接受输入的一般性。2023/4/920本讲稿第二十页，共三十七页1.1算法与程序算法与程序为算法写代码为算法写代码 对算法进行编程既是挑战也是机遇。挑战对算法进行编程既是挑战也是机遇。挑战在于，在把算法转变为程序的过程中，可能会发在于，在把算法转变为程序的过程中，可能会发生错误或者效率非常低。（大多数计算机科学家生错误或者效率非常低。（大多数计算机科学家坚信，除非计算机程序的正确性在数学上得到了坚信，除非计算机程序的正确性在数学上得到了完全严格的证明，否则，我们不能认为程序是正完全严格的证明，否则，
16、我们不能认为程序是正确的。）确的。）运行中的程序为我们提供了一个分析它内运行中的程序为我们提供了一个分析它内在算法的额外机会。这也是我们要把算法变成程在算法的额外机会。这也是我们要把算法变成程序的另一个原因。序的另一个原因。2023/4/921本讲稿第二十一页，共三十七页1.1 算法与程序算法与程序 1理解问题理解问题、2了解计算机设备的性能了解计算机设备的性能 3在精确解和近似解间作出选择在精确解和近似解间作出选择 4描述算法的方法、描述算法的方法、5证明算法的正确性证明算法的正确性 6算法设计技术、算法设计技术、7确定适当的数据结构确定适当的数据结构 8分析算法、分析算法、9为算法写代码为
17、算法写代码 最后，让我们再强调一下算法设计与实现的主要含最后，让我们再强调一下算法设计与实现的主要含义：作为一个规律，一个好的算法是反复努力和重新义：作为一个规律，一个好的算法是反复努力和重新修正的结果。修正的结果。2023/4/922本讲稿第二十二页，共三十七页1.从机器语言到高级语言的抽象1.2表达算法的抽象机制表达算法的抽象机制高级程序设计语言的主要好处是：高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量
18、。间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要要几周时间的培训就可以胜任程序员的工作；几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写
19、出来的程序可植性好、重用率高；程序可植性好、重用率高；2023/4/923本讲稿第二十三页，共三十七页2.抽象数据类型1.2表达算法的抽象机制表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。并作为算法构件的一组运算。抽象数据类型抽象数据类型带给算法设计的带给算法设计的好处好处有有：（1 1）算法顶层设计与底层实现分离；）算法顶层设计与底层实现分离；（2 2）算法设计与数据结构设计隔开，允许数据结构自由选择；）算法设计与数据结构设计隔开，允许数据结构自由选择；（3 3）数据模型和该模型上的运算统一在
20、）数据模型和该模型上的运算统一在ADTADT中，便于空间和时间耗费的折衷；中，便于空间和时间耗费的折衷；（4 4）用抽象数据类型表述的算法具有很好的可维护性；）用抽象数据类型表述的算法具有很好的可维护性；（5 5）算法自然呈现模块化；）算法自然呈现模块化；（6 6）为自顶向下逐步求精和模块化提供有效途径和工具；）为自顶向下逐步求精和模块化提供有效途径和工具；（7 7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。2023/4/924本讲稿第二十四页，共三十七页1.3 算法复杂性分析算法复杂性分析 算法复杂性是算法运行所
21、需要的计算机资源的量，算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为需要时间资源的量称为时间复杂性时间复杂性，需要的空间资源的量称为，需要的空间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的问题的规模、这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用算法的输入和算法本身的函数。如果分别用N N、I I和和A A表示算表示算法要解问题的规模、算法的输入和算法本身，而且用法要解问题的规模、算法的输入和算法本身，而且用C C表示复表示复杂性，那么，应该有杂性，那么，应该有C=F(N,I,A)C=F(N,I,A)。一般把时间复杂性和空间复
22、杂一般把时间复杂性和空间复杂性分开，并分别用性分开，并分别用T T和和S S来表示，则有：来表示，则有：T=T(N,I)T=T(N,I)和和S=S(N,I)S=S(N,I)。（通常，让通常，让A A隐含在复杂性函数名当中）隐含在复杂性函数名当中）2023/4/925本讲稿第二十五页，共三十七页1.3 算法复杂性分析算法复杂性分析分析框架：分析框架：有两种算法效率：时间效率和空间效率。有两种算法效率：时间效率和空间效率。时间效率：指出正在讨论的算法运行得有多快。时间效率：指出正在讨论的算法运行得有多快。空间效率：算法需要的额外空间。空间效率：算法需要的额外空间。2023/4/926本讲稿第二十六
23、页，共三十七页1.3算法复杂性分析算法复杂性分析输入规模的度量输入规模的度量 几乎所有的算法，对于规模更大的输入都需要运几乎所有的算法，对于规模更大的输入都需要运行更长的时间。使用一个以算法输入规模行更长的时间。使用一个以算法输入规模N为参数的为参数的函数，来研究算法效率是非常合乎逻辑的。函数，来研究算法效率是非常合乎逻辑的。选择输入规模的合适度量，要受到所讨论算法的选择输入规模的合适度量，要受到所讨论算法的操作细节的影响。操作细节的影响。例如：对于一个拼写检查算法，例如：对于一个拼写检查算法，如何度量其输入规模呢？如果算法对于输入的每一如何度量其输入规模呢？如果算法对于输入的每一个独立字符都
24、要做检查，应该使用字符的数量来度个独立字符都要做检查，应该使用字符的数量来度量输入规模。如果它的操作是以词为单位的，应该量输入规模。如果它的操作是以词为单位的，应该统计输入中词的数量。统计输入中词的数量。2023/4/927本讲稿第二十七页，共三十七页1.3算法复杂性分析算法复杂性分析运行时间的度量单位运行时间的度量单位 统计算法每一步操作的执行次数。统计算法每一步操作的执行次数。基本操作：对总运行时间贡献最大的操作。基本操作：对总运行时间贡献最大的操作。算法中的基本操作：通常是算法最内层循环中最费时间的算法中的基本操作：通常是算法最内层循环中最费时间的操作。操作。例如：排序：对关键词的比较。
25、例如：排序：对关键词的比较。矩阵相乘：乘法和加法矩阵相乘：乘法和加法 建立一个算法时间效率的分析框架：对于输入规模为建立一个算法时间效率的分析框架：对于输入规模为N的算法的算法统计它的基本操作执行次数，来对其效率进行度量。统计它的基本操作执行次数，来对其效率进行度量。约定：约定：Cop为特定计算机上一个算法基本操作的执行时间。为特定计算机上一个算法基本操作的执行时间。C(N)是该算法需要执行基本操作的次数。是该算法需要执行基本操作的次数。对运行在那台计算机上的某个算法程序的运行时间，用以下公对运行在那台计算机上的某个算法程序的运行时间，用以下公式估计：式估计：T(N)=CopC(N)2023/
26、4/928本讲稿第二十八页，共三十七页1.3算法复杂性分析算法复杂性分析增长次数：一年的秒数增长次数：一年的秒数=3.1536*107nLog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*1041061092023/4/929本讲稿第二十九页，共三十七页1.3算法复杂性分析算法复杂性分析渐进符号和基本效率类型渐进符号和基本效率类型 效率分析框架主要关心一个算法的效率分析框架主要关心一个算法的基本操作次数的增长次数，并把它作为基本操作次数的增长次数，
27、并把它作为算法效率的主要指标。为了对这些增长算法效率的主要指标。为了对这些增长次数进行比较和归类，计算机科学家使次数进行比较和归类，计算机科学家使用用3种符号：种符号：O，。T(n)和和G(n)是定是定义在自然数集合上的任意非负函数。义在自然数集合上的任意非负函数。T(n)是一个算法的运行时间（常常用基本操是一个算法的运行时间（常常用基本操作次数作次数C(n)来表示）。来表示）。G(n)是一个用来是一个用来和该操作次数做比较的函数。和该操作次数做比较的函数。2023/4/930本讲稿第三十页，共三十七页1.3算法复杂性分析算法复杂性分析 当问题规模增大时，复杂度的极限行为称为算法的渐进时间复杂
28、度。算法算法时间复杂度时间复杂度最大问题规模最大问题规模1秒秒1分分1小时小时A1n10006*1043.6*106A2nlogn14048932.0*105A3N2312441897A4N31039153A52n91521算法算法时间复杂度时间复杂度加速前最大问题规模加速前最大问题规模加速后最大问题规模加速后最大问题规模A1nS110*S1A2nlognS2约为约为10*S2A3N2S33.16*S3A4N3S42.15*S4A52nS5S5+3.3假设下一代计算机的速度是目前的10倍，下表是计算机加速后在相同的时间内可以解决的问题规模增量。2023/4/931本讲稿第三十一页，共三十七页1
29、.3算法复杂性分析算法复杂性分析基本的效率类型基本的效率类型 如果一个算法的运行时间是如果一个算法的运行时间是n3，另一个算法的运行，另一个算法的运行时间是时间是106n2；除非；除非n比比106还大，否则，立方算法的表现还大，否则，立方算法的表现会超过平方算法。我们的确知道这样一些算法。例如：有会超过平方算法。我们的确知道这样一些算法。例如：有一些矩阵乘法算法的渐进效率要好于基于定义的立方算法。一些矩阵乘法算法的渐进效率要好于基于定义的立方算法。然而，因为它们的乘法常量值过大，这些非常精美的算法然而，因为它们的乘法常量值过大，这些非常精美的算法在绝大多数情况下只具有理论价值。在绝大多数情况下
30、只具有理论价值。幸运的是，乘法常量之间通常不会相差那么悬幸运的是，乘法常量之间通常不会相差那么悬殊。作为一个规律，即使是中等规模的输入，一个殊。作为一个规律，即使是中等规模的输入，一个属于较优渐进效率类型的算法也会比一个来自于较属于较优渐进效率类型的算法也会比一个来自于较差类型的算法表现得更好。如果拿效率好于指数级差类型的算法表现得更好。如果拿效率好于指数级的算法与指数级（或者更糟糕）的算法相比，这个的算法与指数级（或者更糟糕）的算法相比，这个规律会更加明显。规律会更加明显。2023/4/932本讲稿第三十二页，共三十七页1.3 算法复杂性分析算法复杂性分析设设T(n)是关于算法是关于算法A的
31、复杂性函数。一般说来，当的复杂性函数。一般说来，当N单单调增加且趋于调增加且趋于时，时，T(n)也将单调增加趋于也将单调增加趋于。对。对于于T(n)，如果存在，如果存在t(n)，使得当，使得当n 时有时有(T(N)-t(n)/T(N)00，那么，我们就说，那么，我们就说t(n)是是T(n)当当n 时的渐进性态。时的渐进性态。因为在数学上，因为在数学上，t(n)是是T(n)当当n时的渐进表达式，时的渐进表达式，直观上，直观上，t(n)是是T(n)中略去低阶项所留下的主项，所中略去低阶项所留下的主项，所以它无疑比以它无疑比T(n)来得简单。来得简单。例如：例如：T(n)=3n2+4nlogn+7时
32、，时，t(n)的一个答案是的一个答案是3n2。2023/4/933本讲稿第三十三页，共三十七页1.3算法复杂性分析算法复杂性分析算法的最差、最优和平均效率算法的最差、最优和平均效率一个算法的最差效率：是指当输入规模为一个算法的最差效率：是指当输入规模为N时，算法在最坏情况下的效率。时，算法在最坏情况下的效率。一个算法的最优效率：是指当输入规模为一个算法的最优效率：是指当输入规模为N时，算法在最优情况下的效率。时，算法在最优情况下的效率。一个算法的平均效率：在一个算法的平均效率：在“典型典型”或者或者“随机随机”输入的情况下，算法会具有什么输入的情况下，算法会具有什么样的行为样的行为 2023/
33、4/934本讲稿第三十四页，共三十七页1.3算法复杂性分析算法复杂性分析最坏情况下的时间复杂性：最坏情况下的时间复杂性：最好情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：平均情况下的时间复杂性：其中其中D DN N是规模为是规模为N N的合法输入的集合；的合法输入的集合；I I*是是D DN N中使中使T(N,IT(N,I*)达到达到T Tmaxmax(N)(N)的合法输入；的合法输入；是中使是中使T(N,)T(N,)达到达到T Tminmin(N)(N)的合法的合法输入；而输入；而P(I)P(I)是在算法的应用中出现输入是在算法的应用中出现输入I I的概率。的概率。20
34、23/4/935本讲稿第三十五页，共三十七页1.3算法复杂性分析算法复杂性分析算法复杂性在渐近意义下的阶：算法复杂性在渐近意义下的阶：渐近意义下的记号：渐近意义下的记号：O O、o o 设设f(N)f(N)和和g(N)g(N)是定义在正数集上的正函数。是定义在正数集上的正函数。O O的定义的定义：如果存在正的常数：如果存在正的常数C C和自然数和自然数N N0 0，使得当使得当N N N N0 0时有时有f(N)f(N)C Cg(N)g(N)，则称函数，则称函数f(N)f(N)当当N N充分大时上有界，且充分大时上有界，且g(N)g(N)是它的一个上界，记为是它的一个上界，记为f(N)=O(g
35、(N)f(N)=O(g(N)。即。即f(N)f(N)的阶不高于的阶不高于g(N)g(N)的阶。的阶。根据根据O O的定义，的定义，容易证明它有如下运算规则：容易证明它有如下运算规则：(1)(1)O(f)+O(g)=O(max(f,g)O(f)+O(g)=O(max(f,g)；(2)O(f)+O(g)=O(f+g)(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)(3)O(f)O(g)=O(fg)；(4)(4)如果如果g(N)=O(f(N)g(N)=O(f(N)，则则O(f)+O(g)=O(f)O(f)+O(g)=O(f)；(5)(5)O(Cf(N)=O(f(N)O(Cf
36、(N)=O(f(N)，其中其中C C是一个正的常数；是一个正的常数；(6)(6)f=O(f)f=O(f)。f(N)的阶小于等的阶小于等于于g(N)的阶的阶2023/4/936本讲稿第三十六页，共三十七页1.3算法复杂性分析算法复杂性分析 的定义的定义：如果存在正的常数：如果存在正的常数C C和自然数和自然数N N0 0，使得当使得当N N N N0 0时时有有f(N)f(N)C Cg(N)g(N)，则称函数，则称函数f(N)f(N)当当N N充分大时下有界，且充分大时下有界，且g(N)g(N)是它是它的一个下界，记为的一个下界，记为f(N)=f(N)=(g(N)(g(N)。即。即f(N)f(N
37、)的阶不低于的阶不低于g(N)g(N)的阶。的阶。的定义的定义：定义：定义f(N)=f(N)=(g(N)(g(N)当且仅当当且仅当f(N)=O(g(N)f(N)=O(g(N)且且f(N)=f(N)=(g(N)(g(N)。此时称此时称f(N)f(N)与与g(N)g(N)同阶。同阶。o o的定义的定义：对于任意给定的：对于任意给定的0 0，都存在正整数都存在正整数N N0 0，使得使得当当N N N0N0时有时有f(N)f(N)/C/Cg(N)g(N),则称函数则称函数f(N)f(N)当当N N充分大时的阶比充分大时的阶比g(N)g(N)低，记为低，记为f(N)=o(g(N)f(N)=o(g(N)。例如，例如，4 4NlogN+7=o(3NNlogN+7=o(3N2 2+4NlogN+7)+4NlogN+7)。(f(N)的阶小于的阶小于g(N)的阶的阶)2023/4/937本讲稿第三十七页，共三十七页