算法分析和设计基本知识点复习共30页文档

算法设计与分析基础知识概述算法设计与分析是计算机科学中的重要内容，它旨在解决各种实际问题，并通过分析算法的性能来评估算法的有效性和效率。

本文将对算法设计与分析的基础知识进行概述，包括算法的定义、算法的特性、算法的分类、常见算法设计技巧以及算法分析的方法等。

一、算法的定义算法是一组有限指令的序列，用于解决特定问题或达成特定目标。

它具有以下特点：1. 输入：算法接受零个或多个输入。

2. 输出：算法产生一个或多个输出。

3. 明确性：算法的每一条指令必须明确而无歧义，确保执行结果是确定的。

4. 有限性：算法在有限的步骤内必须终止。

5. 可行性：算法的每一条指令必须能够实际执行。

二、算法的特性算法可以根据其特性进行分类和比较，常见的算法特性有以下几个方面：1. 正确性：算法的执行结果要与问题的要求一致，满足预期的输出。

2. 可读性：算法应该易于理解和阅读，使得其他人能够轻松地理解算法的过程和步骤。

3. 高效性：算法应该能够在合理的时间内产生结果，避免不必要的时间和空间开销。

4. 简洁性：算法应该尽可能简洁，去除不必要的冗余和复杂性。

5. 健壮性：算法应该能够处理各种异常情况，并给出合理的响应和处理方式。

三、算法的分类根据算法的特点和应用范围，可以将算法分为以下几类：1. 穷举法：通过遍历所有可能的解来寻找最优解，适用于问题规模较小的情况。

2. 贪心算法：在每个步骤选择当前最优解，通过局部最优解的选择来达到全局最优解。

3. 分治算法：将问题划分为多个独立的子问题，逐个解决子问题并将结果合并，适用于问题规模较大的情况。

4. 动态规划算法：通过将问题划分为重叠子问题，并利用子问题的解来求解当前问题。

5. 回溯算法：通过逐步尝试所有可能的解，并在搜索过程中剪枝，适用于求解组合优化问题。

6. 随机算法：利用随机性来搜索解空间，通过概率统计的方式获得更好的解。

四、常见算法设计技巧为了提高算法的效率和性能，常见的算法设计技巧有以下几个方面：1. 分解：将复杂的问题分解为多个简单的子问题，通过解决子问题来解决整个问题。

算法设计与分析重点总结考试题型：选择 2* 10个填空2* 10个简答 3* 4个程序分析填空 4* 4个综合（代码）8* 4个第⼀章基础知识1.算法的定义算法就是解决问题的⽅法，是解决某⼀特定问题的⼀组有穷指令的序列，是完成⼀个任务所需要的具体步骤和⽅法2.算法的特征有限性 ⼀个算法总是在执⾏了有穷步的运算之后终⽌确定性：算法的每种运算必须要有确切的定义，不能有⼆义性。

输⼊：每个算法有0个或多个输⼊。

所谓0个输⼊是指算法本⾝定出了初始条件。

输出：⼀个算法产⽣⼀个或多个输出，这些输出是同输⼊有某种特定关系的量可⾏性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由⼈⽤纸和笔在有限的时间内完成。

（实数的算术运算是“不能⾏”的）3.计算过程只满⾜确定性、能⾏性、输⼊、输出四个特性但不⼀定能终⽌的⼀组规则4.算法的有穷性意味着不是所有的计算机程序都是算法5.算法正确性证明数学归纳法，反例：能够使算法运⾏失败的输⼊实例6.算法的好坏：通过数学⽅法进⾏分析，时间复杂度，空间复杂度，循环次数（归并，快排，贪⼼的复杂度）7.算法运⾏中主要影响运⾏时间的语句是基本操作，即占有最多⽐例的语句8.时间复杂度分析：1）确定⽤来表⽰问题规模的变量；2）确定算法的基本操作；3）写出基本操作执⾏次数的函数（运⾏时间函数）；4）如果函数依赖输⼊实例，则分情况考虑：最坏情况、最好情况、平均情况；5）只考虑问题的规模充分⼤时函数的增长率，⽤渐近符号O 、Θ、Ω 、o 来表⽰。

