算法设计与分析 课件 11-课程总结

信息工程大学算法设计与分析知识点梳理国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版课程定位和作用通过学习该课程，提高求解问题能力（高效算法）通过算法分析，评价算法，进一步改进算法通过算法设计策略，学习多种思维方法透过经典问题（典型应用），学习问题抽象分析和求解方法并扩展到更多应用以算法分析方法和常用的算法设计策略为主要内容算法分析□算法分析准则□时间复杂度分析方法□最优性定义与证明□NP完全性理论算法设计□递归与分治□动态规划□贪心法□回溯法□分支限界法□概率算法一.算法分析1.1算法的定义和五个特征1.3时间复杂度分析的两种方法1.4最优性定义与证明1.5

NP完全理论1.2算法分析的五个准则要求：1.掌握基本概念、原理和方法。2.运用时间复杂度分析方法评价算法优劣。非形式定义：一个有穷的运算规则序列运算规则确定了问题的解决方法序列给出了解决方法的先后顺序有穷性表现在：运算规则序列是有穷的

对问题的合法输入，算法经有限

次运算后能终止并给出问题的解算法的定义确定性

－算法中的每种运算有确切的定义，

不允许存在多义性和不确定性。可行性

－每种运算都是相当基本的、可行

的，原则上能精确实施。有穷性

－算法执行有穷步运算后能够终止。有0个或1个以上的输入有1个以上的输出

算法的五个特征返回正确性----算法设计的最低要求工作量----算法在理论上需要的时间空间量----算法在理论上需要的存储空间简单性----算法可被理解程度最优性----算法在同类算法中的水平算法分析的五个准则返回基石：计数法，即统计算法执行的基本操作次数。时间复杂度分析方法第一种：非递归算法的时间复杂度分析方法第二种：递归算法的时间复杂度分析方法步骤：1.确定基本操作； 2.分析有多少种输入； 3.分析每种输入执行的基本操作次数； 4.确定每种(类)输入出现的概率； 5.按相关公式建立关于n的表达式； 6.化简，得到相对简单的结果； 7.用渐近符号表示(得到最高阶项，忽略系数和低阶项）第一种：非递归算法的时间复杂度分析方法按照工作量的定义，分析基本操作的执行次数。算法的工作量通常有“平均时间复杂度（或平均性态）”和“最坏时间复杂度(或最坏性态)”两种表示。

Dn：输入规模为n的输入集合I：一个长度为n的输入P(I)：输入为I出现的概率t(I)：对于I,算法做的基本操作次数平均时间复杂度：最坏时间复杂度：注:实践表明，可操作性最好、且最有实际价值的，是最坏时间复杂度。

渐近时间复杂度：随着n的不断增大，算法时间复杂度的增长趋势，用渐近符号表示

O(f(n))=g(n)（正确吗？）f(n)=2n3+4n2+logn=O(n3)步骤： 1.建立递推方程； 2.求解递推方程。迭代法递归树主定理……第二种：递归算法的时间复杂度分析方法递推方程：一般形式为：其中，ni为第i个子问题的规模；T(ni)为第i个子问题的时间复杂度；g(n)为把大问题划分成若干小问题及把各个小问题的解合并成整个问题的解所需的工作量之和；Ci为常数；ni<n，1≤i≤k。主定理

T(n)=

(nlogba)T(n)=

(f(n))f(n)

(f(n)logn)n

n-

对于红色部分，主定理无法求解。如f(n)=nlogn，a=b=2，nlogn=

(n1+

)

主定理Ο(1)：常数级Ο(logn)：对数级Ο(n)：为线性级Ο(nc)：多项式级Ο(cn)：指数级Ο(n!)：阶乘级定理1：对每个b>1和每个a>0，有logbn=o(na)定理2：对每个r>1和每个d>0，有nd=o(rn)时间复杂度的比较返回算法类－解决某一问题的各种算法中，用算法所执行的基本操作对算法进行划分，基本操作相同的算法为同类算法。最优算法－若算法A在最坏情况（或平均情况）下是最优的，是指：算法A所在的算法类中的其他算法，在最坏（或平均）情况下，执行基本操作的次数不比A更少。最优算法可能不只一个。注：算法的最优性定义以最坏情况说明：求基本操作次数：求解对尺寸为n的任何输入，算法A至多做的基本操作次数W(n)。证明一个定理：算法类中的任何一个算法，在最坏情况下，至少做F(n)次基本操作。比较：若W(n)=F(n)，则A是该算法类中在最坏情况下的最优算法，否则A不是最优算法。算法的最优性证明方法返回NP完全理论算法领域的理论知识：可计算与计算复杂性可计算性：问题是否可计算不可计算可计算现实可计算：存在多项式时间的算法理论可计算：未找到多项式时间的算法易解问题与难解问题P类问题NP类问题NPC类问题NP难问题NP完全理论3个基本计算模型：随机存取机RAM、随机存取存储程序机RASP、图灵机TM二.算法设计要求：掌握每种算法设计策略的基本思想、解题步骤、时间复杂度分析方法。

掌握每种算法设计策略的典型应用的求解方法。

能够灵活运用算法设计策略解决具体问题。二.算法设计□递归与分治分治就是“分而治之”，实质是将原问题分成n个规模较小而结构与原问题相似的子问题，然后递归地解这些子问题，最后合并其结果就得到原问题的解。三个步骤如下：分解(Divide)：将原问题分成一系列子问题；解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解；合并(Combine)：将子问题的结果合并成原问题的解。divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解决小规模的问题

//分解

dividePintosmallersubinstancesP1,P2,...,Pk；

//递归求解各子问题

for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);

