https://www.youtube.com/playlist?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY
计算问题可以定义为输入与输出之间的映射关系。输入是一个有限集合,输出也是一个有限集合。问题就是确定每个输入对应的一个或多个正确输出。
通常不会一个一个列出所有输入输出对,而是定义一个检查函数,用于检测给出的输入和输出是否匹配。
算法是一种能根据给定输入产生正确输出的固定流程。它要求输入和输出大小不变,但能处理任意规模的问题实例。
算法应是一种函数,将问题的输入映射到对应的一个或多个正确输出上。只要对每个输入都能给出正确答案,则该算法解决了这个问题。
判断是否闰年的算法流程:
生日问题定义为:给定若干人的生日,判断是否存在两个人生日相同?
一种解决此问题的算法步骤:
这样一个固定规格的算法能够处理任意数量人的生日匹配问题。
数据结构的目的是存储和操作数据。接口指定了可以存储的数据类型和支持的操作,数据结构指定了具体的表示和实现这些操作的算法。
序列接口规定了固定数量项的顺序集合。支持的操作包括:
静态数组是最自然满足序列接口要求的数据结构。它使用连续内存区域存储固定数量项。
在随机访问内存模型下,数组可以支持常数时间获取和设置项。长度也是常数时间。However,建立和迭代需要线性时间。
在内存分配模型下,给定大小n的数组可以在线性时间O(n)内建立和初始化。这意味着数组的空间复杂度与时间复杂度一致。
序列接口也可以使用动态数组实现。动态数组可以在运行时更改其容量,但是具体实现需要考虑何时和如何重新分配内存。
本节视频是在2006年算法课程上第一次算法题解讨论班。讨论班的目的是记录教师解决过去作业中的一些算法问题,让学生可以观看教师如何解决这类问题。
教师会依次解答不同的函数,比较它们在渐进性行为上大小关系。主要解决以下几点:
将函数分解成主项,比较主项求导数的变化趋势来判断大小关系。
log函数渐进性小于任何多项式函数。
指数函数渐进性最大。
使用斯特林近似公式,可以将阶乘函数表示为指数函数,更方便求导比较。
对一些近似等价的函数,使用集合括号将其括起来表示。
鼓励学生主动回答,互动提问。
第一题5个函数根据渐进性从小到大排序:
f1 < f5 < f2 < f3 < f4
第二题2组函数排序:
a组:f1 < f5 < f2 < f3 < f4 b组:多项式<指数
教师详细解释了比较过程,解答了学生提出的问题。
集合(Set)是一个存储元素的容器,可以添加、删除和查找元素。集合的接口规定了一组操作:
接口定义了集合的操作,但不定义实现细节。集合后台可以用不同数据结构实现,影响操作的效率和内存开销。
最简单的实现方式是使用数组存储元素。每个数组元素对应集合中的一个对象。
这种实现方式添加和获取元素都很简单,直接在数组末尾添加,通过遍历数组找到元素。但查找元素效率低,需要顺序遍历整个数组。
集合操作中常见的算法问题包括:
不同数据结构实现可以优化这些操作中的某些操作,但对其他操作效率可能较低。选择数据结构需要考虑算法的优先级和效率成本。
本课将介绍几种常见的数据结构,比如链表、哈希表和平衡搜索树等,以及它们相应操作的时间复杂度。通过对比不同实现,理解数据结构背后的算法思想。
在证明查找最优复杂度下的计算模型假设是比较模型。比较模型中,数据项被看作黑箱,只能通过比较键来区分。具体来说,只能通过以下操作来比较键:
比较的结果只有两种可能:true 或者 false。
可以用决策树来表示比较模型下的算法。Decision 树中的内部节点代表比较操作,叶子节点代表算法的输出结果。
算法执行时,会依次比较边沿一个从根节点到叶子节点的路径,在叶子节点停止并输出结果。这条路径所包含的比较操作数量就是该算法在最差情况下的比较次数。
对于一个存储 n 个数据项的集合数据结构,其查找算法的决策树应当满足:
否则无法正确处理所有情况下的查询请求
如果数据项数量为 n,则决策树中比较次数的最长路径的长度,就是该算法在最差情况下的时间复杂度
由于路径长度受树的高度限制,树高度就成为时间复杂度的下界
综上,在比较模型下,查找操作的时间下界是 O(logn)。
这道题要求通过大O符号分析递归结构。首先使用Mester定理直接得到结果,然后绘制计算树计数计算次数。
Mester定理分为三种情况:
如果f(n)=O(n^log_b a-ε),则T(n)=θ(n^log_b a)
如果f(n)=θ(n^log_b alog^k n),则T(n)=θ(n^log_b alog^{k+1} n)
如果f(n)=Ω(n^log_b a+ε),f(n)/n^c<1,则T(n)=θ(f(n))
同样使用Mester定理和计算树两种方法求解递归结构,得到问题一对应的大O表达式。
这道题思路跟前面不同,需要分析递归关系找到解。教师花了一个小时思考,最终证明自己的答案正确。
这是一道涉及多个结构交互的问题。教师最初给出的答案错误,但经思考后找到正确解法。
问题讨论通过Mester定理直接求解,同时绘制计算树计数计算量,两种方法互相验证。题目从简单应用变得更复杂,需要深入理解递归关系寻找解。教师重点强调仔细理解每一个步骤。
在只能进行比较操作的比较模型下,任何排序算法的时间复杂度都不能低于Ω(nlogn)。
这是因为可以将任何算法看作一棵二叉决策树。决策树有n+1个叶结点,即排序长度的所有排列方案。而二叉树的高度必须大于等于log(n+1) ,才能区分出所有叶结点 Case。因此,需要至少log(n+1)次比较操作。
希尔排序是插入排序的一种。它通过预先对元素进行部分排序,使得元素接近最终位置,从而达到减少元素移动距离,加快排序速度的目的。
希尔排序的核心思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再整个序列进行依次过程的直接插入排序。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
归并排序的工作原理是:将待排序序列分为两个以上子序列,每个子序列再递归地进行排序,然后将排序好的子序列进行排序。
快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序平均时间复杂度为O(nlogn),但是其最差时间复杂度为O(n^2),这是因为它每一次分割数据都不一定能将数据分割为两部分相当的大小。
以上三种Θ(nlogn)算法在最好情况下仍需要Ω(nlogn)的时间,具有一定限制。以下几种线性时间复杂度的排序就可以突破这个限制。
假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能需要辅助排序算法),时间复杂度可以达到O(n)。
基数排序属于非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基于某些条件,基数排序仅针对整数,其时间复杂度可以达到O(n)。
计数排序利用了一个额外的数组C来记录相应的键值,并利用C对应的位置来输出结果,避免了元素的比较操作。其时间复杂度为O(n+k)。
本问题考察如何利用哈希表实现顺序结构,具体要求:
哈希表可以实现集合,但顺序结构中元素没有键值,无法直接利用哈希表。
所以可以将元素索引作为键值存入哈希表。具体做法是:
这样利用哈希表查找和修改元素就实现了顺序结构的获取和设置功能。
由于要求线性预期时间,可以直接重建全部结构:
相比特定位置,首尾插入删除可以视为堆栈或队列操作,使用双端队列的插入删除方法可以实现常数预期时间复杂度。
二叉树(Binary Tree)是由节点和链接组成的树状数据结构。每个节点最多只能有两个子节点,即一个左子节点和一个右子节点。
二叉树有以下主要特征:
二叉树中常见概念:
二叉树支持以下常见操作:
二叉树通过使用两个指针 links(左/右)来建立节点与节点之间的关系,能代表顺序关系或无序关系。同时二叉树的高度可以是对数级时间,比链表更优。
本次课将介绍二叉树相关概念,以及计算二叉树的高度。通过理解高度,可以为后续利用二叉树支持高效操作打下基础。下次课将会详细介绍如何利用二叉树高效支持插入、删除、搜索等常见操作。
上节我们介绍了二叉树的基本概念。每个节点存储一个物品,同时包含左右指针和父指针。我们定义了节点的高度,即从该节点到树底部的最大路径长度。
二叉搜索树可以用于表示集合。它保证所有左子树节点关键字小于父节点,所有右子树节点关键字大于父节点,从而实现递增顺序的遍历顺序。这样就可以在O(h)时间内实现插入、删除和搜索操作,其中h为树高。
如果要用二叉树表示序列,遍历顺序就应保持插入顺序。搜索一个节点时,可以利用当前节点左右子树大小信息,进行类似二分搜索的递归:
但这只能在O(h)时间内完成。
为了实现O(logn)时间复杂度,需要保证二叉树的高度尽可能小。平衡二叉树(AVL树)通过在每次插入/删除后调整树形状,保证任一节点左右子树高度差的绝对值不超过1, thus实现平衡,使树高度约为O(logn)。
它通过单轮/双轮转动操作来重新平衡树形状。具体平衡算法将在后续内容中详述。
本节概述了二叉树在表示集合和序列的数据结构中的应用,以及使用AVL树来实现平衡来提升操作时间复杂度的思路。后续内容将详细介绍AVL树的平衡算法实现。
导师编写了程序测试不同数据结构的性能,包括序列和集合接口的实现。
测试结果显示:
动态数组等数组实现的接口,获取和设置元素时间很短,因为直接通过索引访问。
链表、跳表等顺序访问数据结构,插入和删除元素时间长,因为需要遍历找到位置。
二叉搜索树实现,插入、删除和搜索元素时间以对数时间增长,优于线性时间复杂度。
哈希表实现获取元素时间很短,但不支持有序操作。
序列接口实现中,平衡二叉树效率好于其他数据结构。
导师给出一个序列AVL树示例,请求删除第8个元素:
通过树结构可以看出,第8个元素是节点5。
删除节点5后,需要进行平衡操作。由于5的右子树为空,将5的父节点4设为5原来的左子树的父节点,这样就完成了删除。
更新节点4和它上层节点的高度和数量值。由于删除后子树数量和高度没有改变,所以不需要进行旋转操作来重新平衡树。
这样就完成了序列AVL树中的删除元素操作。
无。
二叉堆是一种树形结构,用于高效实现优先队列接口,包括插入和删除最大元素操作。
二叉堆有以下优点:
与AVL树相比,结构更简单。
建堆时间复杂度为O(n),比AVL树更快。
插入和删除最大元素操作时间复杂度均为O(logn)。
可以实现基于优先队列的排序算法,如堆排序。
二叉堆是基于完全二叉树实现的,具体规则如下:
完全二叉树是一种二叉树,除最后一层外,其他层都达到完全填充。
节点的键值与其在树中的位置有关:每个节点的键值都大于或等于其左右孩子节点的键值。
根节点的键值总是最大的。
利用这些性质,可以实现优先队列的相关操作:
建堆:将数组元素依次插入二叉堆,时间复杂度为O(n)。
插入:将新元素加入末尾,然后与其父节点比较键值交换位置,最多交换logn次直到满足堆性质,时间复杂度O(logn)。
删除最大元素:将根节点与最后一个叶子节点交换,删除最后一个节点,然后不断与子节点比较交换位置恢复堆性质,时间复杂度O(logn)。
查找最大元素:直接返回根节点,时间复杂度O(1)。
基于二叉堆可以实现堆排序算法。堆排序的时间复杂度为O(nlogn)。
扩宽优先搜索(BFS)是一种用于搜索所有子节点的图算法。BFS从根节点开始,由浅到深地搜索树或图。它先访问离开根节点最近的节点,然后是下一层的节点,以此类推,直到搜索整个图。
| 空间复杂度为O( | V | + | E | ),使用队列保存需要访问的节点 |
| 时间复杂度为O( | V | + | E | ),需要访问每个节点和边一次 |
这次考试的主要考核内容有:
考试不会考察具体的编程实现细节,而是要求应试者能够通过演绎的方式来说明问题的解决思路及证明其正确性。
通常有两种方法来解决计算问题:
自行设计新算法。这需要理解算法设计范式,但是这个过程非常困难。
将问题归纳成我们已学过的问题类型或者接口,然后使用相关的已知算法或数据结构来解决。
问题主要可以分为三种类型:
需要深入了解算法或数据结构的内部实现。比如操作二叉树、堆等结构。
只需要了解接口,不需要关心内部实现细节。可以直接使用算法或数据结构接口来解决问题。
需要对算法或数据结构进行修改扩展,来满足特殊问题需要。比如更新二叉搜索树节点的额外属性。
考试的主要评分标准包括:
给出的算法虽然正确但如果没有高效,或分析有误,也会扣分。
应试者需要通过归纳已知问题来给出高效且正确的解决方案,同时严格证明其各项性质,以获得最高分。
本节介绍了深度优先搜索算法。
首先讲授者回顾了图数据结构的基本概念,包括顶点、边、简单图、有向图、无向图等。图可以用邻接表的形式进行表示,每个顶点包含其出边集。
然后讲解了图搜索问题中的到达性问题。给定图中的源点与目标点,判断是否存在从源点到目标点的路径。
探索图时,即可以用广度优先搜索算法(BFS),也可以用深度优先搜索算法(DFS)。BFS会以“层次”的方式扩散,先探索距离源点最近的顶点,然后再探索更远的顶点。而DFS的思路是从源点出发,尽可能走出最远,只有走不下去时才回溯。
为了描述DFS,需要用到一个“路径树”的数据结构。与单源最短路径树类似,路径树中的每个顶点保存前驱顶点信息。通过遍历树可以得到源点到该顶点的路径。
DFS的具体步骤是:
从源点出发,标记为已经访问。
查找该点的第一个未访问邻居,将其标记为访问,并递归调用该邻居节点。
如果邻居节点全标记过访问,则回溯到上一个点,寻找下一个未访问邻居继续。
完成后,路径树中具有前驱信息的顶点即为从源点可达的顶点集。
在之前,我们只考虑图中边的数量来衡量路径的长度。现在我们将引入“权重”的概念,即给每条边赋予一个整数权重。这样路径的长度就变成路径上所有边权重的总和。
给图G赋权的方法有两种:
在邻接表中对每条边同时存储其终点和权重。
使用哈希表将每个边映射到对应的权重。两种方法都可以在O(1)时间内查询边的权重。
在加权图中,从源点s到终点t的最短路径指的是边权重总和最小的一条路径。
路径pi的权重定义为pi上所有边权重的总和:
weight(pi) = Σ weight of edges in pi
例如在示例图中,路径a-b-f-g的权重为:-5 - 4 + 2 = -7
如果图中存在负权回路,就可能导致从任意点到任意点的最短路径长度为负无限,从而失去意义。
具体来说,如果存在从点v回到点v的路径π,且weight(π)<0,则通过重复此路径,从v到任意点t的路径长度可以任意近似0。
这就是“负权环问题”。我们将在后续讨论如何识别和消除这种情况。
在未来几个视频中,我们将介绍两种算法来找到加权图中的单源最短路径:
对于均为非负权重的图,我们可以使用广度优先搜索BFS获得线性时间的解。
对于任意权重(可以包含负权)的图,我们可以使用Dijkstra算法获得渐近对数线性时间的近似解。
在这一讲中,教授讲解了图论中的一些概念。
图的半径是用于描述整个图形性质的度量之一。
对于某个点v,我们定义它的离心率为到其他任意点w的最大距离。
图的半径定义为所有点v离心率的最小值。
外层循环遍历每个点v;
内层循环计算从v到其他每个点w的最短距离,取最大值记为临时变量little r;
检查little r是否小于当前记录的半径值big r,如果小于则更新big r;
外层循环结束后,big r即为图的半径。
外层循环时间复杂度O(V);
计算最短距离可用广度优先搜索,时间复杂度O(V+E);
但这里因为图是连通图,每点都连至少一条边,所以E最少是V,时间复杂度实际上是O(E)级别;
因此整体算法时间复杂度是O(V×E)。
本小结根据教授讲课内容,将图论算法知识点进行整理,去除主观观点,保留必要详细,实现以标题索引的markdown格式笔记。
最短路径如果没有负权环,一定是简单路径,不会重复通过节点。
简单路径中的节点最多为V-1个。
Bellman-Ford算法用于单源最短路径问题,可以处理有负权和环的情况。
算法每次遍历图中所有边,更新每个节点到源节点的距离。如果在V-1次遍历后距离还可以继续更新,则说明存在负权环,distance设为-INF。
否则第V次遍历后如果没有距离更新,那么求得的distance即为最短距离。
负权环的存在会导致通过它无限次可获得更短距离,所以距离设为-INF表示不可达。
初始化距离数组distance,将源节点distance设为0,其他都设为INF
对每条边进行V-1次松弛(relax)操作:
对每条边(u,v),如果distance[u]+w(u,v)<distance[v],则更新distance[v]=distance[u]+w(u,v)
第V次遍历如果仍有距离更新,则存在负权环,返回true并设distance数组中相关节点distance为-INF
若第V次没有距离更新,说明已经求得最短距离,则返回false
时间复杂度为O(VE),空间复杂度为O(V)
迪克斯特拉算法是一种计算单源最短路径的算法。算法从源点出发,逐步向外扩展,找到到每个节点的最短路径。
从源节点开始,给所有节点标记距离为无穷大,只有源节点标记距离为0。
选择距离最小的未处理节点,作为下一个处理节点。
更新以该节点为中间节点的邻边距离值:
标记该节点已处理。
重复执行2-4步,直到所有节点都标记为已处理为止。
如果图中存在负权边,算法结果会出错。比如节点G到C边原权重为0,现在改为-6。之前计算G的距离为12,通过-6权重边,可以得到更短距离6。此时原有算法结果无效。
给出一个具体图,按照迪克斯特拉算法,逐步计算从源点S出发,到每个节点的最短距离。
首先标记除S外节点距离为无穷大,S距离为0。然后依次处理与S相邻的A和C节点,更新它们的距离。之后按距离从小到大顺序处理节点,并更新相邻节点距离,直到所有节点都处理完毕。
最后得到从S到每个节点的最短距离,验证算法正确性。
Dijkstra算法是解决图中单源最短路径问题的一种算法。它可以在无负权边的有向或无向网格中找到源节点到其余所有节点的最短路径。
Dijkstra算法的思想是:从源节点开始,逐步扩大一个「球面」,包含更多的节点。它保持一个「前沿」,包含的所有节点距离源节点的距离都是确定的。然后重复选择前沿中的节点,更新其相邻节点的距离值,把新的节点加入前沿。
将源节点s距离设为0,其余所有节点距离设为正无穷大。
将源节点s加入到优先队列中,优先根据距离顺序。
取队列首节点u,计算u到其相邻未在队列中的节点v的距离,并与当前v距离比较,如果比当前值小,更新v距离值。如果距离改变,把节点v加入队列。
重复步骤3,直到优先队列为空,则算法结束。此时每个节点的距离值即为源节点到该节点的最短距离。
如果图中边数为E,节点数为V,使用Fibonacci堆等优先队列实现,Dijkstra算法的时间复杂度为O(ElogV)。
只有非负权值情况下,算法能正确计算单源最短路径。如果图中存在负权环,算法会得到错误结果。
动态规划是一个解决问题的思路,它可以应用于许多可以递归定义的问题。
许多问题可以通过把大问题分解成小子问题来递归定义。但是如果子问题需要重复计算,那么效率就很低。动态规划的思想就是记录已经计算过的子问题结果,避免重复计算。
动态规划问题通常需要以下步骤:
将原问题分解成互不重叠的子问题
找出子问题之间的关系式,这样子问题的解就可以根据这个关系式推导出来
将子问题按照从简单到复杂的顺序排列,这就形成了一个有向无环图(DAG)
从简单问题开始,按照DAG中的顺序依次解决每个子问题一次。在解决每个子问题时,都利用已经解决的子问题的结果
收集和输出原问题的解
斐波那契数列可以这样定义:F(0)=0, F(1)=1, F(N)=F(N-1)+F(N-2)。
这个问题可以看成是一棵递归树。对于F(N)这个问题,它需要调用F(N-1)和F(N-2)两个子问题。如果直接递归计算,将产生很多重复计算。
动态规划的思想是:在计算F(N)的时候,记录下F(N-1)和F(N-2)的结果,这样以后如果再有需要这两个子问题的结果,就直接返回记录而不必重新计算。至此就避免了重复计算。
将子问题按从小到大排列后,就可以从最简单的子问题开始顺序计算所有子问题,得到原问题F(N)的结果。
将原问题分解成子问题
找出子问题间的关系式
按照顺序给子问题编号,形成DAG图
建立存储子问题结果的数组或表
根据关系式顺序计算每个子问题一次
处理好边界条件和Base案
收集和返回原问题的结果
将这些步骤统筹起来,就可以成功解决一个动态规划问题。
APSP问题的输入是带权重的有向图G=(V,E),其中V表示顶点集,E表示边集,边上的权重可以是整数。输出是所有顶点对(u,v)之间的最短路径长度。
如果图中存在负环,则某些最短路径长度可能是负无穷大。我们在本课中不考虑这种情况,即图中的所有路径长度都有限。
直接用单源最短路径算法(如贝尔曼-福特算法)从每个顶点出发来解决这个问题,时间复杂度会达到O(V^3)。这只能在稠密图上的特定结构上有更好的算法。
我们可以通过改变图中的边权值,使之都为非负数,同时保持最短路径不变。具体做法是:
找到图中任意一条最短路径长度最小的简单路径,记其路径长度为L。
将所有边权值加上-L,则所有边权值都变为非负数。
由于加入了一个常数,-L,所有最短路径都保持不变。
此时问题转化为带非负权值图的单源最短路径问题,可以用更好的算法如德克斯特拉算法解决。时间复杂度降低到O(V^2logV+VE)。
具体实现上述思路的算法就是Johnson算法:
为每个顶点v增加一个新的超级源点s。
将s向v连边,权值设为0。构成新图G’。
对G’执行贝尔曼-福特算法,找到各点到s的最短路径并保存在长度数组dist[]中。
改变原图G中的边权值:对于每条边(u,v),将其权值增加dist[u]-dist[v]。
在权值修改后的G图上,从每个点出发执行单源最短路径算法,即完成APSP问题。
Johnson算法的时间复杂度为O(V^2logV+VE)。它通过改变边权值,将负权问题转化为非负权问题,得到更好的时间效率。
本次考试的作答范围包括图论知识点。其中:
Quiz 1 的知识点也可考,但不强调。主要内容为用图存储结构实现时间效率。
重点考查过去6堂关于图算法的课程。其中2堂介绍了无权图算法,4堂介绍了有权图算法。这与问题集5-6对应。
本学期考查的问题集数量比以往少。主要考查问题集5-6的知识点。
图算法常用于解决多种不同问题。本次考试可能考察的主要问题包括:单源最短路径、全图感染、有向无环图拓扑排序等。
依次从简单到通用:
无权图用BFS求解,线性时间。
有向无环图用拓扑排序后向放松边求
反复算法设计范式包括6个关键步骤:
定义子问题。一个问题可以划分为许多小子问题。
子问题之间的依赖关系。定义如何通过解决小子问题来解决较大的子问题。
拓扑顺序。确保子问题之间的依赖形成一个有向无环图(DAG)。
基本情况。当问题规模足够小时,直接解决基本情况。
原问题。我们最终要解决的问题。
运行时间分析。
原问题:排序数组A中的所有元素
子问题:对A中索引从i到j的子数组进行排序,定义为S(i,j)
拓扑顺序:按子数组长度从小到大排序子问题
基本情况:空数组已经排序
依赖关系:S(i,j)=Merge(S(i,m),S(m,j)) ,其中m为中间索引
时间复杂度:O(nlogn)
原问题:计算第n个斐波那契数
子问题:计算从1到n所有斐波那契数Fi
基本情况:F1=F2=1
依赖关系:Fi=Fi-1+Fi-2
拓扑顺序:从1到n顺序计算每个子问题
运行时间:O(2^n) ,使用记忆化搜索后时间改为O(n)
子问题之间可以看作一个有向图。其中的关键术语:
顶点:每个子问题。
边:子问题之间的依赖关系。
拓扑顺序:符合DAG边依赖关系的问题解决顺序。
有向无环图(DAG):子问题依赖关系可以形成的图形。
给出两个字符串序列A和B,找出一个最大长度的子序列L,其为A和B的子序列。
子序列不同于子串,子序列可以在字符串中选择任意元素,之间可以跳过元素。
LCS问题中,每个子问题描述为L(i,j),表示A的后缀从i开始,B的后缀从j开始的最长公共子序列长度。
子问题之间的关系为:
如果A[i] != B[j],L(i,j)取L(i+1,j)和L(i,j+1)中的最大值
如果A[i] == B[j],L(i,j) = L(i+1,j+1) + 1
子问题空间为所有(i,j)组合,i从1至A长度,j从1至B长度。初始化边界条件L(i,0)=L(0,j)=0。
根据递归关系计算每个子问题解,时间复杂度O(mn)。
给一个数列,找其最长子序列中的元素按顺序递增。
LIS问题中,每个子问题描述为L(i),表示以第i个元素结尾的最长递增子序列长度。
子问题之间的关系为:
如果num[i]大于之前所有LIS结尾元素,L(i)=max{L(j)}+1
否则 L(i)=max{L(j)}
其中j<i且num[j]<num[i]
子问题空间为所有位置i,初始化L(0)=1。根据递归关系计算每个子问题解,时间复杂度O(n^2)。
给定两个玩家轮流取1-3枚代币,规则使游戏变成最后留下更多代币的一方获胜。求先手是否有必胜策略。
定义子问题P(i,j)为当前可能代币数为i时,另一方可能代币数为j时先手是否有必胜策略。
子问题关系为:
如果i<j,则P(i,j)=True
否则,考虑每种取法后情况,P(i,j)=OR(NOT P(i-x,j+y))
其中x为当前取的代币数,y为对手应对移动。
根据子问题关系计算每个子问题解来判断先手是否有必胜策略。
有个窃贼需要钱,偷来了 n 件完全相同的硬币。这些硬币上有认识标记,不能直接用来兑换。所以需要把硬币重新熔化为其他物品。
窃贼找到一个买手,买手对不同物品有不同的purchasing price(购买价格)。每个物品都有:
窃贼的目标是用有限的n枚硬币,兑换尽可能高的总价格。
用i枚硬币,只考虑前j个物品能获得的最大价格为x(i,j)
不制作第j个物品,那么答案就是用i枚硬币考虑前j-1个物品能获得的最大价格x(i,j-1)
制作第j个物品,价格为Pj,但需要消耗Kj枚硬币。
那么答案为:Pj + x(i - Kj, j-1)(当i大于等于Kj时)
边界条件:i=0时,x(i,j)=0
依次计算从x(i,1)到x(n,m)即为答案
时间复杂度O(nm),空间复杂度O(nm)
上次讲解了有向无环图(DAG)中的单源最短路径算法。这次我们来重点讲解包含负权环的任意图中的单源最短路径问题,即Bellman-Ford算法。
Bellman-Ford算法定义了一个子问题Δ_k(s,v),即从源点s到节点v的最短路径长度,且路径中边数不超过k。它将原问题划分为从k=0到k=V-1的子问题。
关系式如下:
| Δ_k(s,v)=min{Δ_{k-1}(s,u)+w(u,v) | 存在边(u,v)} |
这里添加了k和k-1的限制,因为如果已经判断最后一条边(u,v),那么从s到u的路径长度应该小于等于k-1。
如果路径使用了较少的边,也考虑不跟最后一条边,取Δ_{k-1}(s,v)作为候选值。
通过在每个迭代中更新所有子问题,可以在O(VE)时间内求解出原问题。使用Δ_V(s,v)判断是否存在负权重环。
考虑求解无权图中任意两点之间的最短路径长度。
定义子问题δ(u,v),即节点u到v的最短路径长度。
关系式如下:
| δ(u,v)=min{δ(w,v) | 存在边(u,w)} |
针对每对节点(u,v),从其 neighborhoods中尝试各节点作为中间点,取最小值。
时间复杂度为O(V^3)。
给出一个算术表达式string,求其最优的括号拼写方式。
定义子问题C(i,j),表示从i到j的最优括号匹配方案。
关系式如下:
如果i=j,C(i,j)=0
| 否则,C(i,j)=min{C(i,k)+C(k+1,j)+意义成本 | 所有k} |
其中意义成本表示括号内表达式的计算顺序。
通过尝试所有可能的k来拆分问题,找出最小成本解。时间复杂度O(N^3)。
为一段乐曲定义最优的指法方案。
定义子问题F(i),表示从开头到第i个音符的最优指法成本。
关系式如下:
F(1)=基本指法成本
| F(i)=min{F(j-1)+从j指法到i指法的变换成本 | 所有j<i} |
其中变换成本根据手指间的移动距离来衡量。
通过尝试所有可能的j来分割问题,在O(N^2)时间内找出全局最优解。
以上问题都通过添加子问题的限定条件,来将原问题分解成更小的子问题,这就是动态规划的一个重要思想。
栅栏割裂问题是这样一个问题:给定一个长度为L的栅栏,以及每一段长度l的价值V(l),要求将这个栅栏切割成不同长度的段,求得的最大总价值。
例如:给定长度为7的栅栏,对应的长度和价值如下:
| 长度 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 价值 | 1 | 5 | 13 | 18 | 21 | 31 | 32 |
直接卖长度为7的栅栏的价值为32,但是我们也可以将其切割为两个长度不同的段来获得更高的价值,如切割为长度为3和4的两段,价值分别为13和18,总价值为13+18=31,高于直接卖。
最优的切割方案是将其切割为两个长度为2的段和一个长度为3的段,对应的价值为5+5+13=33,这就是这个问题的最优解。
子集和问题是这样一个问题:给定一个集合S={x1,x2,…,xn}和一个目标数B,判断是否存在S的一个子集的元素和等于B。
我们之前讨论的时间复杂度主要是多项式时间,但对于含有整数输入的问题,如果算法时间与输入整数的大小成正比,那么这类算法称为伪多项时间。
最后我们回顾之前讨论过的动态规划问题,包括字符串编辑、木材切割、背包问题、最短路径等问题,从新的视角来思考各个问题的子问题定义和关系等。
今天我们将讨论计算复杂度这个领域。
计算复杂度研究问题的难易程度。我们将问题分为多种类:
P类问题:这些问题可以在多项式时间内解决,即问题规模n的多项式时间。
EXP类问题:这些问题可以在指数时间内解决,即2的n次方或更高的时间。
R类问题:这些问题可以在有限时间内解决。R表示递归。
我们知道:
P包含在EXP中,EXP包含在R中。
例子:
N×N国际象棋问题可以在指数时间内解但不能在多项式时间内解,属于EXP但不属于P。
负权环检测问题可以用贝尔曼-福特算法在多项式时间内解,属于P。
然后,我们提出一个不可解的问题 - 是否终止问题。给一个程序,判断它是否会停机。这个问题不属于R类,因为对任何程序都没有算法能给出确定答案。
最后,我们讨论了大多数决定问题都不可解。决定问题答案只有是或否。我们 counts 所有的程序仅仅是一组有限长度的二进制串,而所有决定问题对应的算法数量远远大于程序数量,所以绝大多数决定问题没有相应的算法可以解决它。
这个视频介绍了计算复杂度的基本概念和一些重要问题,为后续学习奠定基础。
递归框架可以用来解决任何递归算法问题。它分为以下步骤:
定义子问题。使用变量来表示每个子问题,例如用x表示。
递归关系。用数学表达式表示子问题与其他子问题的关系。
边界条件。能直接得到解决的子问题。
原问题解法。可能需要结合多个子问题的解来解决原问题。
时间分析。分析算法的时间复杂度。
子问题应清楚定义其含义。用词语描述子问题的输入参数、输出结果如何依赖于这些参数。
常见的子问题包括:
对于序列,取其前缀或后缀作为子问题。
可以扩展子问题状态,记录辅助信息,如求最大值时记录当前最大值。
多个输入时,取每个输入对应的索引表示子问题。
用数学表达式表示子问题与其他子问题的关系,比如最大值/最小值/求和等。
能直接得到解的子问题,如长度为1的序列。
可能需要结合子问题解来解决原问题。
分析时间复杂度,判断算法是否高效。
前缀和后缀实际表示同一个动态规划,只是方向不同。
bottom-up计算从最后一个子问题开始。
这节课主要回顾了整个课程的内容和目的。
首先,课程一开始设定的三大目标是:
解决计算问题。通过学习算法来解决计算问题。
证明正确性。证明算法的输出永远都能给出正确答案。这需要使用递归和归纳法。
论证效率。使用了计算模型来判断算法效率好坏。优良算法应是输入规模随着增加,算法时间增长较慢。
此外,还有一个非常重要的目标是:
接着回顾了各个主要章节的内容:
介绍了复杂度理论基本概念,如P、NP、NP完全等。说明大多计算问题都可以用平方时间或指数时间解决。
介绍了递归及归纳的应用。这些技术用于证明算法正确性。
推荐了一些后续课程,如数理逻辑等深入研究相关主题。
最后强调了计算机科学是团队协作的学科。好的沟通能力对解决问题也很重要。
计算机折纸研究如何通过算法将3D物体折叠到2D折纸图样上。常见问题有:
给定目标形状,求出能折叠该形状的折纸图样(设计问题)。
给定折纸图样,判断它是否能折叠成某个形状(可折叠性问题)。
设计问题相对简单,利用算法如Orgamizer就可以解决。可折叠性问题则较难,证明属于NP难问题。
主要研究方向包括:
求取效率高、损失材料少的折叠算法。
理解哪些形状更易被简单折纸包裹。
引入弯曲折痕研究折纸数学。
折纸机器人 automated folding。
将任意多边形折叠到方形纸上的算法证明。
Orgamiizer算法可以将3D模型转化为单张纸的折纸图样。
迷宫折叠算法可将任意大小迷宫折叠成实体迷宫结构。
圆形交替山谷折痕可以折叠成“薯片”状几何形状。
父子合作的雕塑折纸作品引入弯曲折痕。
6.849课程会讨论更多折叠算法与应用。