6）常⽤O和Θ9.基本操作算法中的某个初等操作，基本操作的选择，必须反映出该操作随着输⼊规模的增加⽽变化的情况第⼆章递归算法1.递归若⼀个对象部分地包含它⾃⼰, 或⽤它⾃⼰给⾃⼰定义, 则称这个对象是递归的；若⼀个过程直接地或间接地调⽤⾃⼰, 则称这个过程是递归的过程。

分为直接递归和间接递归2.特点（1）将问题分解成为形式上更加简单的⼦问题来进⾏求解，递归过程⼀般通过函数或⼦过程来实现（2）问题求解规模缩⼩,把问题转化为规模缩⼩了的同类问题的⼦问题（3）相邻两次重复之间有紧密的联系（4）是否收敛，即终⽌条件3.使⽤递归的三种情况问题的定义数据结构问题求解的过程4.递归模型递归边界（递归的终⽌条件）和递归体5.过程先将整个问题划分为若⼲个⼦问题,通过分别求解⼦问题,最后获得整个问题的解。

1. 算法定义：算法是解决问题的方法或过程。

算法的性质：输入：一个算法有零个或多个输入。

输出：一个算法有一个或多个输出。

确定性：算法中每一条指令必须有确切的含义，不存在二义性。

可行性：算法中的每条指令执行次数有限，执行时间时间也有限。

2.程序是算法用某种程序设计语言的具体实现，程序可以满足算法的有限性。

最基本的运算有：赋值运算，算数运算，逻辑运算，关系运算。

3. 数据分为，对象数据，结果数据，他们可以是所有类型中的任何一种类型。

表示方式有集合(枚举)，结构体，指针。

数据类型分为：boolean,byte,char,double,float,int,long,short.4. 描述算法的几种方式：自然语言方式，表格方式，图标（流程图），伪码语言(类程序设计语言)。

5. 算法的复杂性：是该算法所需要的计算机资源的多少，时间资源的量称为时间复杂性和空间资源的量称为空间复杂性。

用n，i，a表示算法要解的问题的规模，算法的输入，算法本身，而且c表示复杂性，应该有c=f（n，i，a）。

5.递归：直接或间接的调用本身的算法成为递归算法。

用函数自身给出定义的函数成为递归函数。

阶乘函数；n！={1 n=0；n（n-1）！n>0；}Public static int factorial(int n){If (n==0)return 1;Return n* factorial (n-1);}斐波那契（Fibonacci）数列F(n)= 1 n==0,1; F(n-1)+F(n-2) n>1;Public static int fib(int n){ if (n<=1) return 0;if (n>1) return fib(n-1)+fib(n-2);}排列问题：Public static void perm (obejt[]list,int k,int m){If (k==m){For (int i=0;i<=m;i++)System.out.print(list[i])System.out.println() }ElseFor (int i=k;i<=m;i++){mymath.swap(list ,k,i);Perm(list,k+1,m);Mymath.swap(list ,k,i); }}整数划分问题Public static int q(int n ,int m ){if ((n<1)||(m<1))return 0;If((n==1)||(m==1))return 1;If(n<m)return q(n,m-1)+1;Return q(n,m-1)+q(n-m,m);}6.系统需要在运行调用算法前先完成3件事情：1.为所有实参指针，返回地址等信息给被调用算法。

·算法是指解决问题的方法和过程。

算法是由若干条指令组成的有穷序列。

·算法特性：输入、输出、确定性、有限性（执行时间和执行次数）（有五个空再加上可行性）。

·程序是算法用某种程序设计语言的具体实现，程序可不满足有限性的特性。

·程序调试只能证明程序有错，不能证明程序无错误!·算法复杂性= 算法所需要的计算机资源。

·算法的复杂性取决于：(1)求解问题的规模N；(2)具体的输入数据I；(3)算法本身的设计A。

·可操作性最好且最有实际价值的是最坏情况下的时间复杂性。

第二章递归与分治策略二分搜索技术：O（logn）大整数乘法：O（n log3）=O（n1.59）Strassen矩阵乘法：O（n log7）=O(n2.81) 棋盘覆盖：O（4k）合并排序和快排：O（nlogn）线性时间选择：O(n)最接近点对问题：O(nlogn) 循环赛日程表：O(n2)·分治法思想：将一个难以解决的问题分割成一些规模较小的相同问题，以便逐个击破，分而治之。

