第1章 算法概论(4np完全性理论)
1
§1.3 NP 完全性理论
如何理解问题的难解？易解？多项式运行时间？
?多项式的运行时间认为是易解算法，当然，你认为θ(n100)难解，但次数如此高的多项式时间问题非常少，且一般都会找到一个更有效的多项式时间算法。
?对很多合理计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以用多项式时间获得解决。
2
如何理解问题的难解？易解？多项式运行时间？
多项式时间可解问题类具有很好的封闭性。比如一个多项式时间算法输出给另一个多项式时间算法作为输入，或被另一个多项式时间算法作为子程序常数次调用，这样的组合算法运行时间也都是多项式的。
3
?一般来说，将可由多项式时间算法求解的问题看成易处理的问题，而把需要超多项式时间才能解决的问题看作难处理问题。
?“NP完全”（NP-Complete）问题，它的状态是未知的，迄今为止，既没有人找出求解NP完全问题的多项式算法，也没人能够证明对这类问题不存在多项式时间算法。
?P≠NP问题，自1971年提出以后，已经成为理论计算机科学研究领域中，最深奥和最错综复杂的开放问题之一了。
4
5
?
从表面上看，有些NP 完全问题有着与多项式时间算法的问题非常相似的特点，这很诱惑。?
最短与最长简单路径：有向图G=(V,E)，单源最短路径可在O(|V|2)时间内完成，但寻找两个顶点间最长简单路径（无重复顶点）问题是NP 完全的。?欧拉游程和哈密顿回路：有向图G=(V,E)，欧拉游程指一个回路，遍历途中每条边一次，但可能不止一次的访问同一个顶点，这可在O(|E|)时间内找到。哈密顿回路也是一个回路，包含V 中每个顶点。确定有向图是否存在哈密顿回路的问题是NP 完全的。
探讨这样三类问题：P、NP、NPC（NP 完全问题）
?NPC类，称NP完全的(NP-complete)，属于NP的一个
最难的子类。如果一个问题属于NP，且与NP中任何问题一样“难的”。
?有宣称：如果任何NPC问题可以在多项式时间内解
决，则NP中所有问题都有一个多项式时间的算法，即有P=NP了。
?大多数认为，NP完全问题是难处理的，因为迄今为止
研究过的NP完全问题非常多，但还没有人将其中任何问题在多项式时间内解决。不能证明！也无法排除！
9
?NP完全问题产生于不同领域：布尔逻辑、图论、算
术、网络设计、集合与划分、存储与检索、排序与调度、代数与数论、游戏与趣味难题、自动机与语言理论、程序优化、生物学、化学、物理学……等等。
?第一个NP完全问题：布尔表达式的可满足性问题。即
Cook定理：给定一个由与、或和非门构成的布尔组合电路，判断它是可满足电路吗？
布尔表达式的可满足性问题SAT是NP完全的。基于SAT，逐渐地生成一棵以SAT为树根的NP完全问题树，其中每个节点代表一个NP完全问题，该问题可在
多项式时间内变换为其任意子节点表示的问题。目
10
前，这颗树已有几千个节点，且在继续生长。
?团问题：NP完全的团是无向图G=(V,E)的一个完全
子图，团的规模为其顶点数。判定：图中是否存在一个给定规模为k的团是NP完全的。
?顶点覆盖问题：NP完全的G的顶点覆盖是覆盖E中
所有边的顶点组成的集合，顶点覆盖规模即指它包含的顶点数。判定：图中是否存在给定规模为k的顶点覆盖，或确定具有最小规模的顶点覆盖都是NP完全的。
?哈密顿回路问题：NP完全的图G中一条包含V中每
个顶点一次(除首尾顶点是重复了两次)的一条回路。
判定：图G是否存在哈密顿回路是NP完全的。
11
12
?旅行商问题：NP 完全的?0-1整数规划问题：NP 完全的?0-1背包问题：NP 完全的?图的k 着色问题：NP 完全的?最长简单回路问题：NP 完全的?图的独立集问题：NP 完全的?子图同构问题：NP 完全的?子集和问题：NP 完全的?集合划分问题：NP 完全的?带收益和完工期限的调度问题：NP 完全的?……（已证明的NP 完全问题已有上千个之多了）典型的NP 完全问题：
典型的
NP完全问题：
13
算法分析与设计习题集整理
算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 第 5 章算法与复杂性 习题 、选择题 1. B 2. D 3. C 4. A 5. B 6. B 7. D 8.B 9.C 10.A 11.A 12.C 13.A 14.A 二、简答题 1．什么是算法，算法的特性有哪些？ 答：“算法 (Algorithm) 是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果” 。算法的特性有： (1)有穷性 (可终止性 )：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。 (2)确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。 (3)有效性 (可执行性 )：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。 (4)输入及输出：一个算法应该有零个或多个输入数据、有 1 个或多个输出数据。2．什么是算法的时间复杂度和空间复杂度，如何表示？答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。记为，T(n)，其中，n代表求解问题的规模。 算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算 机中运行所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为，S(n)，其中，n代表求解问题的规模。 时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模 n之 间的数量级关系。 3．用图示法表示语言处理的过程。 答：语言处理的过程如图所示： 4.简述算法设计的策略。 答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法， 而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中， 算法设计往往处于核心地位。 要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。在算法设计中，通常采用能近似表达性能的方法来展示某个算法的性能指标。例如，计算机对n2 2 和n ，2n的响应速度，当n比较大的时，没什么区别，便可直接认为后者算法的复杂度为 2 n。 基于算法复杂度简化表达的思想基础上，通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法，如果能保证它的最坏情况下的性能依然很好，但是在某些情况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中几乎不会碰到最坏情况下的输入，那么此时进行最坏情况分析显得有些画蛇添足，特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助估计程序的性能，作为算法分析的基本指标之一，但是平均情况和实际情况仍然会有相差很大的时候，这时便可以使用随机法来尽量模拟现实中的情况，这样可以得到在严格的概率意义上的预测运行时间。另外，对于一个经典算法，没有必要再去对该算法进行改进，研究它的上界和下界，只需要了解该算法的特性，然后在合适的时候使用它。 5.简述并行算法研究的内容。 答：（1）并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的 第一章算法的基本概念 1.1 引言 算法设计与分析在计算机科学与技术中的地位 算法（Algorithm）一词的由来。 1.1.1 算法的定义和特征 欧几里德算法： 算法1.1欧几里德算法 输入：正整数m,n 输出：m,n的最大公因子 1. int euclid(int m,int n) 2. { 3. int r; 4. do { 5. r = m % n; 6. m = n; 7. n = r; 8. } while(r) 9. return m; 10. } 一、算法的定义： 定义1.1算法是解某一特定问题的一组有穷规则的集合。 二、算法的特征： 1．有限性。算法在执行有限步之后必须终止。 2．确定性。算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。 3．输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。算法的输入是从特定的对象集合中抽取的。 4．输出。一个算法有一个或多个输出，这些输出，和输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。 1 5．能行性。算法的能行性指的是算法中有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。 1.1.2 算法设计的例子，穷举法 一、穷举法，是从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解。 二、例 例1.1百鸡问题。 “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？” a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程： b +c a（1.1.1） + 100 = b a（1.1.2） + +c 5= 100 3/ 3 c（1.1.3） %= 3 1。第一种解法： a、b、c的可能取值范围：0 ~ 100，对在此范围内的，a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。 把问题转化为用n元钱买n只鸡，n为任意正整数，则方程（1.1.1）、（1.1.2）变成：+（1.1.4） n a= + c b 3 +3/ 5（1.1.5） + c n b a= 算法1.2百鸡问题 输入：所购买的三种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[] 1. void chicken_question(int n,int &k,int g[],int m[],int s[]) 2. { 3. int a,b,c; 4. k = 0; 5. for (a=0;a<=n;a++) 6. for (b=0;b<=n;b++) 7. for (c=0;c<=n;c++) { 8. if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) { 9. g[k] = a; 10. m[k] = b; 11. s[k] = c; 12. k++; 13. } 2 计算复杂性理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。 目录 [隐藏] ? 1 简介 ? 2 历史 ? 3 基本概念和工具 o 3.1 计算模型与计算资源 o 3.2 判定性问题和可计算性 o 3.3 算法分析 o 3.4 复杂性类 o 3.5 归约 ? 4 NP与P关系问题及相关理论 o 4.1 NP和P的定义 o 4.2 NP与P关系问题 o 4.3 NP完备理论 o 4.4 电路复杂性 o 4.5 其它NP与P关系问题相关的理论 ? 5 理论与实践 ? 6 参考 ?7 外部链接 [编辑]简介 计算复杂性理论所研究的资源中最常见的是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。 时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。 空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。 复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。 [编辑]历史 在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns 的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（Time Hierarchy Theorem）。 在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardness of approximation）的研究，以及交互式证明系统（Interactive proof system）理论和零知识证明（Zero-knowledge proof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。 该领域重要的研究者有（不完全列表）： ?史提芬·古克 ?姚期智（Andrew Chi-Chih Yao） ?Allan Borodin ?Manuel Blum ?Juris Hartmanis ?Richard Karp ?Leonid Levin ?Alexander Razborov ?Michel Sipser ?Avi Wigderson ?Walter Savitch ?Richard Stearns ?Lance Fortnow ?V. Arvind ?Lazlo Babai [编辑]基本概念和工具 [编辑]计算模型与计算资源 第5章算法与复杂性 习题 一、选择题 1. B 2. D 3. C 4. A 5. B 6. B 7. D 8.B 9.C 10.A 11.A 12.C 13.A 14.A 二、简答题 1．什么是算法，算法的特性有哪些？ 答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。算法的特性有： (1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。 (2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。 (3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。 (4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。 2．什么是算法的时间复杂度和空间复杂度，如何表示？ 答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。记为，T(n)，其中，n代表求解问题的规模。 算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为，S(n)，其中，n代表求解问题的规模。 时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。 3．用图示法表示语言处理的过程。 答：语言处理的过程如图所示： 4．简述算法设计的策略。 答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。 要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。在算法设计中，通常采用能近似表达性能的方法来展示某个算法的性能指标。例如，计算机对2n 和22n n 的响应速度，当n 比较大的时,没什么区别，便可直接认为后者算法的复杂度为2n 。 基于算法复杂度简化表达的思想基础上，通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法，如果能保证它的最坏情况下的性能依然很好，但是在某些情况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中几乎不会碰到最坏情况下的输入，那么此时进行最坏情况分析显得有些画蛇添足，特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助估计程序的性能，作为算法分析的基本指标之一，但是平均情况和实际情况仍然会有相差很大的时候，这时便可以使用随机法来尽量模拟现实中的情况，这样可以得到在严格的概率意义上的预测运行时间。另外，对于一个经典算法，没有必要再去对该算法进行改进，研究它的上界和下界，只需要了解该算法的特性，然后在合适的时候使用它。 5．简述并行算法研究的内容。 答：(1) 并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 习题一复杂性分析初步 1. 试确定下述程序的执行步数，该函数实现一个m×n矩阵与一个n×p矩阵之间的乘法： 矩阵乘法运算 template 找最大最小元素 方法一 template 深圳大学实验报告 课程名称：算法设计与分析 实验名称：多种排序算法的算法实现及性能比较 学院：计算机与软件学院专业：计算机科学与技术 报告人：张健哲学号： 2013150372 班级： 3 同组人：无 指导教师：李炎然 实验时间： 2015/3/25——2015/4/8 实验报告提交时间： 2015/4/8 教务处制 一．实验目的 1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。二．实验步骤与结果 实验总体思路： 利用switch结构来选择实验所要用的排序算法，每一种排序都用相同的计算运行时间的代码，不同的算法就在算法实现部分进行改动（如下代码1至5所示）。不断的改变数据规模，每一个规模在实验时，用循环进行多次实验并作为样本记录消耗的时间。最后输出在不同排序算法下，不同的数据规模的20次实验样本和平均用时（如下图1至5所示）。 各排序算法的实现及实验结果： （注1：以下代码全部为伪代码，具体代码实现请参照程序中的代码） （注2：图中显示的时间单位均为毫秒，图中“排序所花时间”一项为平均消耗时间，平均消耗时间结果以20组样本计算平均值后取整得到（并非四舍五入）。） 1、选择排序 代码1： for i=0 to n-2 min=i for j= i+1 to n-1 if ele[min]>ele[j] min=j swap(ele[i],ele[min]) //交换 图1、选择排序在不同数据规模下排序所消耗的时间2、冒泡排序 代码2： for i= 0 to n-1 for j=0 to n-1-i if a[j]>a[j+1] swap(a[j],a[j+1]) //交换 图2、冒泡排序在不同数据规模下排序所消耗的时间 算法的含义 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 特征 一个算法应该具有以下六个重要的特征： 算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 1、有限性 算法的有穷性是指算法必须能在执行有限个步骤之后终止； 2、确切性 算法的每一步骤必须有确切的定义； 3、输入 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件； 4、输出一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 算法复杂度分析 通常一个算法的复杂度是由其输入量决定的，随着输入的增加，复杂度越大。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 方法: 时间复杂度 （1）算法耗费的时间和语句频度 一个算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。 若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。 （2）问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。 矩阵乘积问题的规模是矩阵的阶数。 一个图论问题的规模则是图中的顶点数或边数。 一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 （3）渐进时间复杂度评价算法时间性能 主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。 空间复杂度第5章算法与复杂性
第一章算法的基本概念
3 计算复杂性理论
第5章 算法与复杂性(答案)
算法分析习题参考答案第一章
算法分析及复杂性理论实验报告基本排序
算法的含义及算法复杂度分析方法