计算复杂性理论

1、编辑ppt计算复杂性理论计算复杂性理论编辑ppt计算复杂性理论简介计算复杂性理论简介组合优化问题的固有计算复杂性明显与求解算法的计算行为相关，计算复杂性理论试图根据问题的内在复杂性对问题进行分类。这里首先给出问题分类的基本概念，接着介绍算法效率分析框架及算法评估。 M.H.Alsuwaiyel著, 吴伟昶等译.算法设计技巧与分析，北京, 电子工业出版社, 2004.8.Anany Levitin著, 潘彦译.算法设计与分析基础，北京, 清华大学出版社, 2004.3.编辑ppt1 1 算法概述算法概述 算法算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要

2、求或期望的终止状态或输出数据。 算法常常含有重复的步骤和一些比较或逻辑判断。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 编辑ppt算法历史 演算法的大陸中文名稱出自周髀算經；而英文名稱Algorithm来自于9世纪波斯数学家花拉子米（比阿勒霍瓦里松，波斯語：? ，拉丁轉寫：al-Khwarizmi），因為比阿勒霍瓦里松在数学上提出了算法这个概念。“算法”原为algorism，意思是阿拉伯数字的运算法则，在18世纪演变为algorithm。欧几里得算法被人们认为是史上第一个算法。第一次编写程序是Ada Byron于1842年为巴贝奇

3、分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯巴贝奇（Charles Babbage）未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。因为well-defined procedure缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。编辑ppt算法特征算法特征 Donald Knuth在他的著作The Art of Co

4、mputer Programming裡對演算法下的定義： 输入：一个算法必须有零个或以上输入量。 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。 明確性：算法的描述必须无歧义，以保证算法的實際执行结果是精確地符合要求或期望，通常要求實際執行結果是确定的。算法的每一步骤必须有确切的定义； 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機器只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必须在有限個步骤内完成任務。 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。编辑ppt形