边界条件与递归方程是递归函数的两大要素。

递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

·分治法时间复杂度分析：T(n)<= O(1) n=n0aT(n/b)+f(n) n>n0若递归方式为减法：T(n) = O(a n)若递归方式为除法：f(n)为合并为原问题的开销：f(n)为常数c时：T(n)=O(n p)f(n)为线性函数：O(n) a<ba是子问题个数，b是递减的步长T(n)= O(nlog b n) a=bO(n p) a>b,p=log b af(n)为幂函数n x时：O(n x) a<f(b)T(n)= O(n p log b n) a=f(b)O(n p) a>f(b),p=log b a·证明算法的正确性：部分正确性、终止性。

算法设计考试重点整理题型：一选择题（10*2=20 分）二简答题（4*5=20 分）三应用题（3*10=30 分）四算法题（3*10=30 分）第一、二章算法的定义：解某一特定问题的一组有穷规则的集合（对特定问题求解步骤的一种描述，是指令的有限序列）算法的特征：1）有限性 2）确定性 3）输入 4）输出 5）能行性算法分析的目的：基本数据结构：线性结构(元素之间是一对一的关系)用顺序存储结构存储的线性表称为顺序表用链式存储结构存储的线性表称为链表。

树形结构(元素之间是一对多的关系)图(网)状结构(元素之间是多对多的关系)栈：是一种只允许在表的一端进行插入或删除操作的线性表。

允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。

当栈中没有数据元素时，称之为空栈。

栈的插入操作称为进压栈，删除操作称为出栈。

队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。

允许进行插入操作的一端称为队尾。

允许进行删除操作的一端称为队头。

当队列中没有数据元素时，称之为空队列。

队列的插入操作称为进队或入队。

队列的删除操作称为退队或出队。

树：树型结构是一种非线性结构，它用于描述数据元素之间的层次关系图图：G＝(V，E)是一个二元组其中：V是图G中数据元素（顶点）的非空有限集集合E是图G中关系的有限集合由表达式求渐进表达式：例：(n2+n)/4 n2/4（增长速率最快的那一项）时间复杂度的计算：（P23）性能的比较：O(1) < O(log2n) < O(n) < O(nlog2n) =O(nlogn)< O(n2) < O(n3) < O(n k) < O(2n)第三章算法思想、稳定性、时间复杂度、应用、排序的移动次数：希尔排序（数据结构P265）：先将待排序列分割为若干个子序列分别进行直接插入排序；待整个序列基本有序时，再对全体记录进行一次直接插入排序。

也称缩小增量的直接插入排序。

算法设计与分析的复习要点第一章：算法问题求解基础算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

一．算法的五个特征：1．输入：算法有零个或多个输入量；2．输出：算法至少产生一个输出量；3．确定性：算法的每一条指令都有确切的定义，没有二义性；4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；5．有穷性：算法必须总能在执行有限步之后终止。

二．什么是算法？程序与算法的区别1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。

三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。

四．系统生命周期或软件生命周期分为：开发期：分析、设计、编码、测试；运行期：维护。

五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。

六．算法分析：是指对算法的执行时间和所需空间的估算。

算法的效率通过算法分析来确定。

七．递归定义：是一种直接或间接引用自身的定义方法。

一个合法的递归定义包括两部分：基础情况和递归部分；基础情况：以直接形式明确列举新事物的若干简单对象；递归部分：有简单或较简单对象定义新对象的条件和方法八．常见的程序正确性证明方法：1.归纳法：由基础情况和归纳步骤组成。

归纳法是证明递归算法正确性和进行算法分析的强有力工具；2.反证法。

第二章：算法分析基础一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。

二．会证明5个渐近记法。

（如书中P22-25例2-1至例2-9）三．会计算递推式的显式。

（迭代法、代换法，主方法）四．会用主定理求T(n)=aT(n/b)+f(n)。

