算法复杂性精品文稿.ppt

算法复杂性算法复杂性1 1第1页，本讲稿共48页关于本课程关于本课程课程目的：计算机算法设计与分析导引不是一门试验或程序设计课程也不是一门数学课程参考教材：计算机算法设计与分析-王晓东前导课：数据结构+程序设计授课形式：作业+实验+笔试2 2第2页，本讲稿共48页第第1 1章章 算法复杂性算法复杂性本章主要知识点：1.1 引言1.2 算法复杂性的测度3 3第3页，本讲稿共48页1.1 引言引言算法（algorithms）的研究是计算机科学的核心课题之一。早在计算机问世以前，就有人开创了算法的研究，并创建了许多有效的算法。欧几里德算法（求两数的最大公因子）孙子算法（求若干个数的最小公倍数）快速富里叶变换（FFT）算法（60年代后半期）并行算法（70年代）据不完全统计，50年代以前约占文献总量10%；产生60年代的约占文献总量的30%；产生于70年代（76年前）约占文献总量60%。4 4第4页，本讲稿共48页目前，算法的研究仍方兴未艾，它所涉及的范围十分广泛。不论是从事计算机硬件设计（如计算机部件设计、系统设计和网络设计等），还是从事计算机软件设计（如设计系统软件和各种应用软件），都需要认真研究算法。计算机程序的核心则是计算机算法，如果不发明更有效的算法，就不可能开发出更新更先进的软件。5 5第5页，本讲稿共48页一年一度的计算机科学领域最高荣誉计算图灵奖（Turing Awards），被誉为计算机科学领域的“诺贝尔奖”，从1966年至1999年，约有12人是由于在算法与数据结构、计算复杂性理论、程序设计等获图灵奖，比如1984年图灵设计得主瑞士的NWirth教授提出“算法+数据结构=程序”著名公式。1980年授予在程序设计和算法方面，因发明Quick Sort算法的英国Hoare教授。6 6第6页，本讲稿共48页阿兰麦席森图灵（Alan Mathison Turing，1912.6.231954.6.7），是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。7 7第7页，本讲稿共48页提出“图灵机”概念提出“图灵测试”概念开创非线性力学破解德国密码系统Enigma 8 8第8页，本讲稿共48页图灵试验由计算机、被测试的人和主持试验人组成。计算机和被测试的人分别在两个不同的房间里。测试过程由主持人提问，由计算机和被测试的人分别做出回答。观测者能通过电传打字机与机器和人联系（避免要求机器模拟人外貌和声音）。被测人在回答问题时尽可能表明他是一个“真正的”人，而计算机也将尽可能逼真的模仿人的思维方式和思维过程。如果试验主持人听取他们各自的答案后，分辨不清哪个是人回答的，哪个是机器回答的，则可以认为该计算机具有了智能。这个试验可能会得到大部分人的认可，但是却不能使所有的哲学家感到满意。9 9第9页，本讲稿共48页图灵图灵享年42岁，科学家为了纪念他，1966年美国计算机协会设立了“图灵奖”成为计算机科学家的最高奖项。后来一位加利福尼亚的小伙子为了纪念图灵，开办了一家公司，而公司的Logo就是图灵死时手里拿着的被咬过一口的苹果，这家公司就是现在很出名的苹果公司，而那个小伙子则是苹果的第一任CEO乔布斯.1010第10页，本讲稿共48页2009 Charles Thacker 获奖原因 对第一台现代个人计算机Xerox PARC Alto的先驱性设计与实现，还有在局域网（包括以太网）、多处理器工作站、窥探高速缓存一致性协议和平板PC等方面的重大发明和贡献.2008 Barbara Liskov 获奖原因 在计算机程序语言设计方面的开创性工作。她的贡献是让计算机软 件更加可靠、安全和更具一致性。美国第一个获得计算机科学博士学位的女性（1968年，斯坦福大学），其创新性研究给计算机编程领域带来了巨大变革.她是第二位授予图灵奖的女性.2007 Edmund M.Clarke、Allen Emerson和Joseph Sifakis 获奖原因 在将模型检查发展为被硬件和软件业中所广泛采纳的高效验证技术上的贡献。而DDJ则将三人的贡献称为“在发现计算机硬件和软件中设计错误的自动化方法方面的工作”。1111第11页，本讲稿共48页2000 Andrew Chi-Chih Yao(姚期智)获奖原因：由于在计算理论方面的贡献而获奖，包括伪随机数的生成算法、加密算法和通讯复杂性。1984 Niklaus Wirth 获奖原因：由于开发了EULER、ALGOL-W、MODULA和PASCAL一系列崭新的计算语言。算法十数据结构=程序（Algorithms Data Structures Programs)1212第12页，本讲稿共48页1980 C.Antony R.Hoare 获奖原因：由于在编程语言的定义和设计方面的基础性贡献。Quicksort算法之父查尔斯霍尔 1974 Donald E.Knuth 获奖原因：由于在算法分析和程序语言设计方面的重要贡献，计算机程序设计艺术的作者。算法大师Donald E.Knuth的计算机程序设计艺术是一部鸿篇巨著。原计划要出七册，但目前只完成了三册。他还有个中文名字：“高德纳”。数据结构和编译原理的KMP算法和LR(K)算法 1313第13页，本讲稿共48页2006 Fran Allen 获奖原因：对于优化编译器技术的理论和实践做出的先驱性贡献，这些技术为现代优化编译器和自动并行执行打下了基础。第一位女性图灵奖得主。1414第14页，本讲稿共48页约翰约翰冯冯诺依曼诺依曼（John Von Neumann，19031957），美藉匈牙利人，），美藉匈牙利人，1903年年12月月28日，在布达佩斯诞生了一位神童，日，在布达佩斯诞生了一位神童，这不仅给这个家庭带来了巨大的喜悦，这不仅给这个家庭带来了巨大的喜悦，也值得整个计算机界去纪念。正是他，也值得整个计算机界去纪念。正是他，开创了现代计算机理论，其体系结构沿开创了现代计算机理论，其体系结构沿用至今，而且他早在用至今，而且他早在40年代就已预见到年代就已预见到计算机建模和仿真技术对当代计算机将计算机建模和仿真技术对当代计算机将产生的意义深远的影响。他，就是约翰产生的意义深远的影响。他，就是约翰冯冯诺依曼（诺依曼（John Von Neumann）。）。1515第15页，本讲稿共48页1933年，冯诺依曼解决了希尔伯特第5问题，即证明了局部欧几里得紧群是李群1934年他又把紧群理论与波尔的殆周期函数理论统一起来他还对一般拓扑群的结构有深刻的认识，弄清了它的代数结构和拓扑结构与实数是一致的 他对算子代数进行了开创性工作，并奠定了它的理论基础，从而建立了算子代数这门新的数学分支这个分支在当代的有关数学文献中均称为冯诺依曼代数这是有限维空间中矩阵代数的自然推广1616第16页，本讲稿共48页冯诺依曼还创立了博弈论这一现代数学的又一重要分支 1944年发表了奠基性的重要论文博弈论与经济行为论文中包含博弈论的纯粹数学形式的阐述以及对于实际博弈应用的详细说明文中还包含了诸如统计理论等教学思想冯诺依曼在格论、连续几何、理论物理、动力学、连续介质力学、气象计算、原子能和经济学等领域都作过重要的工作 冯诺依曼对人类的最大贡献是对计算机科学、计算机技术和数值分析的开拓性工作1717第17页，本讲稿共48页1.1 引言引言算法：是满足下述性质的指令序列。有穷性:一个算法在执行有穷个计算步骤后必须终止。确定性:一个算法中给出的每一个计算步，必须是精确地定义的、无二义性的。能行性:算法中要执行每一计算步都是可以在有限时间内做完的。能行性、有穷性和确定性是相容的。输入:一个算法一般都要求0个或多个输入信息，这些输入量是算法所需的初始数据，它们取自某一特定的集合。输出:一个算法一般有一个或多个输出信息。被解释为“对输入的计算结果”。程序：1818第18页，本讲稿共48页凡是一个算法，都必须满足以上五个特征，只满足后四条特征的一组规则，不能称作算法，叫做计算过程。操作系统就是计算过程的一个重要例子。设计操作系统的目的是为了控制作业的运行，当没有作业可用时，这一计算过程并不终止，而是处于等待状态，一直等到一个新的作业进入。1919第19页，本讲稿共48页例如，求给定两个整数m和n的最大公因子，这个问题通常用“辗转相除法”求解。西方称为欧几里得（Euclid）算法，我国数学家秦九韶在数书九章中记载了这个方法。Euclid算法如下：（1）输入m，n （mn）；（2）以n除m，r=MOD（m，n），r为余数；（3）若r=o，输出n的当前值，算法结束；否则执行第（4）步；（4）mn，nr，转入（2）。2020第20页，本讲稿共48页2121第21页，本讲稿共48页例m=36，n=28r=8r0 m=28 n=8r=4r0 m=8 n=4r=0输出最大公因子为42222第22页，本讲稿共48页算法与过程的区别：算法要在有限的时间内通过有穷步计算后终止；过程则可以是有穷的，也可以是无穷的，无穷的过程永远不会终止。算法与程序的区别：程序往往是指用某种机器语言书写的一个计算过程；但一个特定的算法不一定表现为一个计算机程序。一个算法可以采用多种方式描述，如图解描述、语言描述等，如果语言描述一算法，既可用人类的自然语言描述，也可以用各种计算机语言描述，这时表现为程序。也就说程序是算法描述的其中一种方法。我们最感兴趣的还是用计算机语言来描述和在计算机上执行各种算法。一个计算机程序一般只能在某些机器上执行；而一个算法，既可以编成程序在各种计算机上执行，也可以用纸、笔手工执行，甚至可以用算盘，算筹或其它工具执行。2323第23页，本讲稿共48页二、算法设计和算法分析的步骤二、算法设计和算法分析的步骤1、问题的陈述 准确地陈述问题是解决问题的第一步。为了设计求解某一问题的算法，首先必须了解问题的实质。即已知条件是什么？要求回答是什么？一个问题的正确描述应当使用科学的语言把所有已知条件和需要的答案陈述清楚。2424第24页，本讲稿共48页2、模型的选择或拟制 当问题陈述清楚后，选择或拟制描述问题的数学模型是非常重要的工作。模型适当与否影响算法设计的速度和算法的效率。模型选择无公式可循，取决于设计者的知识结构、工作经验等。设计者应当十分重视模型的选择，宁可多下功夫来选择或拟制一个适合当前问题的数学模型，才能为后续工作的顺利开展铺平道路。2525第25页，本讲稿共48页3、算法设计和正确性证明 数学模型一经选定，就可以进行算法设计。算法的选择与模型的选择是密切相关的。对同一模型仍有不同的算法，这些算法的有效性可能相差很大。算法的设计是指设计求解某个具体问题类的一般步骤，并且这些步骤通过计算机的各种操作来实现。算法设计是一种复杂的、艰苦的创造性劳动，要求设计者充分发挥主观能动性，充分运用已知知识和抽象思维，形成算法思想，写出算法的具体步骤。2626第26页，本讲稿共48页算法的正确性证明与程序的正确性证明一样，是算法理论研究中引人注目的一部分。一个算法的正确性证明，就是要证明对于一切合法输入算法都能在有限次计算后产生正确的输出。这实际上是一种穷举证明法，当算法的输入庞大时，实际上是很难做到的。当输入是一个无穷集时，穷举证明是不可能的。另一种证明方法将一个算法的输入和输出都表示成“输入断言”和“输出断言”，一个算法的各计算步可以表示成一组“谓词演算”规则。论证通过这一组谓词演算，能由输入断言导出输出断言。这种形式演绎过程是很冗长繁复，往往比一个算法（或程序）本身还要长。我们对算法的正确性不采用严格的形式论证，而只给出非形式的直观解释。2727第27页，本讲稿共48页4、算法的程序实现 将一个算法正确地编写成一个机器程序，叫做算法的程序实现。将给定的算法正确地转换成一个程序，并不是一个简单的工作，要求设计者掌握多种程序设计方法和技巧。2828第28页，本讲稿共48页5、算法分析 算法分析与算法设计有必然联系，算法设计的中心任务对于现实生活中提出的某些问题是如何设计出一个求解的算法。算法分析研究各种算法的特征和优劣。主要关心如何判定算法的优劣，标准是什么？2929第29页，本讲稿共48页6、程序的测试、文档编制 编制完实现算法的程序后，对程序进行测试，程序测试可以被认为是对程序应完成的任务的实验验证，同时确定程序的使用范围。编制文档应该和算法设计及实现阶段交织在一起。编制文档的主要目的是让人了解别人编写的算法和程序。3030第30页，本讲稿共48页问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法3131第31页，本讲稿共48页第二节第二节 计算复杂性的测度计算复杂性的测度一、几个概念及例子体积（size），或称为问题的“大小”，可以用一个整数来表示，它是对问题的输入数据（或初始数据）的多少的一种量度。例如矩阵乘法问题的大小可以用矩阵的阶数来定义，也可以用矩阵元素个数来度量。图论问题的体积可以定义为图的边数等。时间复杂性（time complexity），如果一个问题的体积是n，解这一问题的某一算法所需的时间为T（n），它是n的某一函数，T（n）称为这一算法的时间复杂性。渐近时间复杂性，当输入量n逐渐增大时，时间复杂性的极限情形称作渐近时间复杂性。类似地可以定义一个算法的“空间复杂性”和“渐近空间复杂性”。3232第32页，本讲稿共48页例1：求行列式值的算法，由行列式定义，一个n阶行列式的值由n！项组成，其中每一个项又由行列式的n个元素组成。如果不计加法及其它运算次数而只考虑乘法次数，那么求行列式值就有n！（n-1）次乘法，若每个乘法运算的时间为s，则求n阶行列式值所用的时间为：T（n）=n！（n-1）10-6sn=10 T（10）=32.65sn=50 T(50)=4.71052(年)由此可见,从定义出发求n阶行列式的算法是不可取的。3333第33页，本讲稿共48页3434第34页，本讲稿共48页3535第35页，本讲稿共48页3636第36页，本讲稿共48页例：计算x22需要多少次乘法？a=x*x b=a*a c=b*b d=c*c x22=d*a*b 6次乘法3737第37页，本讲稿共48页二、渐近时间复杂性3838第38页，本讲稿共48页3939第39页，本讲稿共48页4040第40页，本讲稿共48页4141第41页，本讲稿共48页四、问题分类根据算法论和计算复杂性的观点，将现有的问题大致可分为三大类：无法写出算法问题，如哥德巴赫猜想，费马猜想等；有以多项式为界的算法存在的问题P问题，如m-n的最大公因数，矩阵相乘等；介于前两类问题之间-NP-问题。这类问题可以写出算法，但算法的时间复杂性往往是输入量n的指数函数，其中有一类NP-完全问题，比如旅行商人问题（Traveling salesman problem）、整数分划问题、顶点覆盖问题等。4242第42页，本讲稿共48页哥德巴赫哥德巴赫猜想（猜想（Goldbach Conjecture）大致）大致可以分为两个猜想可以分为两个猜想(前者称前者称“强强”或或“二重哥二重哥德巴赫猜想德巴赫猜想,后者称后者称”弱弱“或或”三重哥德巴赫三重哥德巴赫猜想猜想)：1.每个不小于每个不小于6的偶数都可以表示为的偶数都可以表示为两个两个奇素数奇素数之和；之和；2.每个不小于每个不小于9的奇数都可的奇数都可以表示为三个奇素数之和。以表示为三个奇素数之和。6=3+3,8=3+5,10=5+5=3+7,12=5+7,14=7+7=3+11,16=5+11,18=5+13,4343第43页，本讲稿共48页目前最佳的结果是中国数学家陈景润于1966年证明的，称为陈氏定理：“任何充分大的偶数都是一个质数与一个自然数之和，而后者最多仅仅是两个质数的乘积。”通常都简称这个结果为（1+2）。4444第44页，本讲稿共48页NP一完备问题猜想：（1）任何NP一完备问题都不能用任何已知的多项式算法求解；（2）若任何一个NP一完备问题有多项式算法，则一切NP一完备问题都有多项式算法。由此不少人猜测任何NP一完备问题都没有多项式算法，但至今无人证明，人们普遍认为，不发展全新的数学技术就证明不了这个猜想。在所有能精确求NP一完备问题的算法，在最坏情况下都需要指数级的时间。4545第45页，本讲稿共48页五、平均复杂性和最坏情形复杂性（Average behavior and worst case complexity）算法的时间复杂性分为最坏情形复杂性和平均情形复杂性。如果给定输入大小，把复杂性取作这种大小的所有输入上的最大复杂性，则称之为最坏情形复杂性。如果把复杂性取作这种大小的输入的“平均”复杂性，称之为期望复杂性。4646第46页，本讲稿共48页4747第47页，本讲稿共48页4848第48页，本讲稿共48页