5、式化算法形式化算法 算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。 编辑ppt复杂度复杂度 时间复杂度时间复杂度 算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=O(f(n) 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Comp

6、lexity）。 空间复杂度空间复杂度 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。编辑ppt算法设计与分析的基本方法算法设计与分析的基本方法 递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。 递归递归指的是一个过程：函数不断引用自身，直到引用的对象已知 穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 贪婪法贪婪法是一种不追求

7、最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。编辑ppt 分治法分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 动态规划动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用

8、于计算机科学和工程领域。 迭代法迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。 编辑ppt2 2 P P、NPNP和和NPNP完全问题完全问题 判定问题判定问题指要求回答是与否的问题。如背包问题，对于集合T=1,t，正整数a1, a2,at, B，是否存在一个子集ST使得iS ai=B? 确定性算法确定性算法，设A是某问题的一个算法，如果在展示问题的一个实例时，在整个执行过程中每一步都只有一个选择，则称算法是确定性算法。 编辑ppt 不确定算法不确定算法是一个两个阶段的过程，它把一个判定问题的实例l作

9、为它的输入，并进行以下操作： 非确定阶段“猜测”，生成一个任意串S，把它当作实例l的一个候选解，但也可能是完全盲目的； 确定阶段“验证”，确定算法将l和S作为它的输入，如果S的确是l的一个解，则输出“是”，否则返回“否”或根本不停下来。 编辑pptP类问题是一类能够用（确定性的）算法在多项式的时间内求解的判定问题，也称多项式类型问题。Polynomial time NP类问题是一类可以用不确定多项式算法求解的判定问题，也称不确定多项式类型。 Non-deterministic Polynomial time P类问题属于NP类问题。 In this theory, the class P P

10、consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NPNP consists of all those decision problems whose positive solutions can be verified in polynomial time given

11、the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine 给定正确信息可在大多项式时间验证问题的肯定解。编辑ppt 如果对任何实例，可在多项式时间内构造一个实例，使得求解实例也将求解实例，则问题可简化到问题。到的可约性暗示可看作是的特殊情况，至少和一样困难。 对于任何一个NP类问题，都可简化到问题，则问题是NP难的。此时问题至少和NP类问题中任何问题一样困难。 NP完全问题属于NP类，且NP中任何问题都能在多项式时间内

12、简化为该问题，即是NP类中的NP难问题。NP完全问题是NP类中最困难的问题。根据定义，在NP完全问题中没有一个问题可以被很好求解，若其中有一个被很好求解了，则其它问题也可被很好求解。对这类问题，采用多项式求解很困难。求解该类问题可能只能接受一个差的优化算法，或者使用一个好（多项式）的近似算法。 编辑ppt编辑pptNP完全问题证明 证明一个判定问题D属于NP完全问题要经历两步， 首先证明D是NP问题，即可在多项式时间内检验一个任意生成串是否为D的一个解； 然后，须证明NP中每个问题能在多项式时间内化简为D。 这一步比较困难，可利用多项式化简的传递性，证明一个已知的NP完全问题可在多项式时间内转

13、化为D，见下图 编辑ppt NP完全问题的概念及证明方法演示 NP问题已知的NP完全问题NP完全性的候选者编辑ppt3 算法效率分析框架 算法是一系列解决问题的清晰指令，即能够对符合一定规范的输入，在有限时间内获得所要求的输出。算法评价包括正确性、效率、一般性和简单性。 正确性是对算法的基本要求。 一般性包括所解决问题的一般性和算法所接受输入的一般性。 简单性主要是考虑算法易于理解和实现。 算法效率包括时间和空间两种，时间效率显示算法运行有多快，空间效率是指算法需要多少额外的存储空间。 随着计算机技术的进步，一个算法所需的额外存储空间已不是关注的重点。在算法效率分析时，广泛采用的标准是算法的时

14、间复杂性。 编辑ppt时间效率分析步骤 在进行时间效率分析时，首先要选择合适的输入规模量度； 接着要确定运行时间的度量单位，常采用算法中基本操作的运行次数，基本操作指算法最内层循环中最费时的操作。 在此基础上，可写出以算法输入规模为参数的运行时间度量函数。 相对于运行次数（时间）来说，人们更多地关注运行次数（时间）的增长率或增长的阶，且通常只度量算法的渐进运行时间，即去除运行时间函数中的常量（包括常量项和常量系数）和低阶项。 在算法分析术语中，用时间复杂性表示渐进运行时间。 在输入规模相同的情况下，有些算法的效率会有显著差异。对这样算法需要区分其最优效率、最差效率和平均效率。 编辑ppt 时间

15、复杂性的形式化符号有O、和。对所有足够大的n，设t(n)和g(n)为自然数集合到非负实数集合的函数，t(n)表示一个算法的运行时间，g(n)用于比较，c和n0分别为大于0的常数和整数，则t(n)O(g(n)表示t(n)的上界是g(n)的常数倍，即对所有的n n0，t(n) cg(n)；t(n)(g(n)表示t(n)的下界是g(n)的常数倍，即对所有的n n0，t(n) cg(n)；t(n)(g(n)表示t(n)的上、下界均由g(n)的常数倍确定，即对所有的n n0，c1g(n) t(n) c2g(n)，c1和c2为常数。可用图表示，图中n0前无关紧要。 编辑ppt 时间复杂性的形式化符号 cg

16、(n)t(n)n0nOcg(n)t(n)n0nc1g(n)t(n)n0nc2g(n)编辑ppt4 算法评估 从算法时间效率角度，存在三类算法。多项式时间算法是指算法的时间复杂性函数为O(p(n)，p是n的多项式函数，如O(n2)。 指数时间算法是指算法的时间复杂性函数不能写成O(p(n)形式，即算法的计算时间需要用指数函数限界，如O(2n)。 伪多项式时间算法是指算法的时间复杂性函数为O(M p(n)，M为问题中出现的最大整数。 编辑ppt 算法评估通常包括有效性和效率两方面，上述三类算法的评估策略如下： （1）多项式算法得到的问题解是精确解，在最坏情况下，算法求解时间是多项式级的，因此，算法的有效性和效率的计算机仿真试验是演示性。算法的性能评估主要是通过理论分析，得到在最差情形下算法的时间复杂性和空间复杂性。 （2）对伪多项式算法，理论分析可以得到在最坏情况下的计算性能，但通常需要做算法的计算机仿真试验，测试算法的平均性能（效率），这样评价所设计的算法更科学。编辑ppt （3）对近似算法（如启发式、元启发式算法），解的质量评估是主要关注点，规则和知识