（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征：1.正确性：算法的执行结果应当满足预先规定的功能和性能要求；2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试；3.效率：算法应有效使用存储空间，并具有高的时间效率；4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。

算法设计与分析复习要点一、单项选择题（本大题共15小题，每小题2分，共30分）二、填空题（本大题共15空，每空1分，共15分）三、分析题（本大题共5小题，每小题5分，共25分）四、综合题（本大题共4小题，1、2题每题6分，3题8分，4题10分，共30分）第2章，导引与基本数据结构：1、什么是算法, 算法的5个特性；对一个算法作出全面分析的两个阶段。

P245个特性：确定性、能行性、输入、输出、有穷性两个阶段：事前分析、事后测试2、O(g(n))，Ω(g(n))， (g(n))的含义。

3、多项式时间算法：可用多项式（函数）对其计算时间限界的算法。

4、常见的多项式限界函数所表示算法时间复杂度的排序：Ο(1) <Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)5、指数时间算法：计算时间用指数函数限界的算法6、常见的指数时间限界函数：Ο(2n) < Ο(n！) < Ο(n n)11()2(1)11()21nn T n T n n T n =⎧=⎨-+>⎩⇒=-7、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。

8、复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接表存储方法。

9、能写出图的深度优先序列和广度优先序列。

10、会求如下一些简单的函数的上界表达式： 3n 2+10n =O(n 2)第3、4章 递归与分治算法1、理解递归算法的优缺点，深刻理解递归算法的执行过程。

如能写出解决n 阶汉诺塔问题的解，并能分析写出3阶汉诺塔问题的递归执行轨迹。

2、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

3、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。

为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。

算法设计与分析期末备考知识点总结●通俗地说，算法是解决咨询题的办法，严格地讲，算法是对特定咨询题求解步骤的一种描述，是指令的有限序列。

●算法还必须满脚一下五个重要特性：输入、输出、有穷性、确定性、可行性。

●程序（Program）是对一具算法使用某种程序设计语言的具体实现，原则上，算法能够用任何一种程序设计语言来实现。

啥是算法的计算复杂性？●算法分析指的是对算法所需要的两种计算机资源——时刻和空间(时刻复杂性和空间复杂性举行估算，所需要的资源越多，该算法的复杂性就越高。

●表示计算复杂性的O你掌握了？若存在两个正的常数c和n0，关于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))（或称算法在O(f(n))中）。

我们要紧介绍了哪几种算法设计办法？分治法：将一具难以直截了当解决的大咨询题，分割成一些规模较小的子咨询题，以便各个击破，分而治之。

减治法：减治法在将原咨询题分解为若干个子咨询题后，利用了规模为n 的原咨询题的解与较小规模（通常是n/2）的子咨询题的解之间的关系，这种关系通常表现为：（1）原咨询题的解只存在于其中一具较小规模的子咨询题中；（2）原咨询题的解与其中一具较小规模的解之间存在某种对应关系。

由于原咨询题的解与较小规模的子咨询题的解之间存在这种关系，因此，只需求解其中一具较小规模的子咨询题就能够得到原咨询题的解。

动态规划法、贪心算法、回溯算法、概率RAM程序分治法------合并排序设算法4.3对n个元素排序的时刻复杂性为T(n)，则该二路归并排序算法存在如下递推式：二路归并排序的时刻代价是O(nlog2n)。

所需空间只要O(m+n+min(m, n))的空间就够了(假设两个合并串的长度分不为m和n)。

分治法------快速排序在最好事情下在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时刻为O(n)。

时刻复杂度为O(nlog2n)。

在最坏事情下必须通过n-1次递归调用才干把所有记录定位，而且第i趟划分需要通过n-i 次关键码的比较才干找到第i个记录的基准位置，所以，总的比较次数为：时刻复杂度为O(n2)分治法------最大子段递推式：算法时刻复杂度：O(nlog2n)分治法------棋盘覆盖咨询题T(k)满脚如下递推式：分治法------循环赛日安排咨询题基本语句的执行次数是：算法的其时刻复杂性为O(4k)。

《算法分析与设计》课程复习资料一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树 二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。

2.简述回溯法解题的主要步骤。

3.简述动态规划算法求解的基本要素。