//将子问题的解合并为原问题的解

returnmerge(y1,...,yk);}分治法设计的平衡原则：使子问题的规模大致相同二.算法设计□递归与分治典型应用：找伪币找最大最小值二分查找快速排序归并排序棋盘覆盖大整数相乘Strassen矩阵相乘最大子段和问题……分治法的时间复杂度分析方法：建立并求解递推方程分治法的思路描述重点：怎么分、怎么治、怎么合并二.算法设计□动态规划最优子结构性质：问题的最优解包含子问题的最优解。重叠子问题性质：每次产生的子问题并不总是新问题，有些子问题重复出现多次。动态规划解题步骤：找出最优解的性质，并刻划其结构特征。递归地定义最优值（动态转移方程）。以自底向上的方式计算出最优值（或采用备忘录方法）。根据计算最优值时得到的信息，构造最优解。□动态规划二.算法设计典型应用：数塔问题0-1背包问题矩阵连乘问题、石子合并问题最长公共子序列问题最长不上升子序列问题最大子段和问题……动态规划复杂度分析方法：时间复杂度：

分析循环的嵌套层数

及循环次数

空间复杂度：取决于表的规模动态规划的思路描述重点：建立动态转移方程，解释具体含义二.算法设计□贪心最优子结构性质：问题的最优解包含其子问题的最优解。贪心选择性质：问题的最优解可以通过一系列局部最优解得到。贪心法的特点：算法简单时间和空间复杂性低贪心算法不一定总产生最优解选择正确的贪心选择策略是关键贪心算法是否产生最优解，需严格证明可用于求近似解二.算法设计□贪心典型应用：活动安排问题会场安排问题最优装载问题最短服务时间问题部分背包问题区间覆盖问题哈夫曼编码问题最小生成树问题单源最短路径问题……贪心法时间复杂度分析方法：

是否需要排序:O(nlogn)处理过程的复杂度与具体问题相关贪心法的思路描述重点：确定贪心选择策略、描述具体过程

回溯法也称为通用解题法，是一种对问题解空间树进行深度优先的搜索算法，并在搜索过程中利用剪枝函数（约束函数和限界函数）提高搜索效率。二.算法设计□回溯回溯法的特征：回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。运用回溯法解题通常包含以下三个步骤：针对所给问题，定义问题的解空间确定易于搜索的解空间结构以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索二.算法设计□回溯回溯法的要素：解向量，解空间，解空间树，深度优先搜索，剪枝函数两类典型的解空间树：子集树：当所给问题是从n个元素中找出满足某种性质的子集时，相应的解空间树称为子集树。排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。子集树排列树二.算法设计□回溯子集树算法框架voidBackTrack(intt){if(t>n)Output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(Constraint(t)&&Bound(t))BackTrack(t+1); }}二.算法设计□回溯排列树算法框架voidBackTrack(intt){if(t>n)Output(x);elsefor(inti=t;i<=n;i++){

swap(x[t],x[i]);if(Constraint(t)&&Bound(t))BackTrack(t+1);swap(x[t],x[i]); }}二.算法设计□回溯二.算法设计□回溯典型应用：N皇后问题0-1背包问题旅行售货员问题子集和问题装载问题符号三角形问题圆排列问题批处理作业调度问题……回溯法时间复杂度分析方法：

取决于是子集树O(2n)还是排列树O(n!)回溯法的思路描述重点：给出解空间，确定是子集树还是排列树，设计剪枝函数二.算法设计□分支限界分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数达到极大或极小的解，即在某种意义下的最优解。

为了上述求解目标，分支限界法以广度优先或最小代价优先的方式来搜索解空间。分支限界的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。二.算法设计□分支限界基本要素：解向量、解空间、解空间树、广度优先搜索、约束函数、限界函数两种实现：先进先出式、优先队列式要点：合理设计限