4.简述回溯法的基本思想。

5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

6.简要分析分支限界法与回溯法的异同。

7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。

9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。

10.简述分析贪心算法与动态规划算法的异同。

三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。

2.按要求完成以下关于排序和查找的问题。

①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。

②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。

③给出上述算法的递归算法。

④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。

3.已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。

4.根据分枝限界算法基本过程,求解0-1背包问题。

已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。

算法是一系列解决问题的清晰指令，也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。

简单的说，就是解决问题的一种方法或过程。

算法－特征：（1）确定性（2）多样性（3）有穷性（4）输出所需资源越少，该算法越好，计算机最重要的资源是时间和空间把基本操作（最重要的操作）次数作为算法运行时间的度量单位。

•T(n)≈c op C(n)基本操作的执行时间基本操作次数算法输入规模n为时间效率的参数算法的时间效率和空间效率都用输入规模的函数进行度量O(g(n)) 是增长次数小于等于g(n)(以及其常数倍，n趋向于无穷大)的函数集合。

符号О成立条件：对于所有足够大的n，t(n) 的上界由g(n)的常数倍数所确定。

即，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥ n0来说，t(n) ≤c g(n)Ω(g(n))代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合符号Ω成立条件：对于所有足够大的n，t(n)的下界由g(n)的常数倍所确定，即，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥ n0来说，t(n) ≥c g(n)Θ(g(n))是增长次数等于g(n) (以及其常数倍,n趋向于无穷大)的函数集合。

符号Θ成立条件：对于所有足够大的n，t(n) 的上界和下界都由g(n)的常数倍数所确定，即，存在大于0的常数c1，c2和和非负的整数n0，使得：对于所有的n≥ n0来说，c2g(n) ≤t(n) ≤ c1g(n)算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分。

动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质矩阵连乘计算次序问题的最优解包含着其子问题的最优解。

这种性质称为最优子结构性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。

这种性质称为子问题的重叠性质动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果通常不同的子问题个数随问题的大小呈多项式增长动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。

第一章算法概述1、算法的五个性质：有穷性、确定性、能行性、输入、输出。

2、算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A)，C=F(N,I,A。

3、算法的时间复杂度的上界，下界，同阶，低阶的表示。

4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。

5、常用的几种数据结构：线性表、树、图。

第二章递归与分治1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。

递归的时间复杂性可归结为递归方程：1 11= 1T(n) <aT(n—b) + D(n) n> 1其中，a是子问题的个数，b是递减的步长，~表示递减方式，D(n)是合成子问题的开销。

递归元的递减方式~有两种：1、减法，即n -b，的形式。

2、除法，即n / b，的形式。

2、D(n)为常数c：这时，T(n) = 0(n P)。

D(n)为线形函数cn：r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x：r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI：中，p= log b ao考虑下列递归方程：T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解：方程中均为a = 4，b = 2，其齐次解为n2。

对⑴，T a > b (D(n) = n) /• T(n) = 0(n);对⑵，•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶，•/ a < b3(D(n) = n3) - T(n) = 0(n3)；证明一个算法的正确性需要证明两点：1、算法的部分正确性。

《算法设计与分析》复习要点2.算法的概念：答：算法是求解一类问题的任意一种特殊的方法。

一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

注：算法三要素：1、操作2、控制结构3、数据结构3.算法有5大特性：答：输入、输出、确定性、能行性、有穷性。

注：输入：一个算法有０个或多个输入；输出：一个算法将产生一个或多个输出。

确定性：一个算法中每一步运算的含义必须是确切的、无二义性的；可行性：一个算法中要执行的运算都是相当基本的操作，能在有限的时间内完成；有穷性：一个算法必须在执行了有穷步运算之后终止；4.算法按计算时间可分为两类：答:多项式时间算法的渐进时间复杂度:O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)，具有此特征的问题称为P为题。

有效算法。

指数时间算法的渐进时间复杂度之间的关系为：O(2^n)<O(n!)< O(n^n)，具有此特征的问题称为NP问题。

注：可以带1或2这些数字来判断它们之间的大小关系。

5.一个好算法的4大特性：答：正确性、简明性、效率、最优性。

注：正确性：算法的执行结果应当满足预先规定的功能和性能要求。

简明性：算法应思路清晰、层次分明、容易理解。

利于编码和调试。

效率：时间代价和空间代价应该尽可能的小。

最优性：算法的执行时间已经到求解该类问题所需要时间的下界。

6.影响程序运行时间的因素：1、答：程序所以来的算法。

问题规模和输入数据。

计算机系统系能。

注：算法运行的时间代价的度量不应依赖于算法运行的软件平台，算法运行的软件包括操作系统和采用的编程语言及其编译系统。

时间代价用执行基本操作（即关键操作）的次数来度量，这是进行算法分析的基础。

7.关键操作的概念答：指算法运行中起主要作用且花费最多时间的操作。

1.简述分治法是怎样的一种算法设计策略：答：将一个问题分解为若干个规模较小的子问题,且这些子问题互相独立且与原问题类型相同,递归地处理这些子问题，直到这些子问题的规模小到可以直接求解，然后将各个子问题的解合并得到原问题的解。

第一章概述算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。

算法的特征：可终止性：算法必须在有限时间内终止；正确性：算法必须正确描述问题的求解过程；可行性：算法必须是可实施的；算法可以有0个或0个以上的输入；算法必须有1个或1个以上的输出。

算法与程序的关系：区别：程序可以不一定满足可终止性。

但算法必须在有限时间内结束；程序可以没有输出,而算法则必须有输出；算法是面向问题求解的过程描述，程序则是算法的实现。

联系：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性性质。

算法描述方式：自然语言，流程图，伪代码，高级语言。

算法复杂性分析：算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。

算法复杂性度量：期望反映算法本身性能，与环境无关。

理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。

一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。

即C=F(N, I, A)。

第二章递归与分治分治法的基本思想：求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。

各个击破，分而治之。

分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。

递归是分治法中最常用的技术。

使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

算法设计考试重点整理题型:一选择题(１0*2=20 分)二简答题(４*5＝20分)三应用题(３*１０=30 分)四算法题(３＊１0=30 分)第一、二章算法的定义:解某一特定问题的一组有穷规则的集合(对特定问题求解步骤的一种描述,就是指令的有限序列)算法的特征:1)有限性２)确定性３)输入4)输出5)能行性算法分析的目的:基本数据结构:线性结构(元素之间就是一对一的关系)用顺序存储结构存储的线性表称为顺序表用链式存储结构存储的线性表称为链表。

树形结构(元素之间就是一对多的关系)图(网)状结构(元素之间就是多对多的关系)栈:就是一种只允许在表的一端进行插入或删除操作的线性表。

允许进行插入、删除操作的一端称为栈顶,另一端称为栈底。

当栈中没有数据元素时,称之为空栈。

栈的插入操作称为进压栈,删除操作称为出栈。

队列:只允许在一端进行插入操作,在另一端进行删除操作的线性表。

允许进行插入操作的一端称为队尾。

允许进行删除操作的一端称为队头。

当队列中没有数据元素时,称之为空队列。

队列的插入操作称为进队或入队。

队列的删除操作称为退队或出队。

树:树型结构就是一种非线性结构,它用于描述数据元素之间的层次关系图图:G＝(V,E)就是一个二元组其中:V就是图G中数据元素(顶点)的非空有限集集合E就是图G中关系的有限集合由表达式求渐进表达式:例:(n２+ｎ)／4 ｎ2/4(增长速率最快的那一项)时间复杂度的计算:(Ｐ２３)性能的比较:O(1) <O(log2n)< O(n) ＜O(nlog2ｎ) =O(ｎlogn)< Ｏ(n2) < Ｏ(n３) <O(n k) <Ｏ(2n)第三章算法思想、稳定性、时间复杂度、应用、排序的移动次数:希尔排序(数据结构P２65):先将待排序列分割为若干个子序列分别进行直接插入排序;待整个序列基本有序时,再对全体记录进行一次直接插入排序。

也称缩小增量的直接插入排序。

0/1背包问题：给定n 个重量为｛w 1，w 2，...，w n ｝、价值为｛v 1，v 2，...，v n ｝的物品和一个容量为C 的背包，应选择哪些物品装入背包，才能使装入背包的物品价值最高？ 蛮力法：给出所有子集，计算子集的总重量和总价值，进行比较。

动态规划法：证明0/1背包问题，满足最优性原理，分支限界法：用贪心法求得背包问题的下界，再求得上界：将背包中剩余容量全部装入第i+1个物品，并可以将背包装满，限界函数：ub=v+(W-w)*(v i+1/w i+1)。

总结：1.剪枝函数给出每个可行结点相应的子树可能获得的最大价值的上界。

2.如这个上界不会比当前最优值更大，则可以剪去相应的子树。

3.也可将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点。

由此可快速获得最优解。

贪心法：选择单位重量价值最大的物品。

哈密顿回路问题：共有n 个城市，要求从一个城市出发，经过每个城市恰好一次，最后回到出发城市。

蛮力法：对于给定的无向图G=（V ，E ），依次考察图中所有顶点的全排列，满足以下条件的全排列（v i1,v i2,...,v in ）构成的回路就是哈密顿回路：（1）相邻顶点之间存在边，即（v ij ,v ij+1）∈E （1≤j ≤n-1）（2）最后一个顶点和第一个顶点之间存在边，即（v in ,v i1）∈E回溯法：假定图G=（V ，E ）的顶点集为V=｛1,2,…,n ｝，则哈密顿回路的可能解表示为n 元组X=（x 1,x 2,…,x n ），其中，xi ｛1,2,…,n ｝。

根据题意，有如下约束条件：{(x i ,x i+1)∈E(1≤i ≤n −1)(x n ,x 1)∈E x i ≠x j (1≤i,j ≤n,i ≠j )首先把所有顶点的访问标志初始化为0，然后依次为每个顶点着色。

在解空间树中，如果从根结点到当前结点对应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子树继续搜索，否则，对当前子树的兄弟子树继续搜索，即为当前顶点着下一个颜色。

期末考试题型：1 判断题（10题，10分）2 填空题（5题，10分）3 简答题（4题，20分）4 应用题（5题，60分）期末考试复习要点：1 基本概念算法：有限条指令的序列，确定了解决某个问题的运算或操作顺序（了解概念）算法的时间复杂度（了解概念）函数渐进的界O ΩΘo ω有关函数渐进的界的定理（定理1、定理2）（记住、理解）主定理（会使用主定理求解递推方程）分治法相关：分治策略:适用条件:算法的设计步骤:时间复杂度：列出关于时间复杂度函数的递推方程和初值，求解递推方程提高分治算法效率的途径：动态规划算法相关：分治策略:适用条件:算法的设计步骤:时间复杂度：（备忘录的计算工作量）贪心法：贪心法:适用条件:算法的设计步骤:贪心法正确性的证明（第一归纳法、第二归纳法）回溯与分支界限：解空间：回溯算法：分支限界算法：代价函数：界函数：多米诺性质：NP完全性问题：P问题、NP问题、NP hard问题、NPC问题2 几个重要的算法二分检索红黑树插入排序二分归并排序：快速排序堆排序PrimKruskalBellman-FordFloyd-WarshallDijkstra3 几个重要的问题背包问题选最大最小问题第K小问题最长公共子序列问题最优二叉检索树矩阵链乘法问题活动选择问题Huffman编码最小生成树连续邮资问题4 求解递推方程（公式法、迭代法、递归树、主定理）：T (n )=T (n −1)+n 2T (n )=9T (n 3)+n T (n )=T (n 2)+T (n 4)+cn c 是常数 T (n )=3T (n −1)+lg3nT (n )=5T (n 2)+(nlgn )2 T (n )=2T (n 2)+n 2lgn T (n )=T (n −1)+1nT (n )=2T (n 3)+nlgn T (n )=3T (n 5)+lg 2n T (n )=T (n 2)+2n T (n )=T(√n)+θ(lglgn )T (n )=10T (n 3)+17n 1.2 T (n )=7T (n 2)+n 3 T (n )=T (n 2+√n)+√6046 T (n )=T (n −2)+lgnT (n )=T (n 5)+T (4n 5)+θ(n ) T (n )=√nT(√n)+100n。