https://www.youtube.com/playlist?list=PLRdD1c6QbAqJn0606RlOR6T3yUqFWKwmX
这节课是关于算法开发在线课程的简介。讲师Bob Sedgewick和Kevin Wayne将于普林斯顿大学一起开设这门课程。
该课程是一个关于算法的中级调查课程。它将专注于算法和数据结构在真实应用中的编程和问题解决。算法是解决问题的方法,数据结构存储与问题有关的信息。
第一部分包括数据类型、排序和搜索。它将考虑堆栈、队列、包和优先级队列等基本数据结构和算法。然后将考虑快速排序、归并排序、堆排序和基数排序等经典排序算法。还将考虑二叉搜索树、红黑树和哈希表等经典搜索方法。
第二部分将涉及更高级的算法,包括图算法、字符串处理算法(正则表达式、数据压缩)以及使用基本算法的高级算法。
学习算法的主要原因是能够解决以前无法解决的问题。例如,网络连接问题需要高效算法才能找到所有节点之间是否存在路径。学习算法也可以带来思想上的刺激,算法可以揭示生命和宇宙的奥秘。掌握好的算法和数据结构对成为一名熟练程序员也很重要。
本课程提供书籍和在线学习资源。书和论文网站提供讲义、代码、练习题等更丰富的内容。 prerequisites 是掌握 Java 语言基础,包括循环、数组、函数等知识。
这节课介绍了联合查找问题。联合查找算法可以高效支持将不同对象连接在一起,并查询两个对象是否连接在一起的操作。
首先,需要建立问题模型。这里对象用0到N-1的整数表示,可以进行“连接对象i和对象j”的联合操作,以及“对象i和对象j是否连接”的查找操作。
然后介绍两个典型的联合查找算法:快速查找和快速联合。快速查找算法支持每次操作的常数时间复杂度,但占用空间较大。快速联合算法空间复杂度低,但联合操作时间复杂度高。
将对象通过连接关系划分成若干个连通成分。连通成分中的任何两个对象都相互连接,且不与其他连通成分中的对象连接。这可以有效提高算法效率。
最后介绍实现联合查找问题的数据类型:定义一个UF类,包含构造函数和connected、union两个方法。构造函数输入对象个数N,以初始化数据结构。客户端程序可以使用UF来处理从标准输入读入的联合和查询操作。
联合查找问题广泛应用在计算机网络、社交网络、集成电路等多种领域。开发高效算法可以支持海量对象和操作数量级的系统。
这段视频介绍了快速查找算法在解决动态连通性问题时的第一个实现。
快速查找算法是一种“热切”算法,能够高效支持将不同对象连接起来并查询两个对象是否连接的操作。
它使用一个整数数组来存储数据结构,数组的下标为对象编号。两个对象P和Q连接如果且仅如果它们在数组中的条目值相同。
视频通过一个具体例子展示了快速查找算法在不同连通操作下是如何工作的。起初每个对象对应数组中的条目值都等于其下标,表示对象独立。
联通操作会将第一个对象对应的所有条目值改为第二个对象对应的条目值,这样就将两个对象连通了。找到操作仅需要检查两个对象在数组中的条目值是否相同。
然后给出了实现快速查找算法的Java代码。主要包含构造函数初始化数组,以及找到和联通两个对象的方法。
最后分析快速查找算法的时间复杂度。构造函数和联通操作都需要遍历整个数组,时间复杂度为O(N)。但如果有N次联通操作,则总时间复杂度为O(N^2),这对大规模问题来说时间效率并不高。
快速联合算法是一种更高效的动态连通算法。它使用与快速查找相同的数据结构-一个整型数组来存储对象的标识。
不同的是,数组中的每个元素不再直接代表对象,而代表一棵树。元素的值表示指向该树根节点的父节点。每个对象起初都视为一棵包含自身的单节点树。
找操作通过计算两个元素的根节点来判断是否连通。联合操作仅需要将第一个元素的根节点指向第二个元素的根节点,就实现了两棵树的合并。
实现中,构造函数初始化每个元素指向自身,找到操作计算元素根节点再比较。联合操作直接修改第一个元素的根节点指针。
这比快速查找更高效,因为找操作需要跟踪到根,联合只改动一次数组。
但如果树过高,找到的代价将增强线性级。长期下来,部分树可能会非常长,影响效率。
以上介绍了快速联合算法的基本思路和实现。它比快速查找更高效,但树的高度问题也会影响算法效率,需进一步优化。
本节视频介绍了使用加权路径压缩来解决联合查找问题的Java 实现。
与之前介绍的加权联合算法相同,使用一个整型数组存储对象标识,另一个整型数组存储每个对象树的大小。
find操作实现与快速查找相同,即比较两个对象的根节点标识是否相同。
union操作首先比较两个对象树的大小,将较小树的根节点指向较大树,然后更新大小数组。
具体实现是,如果将对象i的根节点指向j,则将j树的大小加上i树原有大小;反之亦然。
算法的时间复杂度为O(logN),因为任何对象到根节点的深度最多为logN。
发现路径压缩的思想后,在find操作中可以将访问路径上的所有节点直接指向根节点。实际上使用一个变种算法,每次将节点指向其祖父节点。
这样实质上能保持树的更平坦,但实现起来更简单。这种优化大幅提高算法性能。
这些算法是通过不断改进设计而来,理论分析也非常深入。它们可以高效解决以前无法解决的海量规模问题。
这段视频主要介绍了使用联合查找算法解决连通性问题的另一个应用——森林火灾模型。
森林火灾模型中,每个方格表示森林中的一个区域。每个区域有可能“着火”,也有可能“未着火”。
“着火”的区域用白色表示,“未着火”的区域用黑色表示。两个区域相邻且都着火,就会产生“火势蔓延”。
要求检查整个森林是否会完全烧毁。也就是检查是否存在一条路径,可以从任意一个着火区域通往整个森林中的任意区域。
与之前的渗透问题类似,也可以建立对象,每个对象对应一个区域。然后根据区域是否着火,使用union和find操作进行连接和查询。
这样一来,解决森林火灾问题就变成了一个典型的动态连通性问题,我们可以直接利用之前实现的联合查找算法进行检测。
这类物理模拟问题归纳总结出来的数学模型和算法,对许多其他应用都很重要。它体现了算法设计的科学方法:通过抽象建立模型,再应用于具体问题。
森林火灾问题是联合查找算法又一个具体应用。利用算法,可以在计算机上快速、高效地模拟并解决这个真实世界中的问题。
这段视频介绍了如何观察和描述算法运行时间的方法。
首先,需要做实验来观察每个问题规模下算法的运行时间。需要多次重复运行并取平均值,以减少随机因素的影响。
然后,需要找出规律并进行建模。可以画出曲线来查看随问题规模的变化趋势,例如线性增长或对数增长。
一般来说,随问题规模N的增加,运行时间T的增长类型有:
这些增长类型直接反映了算法效率。O(1)最高效,O(N)次之,O(N2)比O(N)低一个数量级。
除运行时间外,也需要观察算法的空间复杂度,即随问题规模而增长的内存使用量。
最后,通过重复实验观察,让观测结果与建立的模型吻合,从而验证并确定算法的时间/空间复杂度。这是运用科学方法来研究算法性能的基本流程。
理解算法复杂度对选择高效算法、预测性能非常重要。它也有利于后续理论研究比如P、NP问题。
这段视频主要介绍了分析算法运行时间的方法。
首先,可以对程序运行多次,对不同规模的输入数据进行测试,并记录每次运行所需的时间。这样就可以得到不同规模问题对应的运行时间数据。
然后,可以将问题规模和运行时间画出折线图。很多问题的运行时间随问题规模的增加呈指数级增长,此时如果将坐标轴取对数尺度,曲线通常会近似为一条直线。
通过直线回归分析,可以求得曲线的斜率B。若回归直线斜率为B,则运行时间T与问题规模N的关系为T∝N^B。
此外,还可以通过不断扩大输入规模,来快速估计指数B。每次扩大一倍输入,运行时间比值会收敛于一个常数,其对数即为指数B。
最后,运行时间随机器配置也会有差异。但算法复杂度与问题规模的函数关系是独立的。只有问题规模才决定运行时间增长速度。
通过实验探索算法的时间复杂度,可以有效预测更大规模问题的运行消耗,并针对性优化算法。这是分析算法性能的基本方法。
这段视频主要介绍了如何使用数学模型来分析算法的运行时间。
首先,通过实验获取不同规模输入的数据集上的运行时间,并绘制出时间曲线。然后使用回归分析求取曲线的斜率,作为问题规模N和运行时间T之间的函数关系。
其次,需要分析算法中各种基本操作的执行次数频率,如数组访问或字符串连接等。这里采用替换求和为求积分的方法,将离散求和近似表示为连续求积分,从而简化计算。
还可以使用渗透符号忽略低阶项的影响。例如1/2N^2渗透N^2,表明随N较大时低阶项对总体效果影响不大。
然后,根据基本操作的成本和频率的乘积来选择一个代理操作。假设运行时间成正比于该操作的频率。
最后给出几种常见算法的时间复杂度近似模型。例如1维数组内和问题Θ(N),二维Θ(N^2),三维Θ(N^3)等。
视频还提到,完整精确的数学模型计算较复杂。approximater模型已能很好描述算法运行时间。这为后续学习和分析算法性能提供了方法论支持。
该视频主要介绍了算法复杂度分类和最常见算法时间复杂度的数学分析方法。
首先,算法的运行时间随问题规模的增加,可以按照不同的函数关系进行分类。包括O(1)、O(logN)、O(N)、O(NlogN)、O(N^2)、O(N^3)等。这决定了算法的效率。
然后,通过对二分搜索算法的数学分析说明了如何建立算法运行时间的数学模型。给出二分搜索在最坏情况下比较次数的递归公式,并应用递推法解出结果为O(logN)。
视频还给出了排序算法的一个常见应用-三数之和问题的改进算法。此算法首先对输入数组进行排序,然后对每个数对进行二分搜索,找出和为0的三元组。通过分析,此算法的时间复杂度为O(N^2logN),远优于原来O(N^3)的算法。
最后,视频强调通过实际测试可以验证更好时间复杂度的算法是否真的更快。验证了对三数之和问题,新算法能处理问题规模远大于原算法。
总之,该视频系统讲解了算法分类标准、建立数学模型的方法,并给出一个将基本操作结合起来并通过分析优化算法的具体例子。
这段视频主要阐述了算法复杂度分析的一些细节问题。
首先回顾了从最坏情况、平均情况到随机输入三种不同情况下的算法运行时间分析方法。
然后强调实际问题的输入往往不是最坏情况,应根据具体问题特征分析输入模型,找到效率高的算法。
视频还指出,仅使用渐函数级别的Θ(f(n))级别分类,不能精确预测运行时间。需要给出具体常数项或运行次数,才能更好比较不同算法。
以1维、2维、3维数组内和问题为例,给出不同维度下算法时间复杂度的更精细表达,其中隐含了常数项的影响。
视频最后说明,理论算法研究最重要的目标是找出问题的上下界,以确定难易程度。但在实际应用中,我们应该根据输入特点研发高效算法。
总之,这段视频强调了算法分析应考虑问题输入模型的影响,给出更精细的运行时间描述formula,以及理论研究与实际应用的区别。
它补充说明了算法学习的一些重要细节,帮助我们更好理解和运用算法分析方法。
这段视频主要介绍了程序内存使用量的分析方法。
首先回顾了基本的数据类型如布尔值、字符、整数等在内存中的占用大小。其中布尔值虽然仅有 true/false 两个值,但实际占用一个字节。
然后分析了数组的内存使用。一维数组需要 24 字节开销加上每个元素的大小。两个整数的二维数组大致为 8MN 字节。
对于对象来说,需要考虑对象头开销 16 字节、实例变量大小、内部类引用以及填充导致对齐到 8 的倍数。
以日期对象为例,三个整数实例变量加上开销和填充共占 32 字节。字符串包含字符数组指针和附加信息,约为 2N+64 字节。
视频给出了内存分析的一般步骤:识别数据结构、统计各元素大小、考虑填充与对齐问题。
以链接表示法为例,分析了其中两个整数数组及开销仅为 8N+88 字节。
最后强调可以通过实验与理论分析两种方式得到算法内存复杂度,而理论模型需要通过实验验证。这提供了一整套计算机科学研究算法的方法论。
总之,该视频系统地介绍了如何根据数据类型和结构进行内存使用率分析,给出了一个实际示例,并阐述了算法学习研究的常见流程。
这段视频主要介绍了数组动态增长实现栈的数据结构。
起初,我们使用定长数组实现栈时,需要提前告知最大容量。为解决这个问题,可以使用动态增长数组。
当插入新元素时,若数组满了,我们就创建大小为原数组两倍的新数组,将元素拷贝过去。这样插入n个元素只需O(n)的时间复杂度。
在删除元素时,如果数组仅剩原容量四分之一时,就缩减数组大小为一半。这可以防止频繁调整数组大小引起的“抖动”效应。
通过推断元素插入和删除次数,可以证明平均每个操作的时间复杂度为O(1)。
此外,我们保证数组利用率在25%至100%之间。每次调整数组大小前,我们都已经通过前置操作“支付”了这一操作。这就是“分摊”分析的思想。
此数据结构实现了动态增长的栈接口,客户端无需预先指定最大容量。同时,内存使用率是元素数量的常数倍。
与链式存储相比,数组实现更高效但无法提供每次操作 Worst Case 的时间保证。这两种方式各有利弊,客户端可以根据实际需求灵活选择。
总之,这一实现巧妙利用了分配分析,很好地解决了动态数组应用中的核心问题。
这段视频介绍了使用链表和数组实现队列的数据结构。
队列的操作与栈类似,插入用“NQ”,删除用“DQ”。它遵循“先进先出”原则。
使用链表实现队列时,需要维护队首和队尾的指针。插入新元素时,添加到队尾;删除时,从队首移除元素。
具体来说,DQ时与弹出栈一样,保存被删除节点并移动队首。NQ时首先定位当前队尾,然后添加新节点连接在其后,更新队尾指针。
使用数组实现队列时,同样需要记录队首和队尾位置的指针。插入时在队尾添加,删除时在队首删除元素。遇到容量限制需要重设指针。
实现队列时需要考虑empty状态下的操作。无论使用什么底层结构,实现queue的API与stack类似。
视频还提到数组实现需要处理循环问题,为难度较大的课后练习。总体来说,通过指针移动和索引计算即可实现队列这个基本的数据结构。
本视频主要讨论了利用泛型技术实现数据结构支持多种数据类型的问题。
首先介绍了不使用泛型直接为每种数据类型实现独立的栈类,这将产生大量重复代码,效率低下。
然后提出使用对象类型实现通用栈类,通过类型转化让客户端使用。但这会增加类型检查错误发生在运行时的风险。
视频进而介绍了使用泛型定义类型参数的方法。这样不同类型的栈在编译时就可以检查类型安全性,避免运行时错误。
然而,直接使用泛型定义数组会触发编译错误。为解决这个问题,视频给出了使用对象数组并执行强制类型转换的实现方法。此处需要注意警告信息。
最后分析了如何使用包装类处理基本数据类型,以及泛型实现可以很好支持任何数据类型的架构。
总之,该视频通过一个栈数据结构的例子,系统介绍了泛型技术解决多类型支持问题的原理及细节实现问题,给出了一个类型安全且高效的通用解决方案。
本视频介绍了Java提供的迭代(Iteration)机制,让数据结构支持简洁优雅的客户端代码进行集合迭代。
为实现迭代,需要集合类实现Iterable接口,其中iterator()方法返回相应的Iterator接口实例。Iterator进一步实现hasNext()和next()方法。
对于链表,迭代器类维护current指针迭代元素。对于数组,迭代器直接通过索引迭代元素。
迭代器负责确定何时结束迭代(hasNext返回false)以及获取下一个元素(next方法)。
通过实现迭代接口,可以支持Java中的for-each语法进行简洁迭代,避免非必要的数据结构操作。
此外,视频提到 Bag数据结构,其特点是无需考虑元素顺序,只提供添加(add)和迭代两类操作。其实现可以直接基于Stack或Queue数据结构。
总之,迭代机制解耦了数据结构的内部表示和客户端迭代代码,大大提高了客户端程序的简洁性和可读性。
视频介绍了一些基本的数据结构和实现,比如数组、链表等。这些数据结构看起来很基础简单,但是可以应用于一些非常复杂的应用场景。
Java提供了集合框架,包含链表、队列等常用数据结构。但是框架中的API设计过于宽泛,包含了太多操作,性能特征无法明确,可能导致性能损失。因此本课程建议学生自己实现这些基础数据结构,至少能了解其性能特征。
视频给出了二叉堆栈算法用于计算算术表达式。该算法利用两个栈分别存储运算数和运算符,从左到右扫描表达式。遇到运算数入值栈,运算符入运算符栈;遇到右括号则从两个栈顶取出运算数和运算符进行运算,结果再入值栈。整个过程利用栈模拟递归,计算任意复杂的算术表达式。
本节视频总结介绍了一些常用的数据结构,强调了自定义实现的重要性。并给出二叉堆栈算法详细案例,说明如何利用栈实现递归计算任意算术表达式,为后续学习编译原理奠定基础。
视频首先介绍了常见的排序问题:需要对一组记录根据关键字段进行排列。记录包含多个字段,但我们只关注关键字段(即键)进行排序。
视频提出如何实现一个通用的排序算法,使它可用于处理不同类型的数据。问题的答案是使用回调机制。客户端通过传入一个实现了Comparable接口的数组,实现比较物件。排序算法内部调用compareTo方法完成实际比较。
Java语言内置Comparable接口,要求实现该接口的类必须定义compareTo方法。许多核心类型如数字、字符串等均实现了这个接口。如果我们定义自己的类,也需要实现Comparable接口规定的比较规则。
为了退出排序算法的通用性,视频提出使用两个静态方法less和exchange来替代直接访问数组,实现了数据的封装。less方法做比较,exchange方法做交换。这样 sorting 算法即可与数据的具体类型解耦。
通过回调机制和封装比较交换操作,实现了一个通用的排序算法框架。它可以处理任何实现Comparable的对象,达到数据类型的最大独立性。这为不同语言实现
选择排序是一种简单直观的排序算法。其基本思想是每轮从待排序的数据元素中找到最小(或最大)的一个元素,存放在序列的起始位置。
从未排序数据元素中找到最小(或最大)元素,存放在序列起始位置;
除第一个位置外,其余位置依次与第二个位置先进速进行比较,将最小(或最大)元素移动到第一位置。如此循环,直到全部元素排完。
使用一个指针I遍历整个数组,寻找I后面最小的元素,并与其交换位置。交换后右边部分保持顺序不变。每次交换完成后I右移一位,继续执行同样操作。
选择排序每轮需要遍历整个数组找到最大(或最小)元素,时间复杂度为O(n^2)。比较次数为n(n-1)/2次,交换次数为n次。
选择排序的实现简单,但效率较低。不论输入数据的性质如何,其时间复杂度都是O(n^2)。如果输入数据基本有序,选择排序表现不佳。
选择排序是一种简单直观的排序算法,时间复杂度为O(n^2),但实现简单,容易理解。如果数据量很小,选择排序可以进行考虑。但一般不推荐用于大规模排序。
插入排序是一种简单直观的排序算法。其基本思想是以构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
从数组的第二个元素开始,将该元素首先与前一个元素进行比较,如果当前元素小于前一个元素,则将该元素移到前一个元素的后面。
如果当前元素大于前一个元素,则与前前一个元素进行比较。继续向前比较,直到找到合适位置插入该元素。
重复第一步和第二步操作,直到所有元素排完序。
平均时间复杂度O(n^2),最好情况下(数据已排序)时间复杂度O(n),最坏情况下(数据翻转排序)时间复杂度也是O(n^2)。空间复杂度O(1)。
时间效率比选择排序高,在数据基本有序的情况下,效率比其他Ο(n2)时间复杂度的排序算法要更好。
如果数据中心化程度高或随机性不强,比如客户表或员工表,往往都很适合使用插入排序。也适用于小规模排序。
插入排序时间复杂度低于选择排序,但依赖数据的初始顺序,效率比选择排序高。适用于数据量小或近似有序的场景。
Shell 排序是一种插入排序的增强版。它通过把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分解为一组,算法便终止。
按初始增量h将记录分组,对每组使用直接插入排序算法排序;
带增量h/2重复第一步,对每组进行直接插入排序;
依此类推,直到增量减至1,即整个文件作为一个组进行直接插入排序便可完成排序工作。
Shell 排序的时间复杂度取决于增量序列选择。如采用Knuth提出的3x+1增量序列,其时间复杂度为O(n^1.5)。但实际排序速度还取决于输入的数据特征。
借助于直接插入排序的特点,用不同增量h对数组进行h插入排序,即跳过h个位置进行比较和交换,完成组内排序工作。然后以h/2作为新增量重复此过程,直到h=1时完成整体排序。
算法简单,效率高于直接插入排序。随着增量的减小,数组越来越趋于有序,后面排序工作越来越快。适用于大量数据快速排序。
选择好的增量序列对算法效率影响很大,但目前还未找到最优增量序列。理论时间复杂度分析也较难,尚不能给出精确模型。
洗牌是随机重新排列一副牌的顺序。可以使用排序算法来实现洗牌。
为每张牌生成一个随机数作为关键字
按随机数进行排序
排序完成后牌则随机重新排列,保证洗牌均匀
从左至右遍历每张牌
对于每张牌,随机选择在其左面的牌进行交换
遍历完全程,牌顺序即完成随机洗牌
方法一时间复杂度为排序算法的时间复杂度,额外需要随机数生成。
方法二时间复杂度O(n),只需要一次遍历,每步交换一次,实现在线洗牌。
随机数范围必须为0到当前索引之间
随机种子不宜过少,否则难保随机性
不要直接使用系统时间作为随机种子
对于业务需要,应选择安全可靠的随机数算法实现洗牌
正确实现洗牌算法能有效保证游戏公平性。
凸包是指包含所有给定点的最小凸多边形。
机器人路径规划:计算在有障碍物的场地内由源点到目标点的最短路径
点集间距计算:找出点集内两点间最大距离,这对统计计算很重要
Graham扫描算法是计算凸包的一种算法,它基于以下两个性质:
可以只做逆时针转弯就可以遍历凸包
以Y坐标最小的点为基点,以极坐标角度顺序排列其他点
寻找Y坐标最小的点P
按P的极坐标角度排序其他所有点
将P和最小角点入栈作为初定hull
依次考察排序后的每个点,计算与栈顶二点和当前点构成的三角形是否逆时针
如果不是,弹出栈顶点,否则继续考察下一个点
全部考察结束后,栈内点即为凸包结果
定义点的顺序关系以进行排序
计算三点是否逆时针需要利用斜率关系判断
效率和排序算法有关,可以用归并排序和快速排序
实现时需要考虑一些临界情况如重合点等
Graham扫描利用好排序算法,实现了高效的凸包计算。
排序算法是计算机科学中一个重要的应用领域,它的目的是对一组项目进行排列,使它们符合某种顺序。
插入排序:每次将一个记录插入到已排好序的子序列中
选择排序:每次从未排序的子序列中选择最小的元素,插入到已排序的子序列中
冒泡排序:通过相邻元素比较交换位置实现升序/降序排序
快速排序:通过分治思想,选择一个基准值,将元素分割为两部分
归并排序:通过分治思想,先将序列均匀分割成不同长度的子序列进行排序,再合并
堆排序:通过构建最大堆实现升序或最小堆实现降序排序
希尔排序:缩小增量的插入排序
插入排序:平均Ο(n2),最坏Ο(n2)
选择排序:Ο(n2)
冒泡排序:Ο(n2)
快速排序:平均Ο(nlogn),最坏Ο(n2)
归并排序:Ο(nlogn)
堆排序:Ο(nlogn)
希尔排序:Ο(nlogn)最坏Ο(n2)
根据问题不同需求,使用时间复杂度低且性能稳定的算法,如归并排序和堆排序。
选择问题是找到一个无序数组中的第k大元素。
使用排序后查找:时间复杂度O(NlogN)
直接遍历:如果k很小,时间复杂度可达O(N)
理论下界:必须遍历所有元素,时间复杂度Ω(N)
1961年,Hoare提出使用快速排序的思想解决选择问题:
对数组进行快速排序式的一次划分
根据划分结果和k,决定在哪个子数组继续操作
递归处理对应的子数组直至找到第k大元素
平均时间复杂度为O(N),因为每次划分可以将问题大小减半。
但最坏情况下为O(N2),难保每次能准确减半。
1973年,一个选择算法给出了线性时间且最坏为O(N)的算法。
但实现复杂,在实践中仍使用平均线性时间的快速选择算法。
选择问题表明,即使简单问题实际上解也很困难,理论研究极为重要。
在实际应用中,数据中会有大量重复键值,这时排序的目的是将具有相同键值的项划分在一起。
传统快速排序在大量重复键时时间复杂度为O(n^2)。这是因为将与分割项相等的项全数放在一侧导致分割后子问题规模没有减少。
三路快速排序通过维护数组的三个范围解决此问题:
将数组分成这三个部分,利用三个指针分别指向三个范围的边界。
使用第一个元素作为分割项,利用三个指针划分数组为三个范围
指针I依次遍历数组,根据元素与分割项的关系移动LT,I,GT指针
移动指针保持三个范围不重叠的不变性
遍历结束时数组自动排序
时间复杂度为O(nlogn),对等值关键字表现优异
排序次数接近理论下限,属于熵最优排序
实现简单高效,使得快速排序成为排序算法中性能最好的选择。
三路快速排序很好解决了快速排序在重复键情况下的问题。
排序算法在许多日常应用中广泛使用,例如音乐播放软件排列歌单、搜索引擎显示结果、浏览器排列 feeds 等。
一些其他不那么明显的场景也使用排序算法,例如找中位数问题一旦数据已排好序就很容易解决;找重复数据也可以通过先排序再检查相邻数据来实现。
Java 提供了 Arrays.sort() 作为通用排序方法。它支持所有数据类型和各种排序规则,通过实现 Comparable 接口或传入 Comparator 对数据进行默认或自定义排序。
对基本数据类型使用两路快速排序,对对象使用两路合并排序。因为对象排序时空间可能不是主要考虑,使用需要辅助空间的合并排序开销可能被接受。
早期 qsort 存在处理重复键数据复杂度为 O(n2) 的问题。后来提出的三路快速排序很好解决了这个问题。但系统排序可能仍存在“杀手输入”,能导致运行时间节外生枝。
排序算法选择需考虑各种属性,如稳定性、并行性、重复键处理、内存访问模式等影响算法效率的因素。不同组合下算法效果不同,无法列举出涵盖所有场景的统一算法。
总结了选择排序、插入排序、希尔排序、归并排序、快速排序等排序算法的时间复杂度、特点及适用场景。Quicksort 在考虑重复键优化后的效率以及通用性使其成为系统排序的主流选择。
优先队列是一种数据结构,可以将元素插入其中,并根据优先级删除元素。
优先级可以通过元素的比较关系决定,代表元素大小的顺序。也可以通过分配优先级数值来表示。
无序数组实现:插入常量时间,但删除最大/获取最大需要Ο(n)时间复杂度
有序数组实现:删除最大/获取最大常量时间,但插入需要Ο(n)时间复杂度
都不适合大数据量的优先队列操作。
使用二叉堆数据结构可以实现插入、删除最大和获取最大元素操作的时间复杂度都为Ο(logn),在理论上近似最优。
它可以很好解决有大量元素插入和删除操作的优先队列问题。
无向图是一种广泛应用于许多领域的模型,它由顶点和连接顶点的边组成。
由于应用场景非常广泛,已知数百种图算法。它们有时极为复杂,但对理解应用至关重要。
无向图是一种灵活且动态的抽象模型。涵盖的应用规模可从小到极为庞大和复杂。
常见问题包括:查找路径、求最短路径、检测回路、遍历每个顶点或边等连接性问题。也有图绘制、最小生成树等问题。
难易程度多种多样:易问题、难问题、未知难易问题。这给图处理带来很大挑战。
设计高效算法来理解庞大复杂图的结构,提供问题解决的见解。这将是后续讨论的重点。
无向图中的顶点通常用0到V-1之间的整数来表示,使用整数可以利用数组来访问顶点。我们可以使用hash表将名称映射到整数。
设计一个图的API接口,主要包含以下方法:
我们使用数组+Bag实现邻接表表示。
设计一些使用API的图算法:
它们都利用了遍历邻接列表的操作。这 fully 体现了API设计用于分离图表示和算法。
实际大规模图中,顶点数量大但每个顶点的度数较小。邻接表表示使时间和空间效率都很好,成为主流表示方法。它可以很好支持图算法需要的遍历邻接顶点操作。
图遍历算法通过对图的每个顶点访问一次来探索图的结构。
DFS使用栈来保存当前未访问的邻接顶点。当访问一个顶点时,首先递归地遍历其所有未访问的邻接顶点,然后回溯至上层顶点。
BFS使用队列来保存当前待探索的顶点。它从起点出发,先访问与起点直接相邻的顶点,然后再访问这些顶点的邻点,依此类推,直到访问图中的每个可达顶点。
使用递归或栈实现DFS,使用队列实现BFS。核心是维护已访问标记visited[]数组,避免重复访问同一顶点。
DFS和BFS针对任意图的时间复杂度均为O(V+E),因为最多 visiting 每个顶点和边一次。但BFS需要额外队列空间O(V)。
图遍历是图算法的基础,可以解决多种连接性问题。DFS使用递归或栈,BFS使用队列实现。它们均以线性时间复杂度遍历任意图。
广度优先搜索(Breadth-First Search,BFS)是一种用队列实现的无向图遍历算法。它用于查找图中所有与起始顶点相连的顶点。
BFS从源点开始,先访问相邻的顶点,再访问这些顶点的相邻但未被访问的顶点,依此递归下去,直到图中的所有可达顶点都被访问一次。它使用队列存储当前层的顶点,按FIFO顺序依次访问每个顶点。
BFS的实现步骤为:
BFS遍历任意图的时间复杂度为O(V+E),其中V为顶点数量,E为边数量。这是因为每个顶点和边最多只会被访问一次。同时BFS需要O(V)的额外空间来存储队列。
BFS常用于解决网络 shortest path 问题,计算两点间最短路径(最少边数);也可用于匹配问题、网络攻击模拟等场景。
连接分量是图论中的一个概念。如果图中的两个顶点之间存在路径连接,则称它们属于同一个连接分量。
连接分量算法的目的是partition图中的顶点,将所有连接在一起的顶点划分到同一个连接分量中。
连接关系是等价关系的一种。也就是说:
利用这一属性,可以用深度优先搜索(DFS)来找到所有连接在一起的顶点,将它们划分为一个连接分量。
使用DFS标记法实现连接分量算法:
算法Time Complexity为O(V+E),只需要一次图的扫描。
代码实现上使用visited数组记录顶点是否已访问,ID数组记录每个顶点的连接分量ID。
传染病传播分析:图中的节点代表人,边表示联系,找出潜在传播组。
科学实验数据分析:把图像像素点看作图中的节点,邻近像素点连边,找出各个粒子集团的移动轨迹。
这些都是大数据量的图问题,使用连接分量算法可以在线性时间内完成。
广度优先搜索(BFS)使用队列记录当前待访问的邻接节点,先访问距离源点最近的节点。深度优先搜索(DFS)使用栈记录当前路径,先深入某一路径直至无法继续为止,再回退考察其它路径。
连接分量是将所有相通的顶点划分到同一组的分组。可以使用DFS标记法遍历每个未访问顶点,将其与访问过的顶点分到同一连接分量。
二分图是指顶点可以分为两组,每条边只连接不同组内的顶点。可以使用DFS递归访问每个顶点并标记其组别,如果全部边都符合该属性则为二分图。
可以使用DFS遍历每个顶点,如果在访问过程中回到已经访问过的顶点则存在环。
如果图是连通图且每个顶点度数均为偶数,则存在欧拉回路,即包含图中每条边恰好一次的回路。可以使用基于度数判断及dfs遍历寻找欧拉回路。
汉密尔顿回路包含图中每个顶点恰好一次的回路。该问题属于NP完全问题,没有已知的高效算法能求解。
判断两张图是否仅通过重命名顶点就等价。该问题至今没有被证明属於P类或NP类,难度极高。
判断是否可以将图绘制在平面上而不产生边交叉。 Tarjan在1970年提出的线性时间算法能解决该问题。
有向图(Directed Graph,Digraph)是指图中的边具有方向性,可以从一个点指向另一个点。有向图的应用包括:
道路网络:路口为点,单向道路为有向边
政治博客网络:博客为点,链接为有向边
银行贷款网络:银行为点,贷款为有向边
逻辑关系网络:逻辑变量为点,蕴含关系为有向边
电路网络:元件为点,信号传输方向为有向边
常见有向图算法包括:
单源最短路径:寻找从源点到其他点的最短路径
拓扑排序:判断任务排序是否合法并排序
强连通分支:判断双向连通分量
传递闭包:判断是否存在从u到v的传递路径
BFS算法可以实现单源最短路径,时间复杂度O(V+E)。
Kahn算法可以实现拓扑排序,时间复杂度O(V+E)。
Tarjan算法可以找出强连通分支,时间复杂度O(V+E)。
Floyd-Warshall算法可以计算传递闭包,时间复杂度O(V^3)。
有向图广泛应用于交通网络、逻辑关系、电路分析、网页关系网等领域。其重要性在于可以建模实际问题中的方向性关系。
有向图API使用类名为Digraph,与无向图API仅有类名不同。
主要方法包括:
addEdge(Vertex v, Vertex w): 添加从v指向w的有向边
iterator(): 获取指定点可以指向的下一个点
reverse(): 将图中所有边反转方向
vertexCount(): 返回顶点数
edgeCount(): 返回边数
数据结构使用数组存储顶点,每个顶点使用链表存储下游顶点。
读取图数据时,以顶点对形式读取边,构建出度表。
输出图时,遍历每个顶点及其下游顶点,打印指向关系。
输入文件tinyDG.txt定义一个示例有向图,有13个顶点22条边。
通过客户端程序读取此图,构建Digraph对象,然后遍历输出每个顶点的下游顶点集合。
这提供了一个使用有向图API实现基本有向图操作的示例。
可以用广度优先搜索(BFS)来解决单源点到其他所有顶点的最短路径问题。BFS使用队列,先将源点加入队列并标记为已访问,然后循环取出队头元素,遍历其相邻但未访问的顶点,将其加入队列并标记为已访问。如此循环下去,BFS总是优先访问距离源点距离短的顶点,所以访问顺序就是从源点到其他顶点的最短路径顺序。
给一个有向图和一组源点集合,求这组源点到其他每个顶点的最短路径。可以使用修改后的BFS算法:直接将所有源点加入队列启动算法。然后任何一个可达的顶点都表示从源点集合中的一个点可达,距离就等于到达此点的距离加一。
可以使用BFS模拟图爬虫爬取全网页面内容。用队列存储待爬取页面,集合存储已经爬取的页面。先将起始页面加入队列和集合,然后循环取队头元素,解析其中的链接,将未在集合中出现的新链接加入队列和集合,直至队列为空。
用深度优先搜索(DFS)可以找出图中一个源点可达的所有顶点集。DFS使用递归,先访问源点,然后递归访问其相邻但未访问的顶点,每个顶点访问后标记为已访问。通过这种递归方式可以遍历出源点到其他所有顶点的所有路径。
可以把程序视为一个有向图,每个基本块为一个顶点,控制流转移关系为边。用DFS遍历程序流图可以找到程序中不可达的死码,或判断从一个点是否可到达结束点。
对象存储可以看作一个有向图,根节点为程序可直接访问的对象,其他节点通过引用链接相连。用DFS标记根节点可达的对象,未被标记的对象即为垃圾,可回收其内存空间。
对一个没有环的有向无环图(DAG)做DFS遍历可以得到它的拓扑排序结果。
以上内容概括了图搜素算法在常见应用场景下的使用方法,包含了算法描述和原理说明。
拓扑排序是在有向无环图(DAG)中,求出从底至顶的顺序的算法。具体来说,就是找到一种顺序,使得所有有向边都指向顺序更后面的顶点。
使用深度优先搜索(DFS)拓扑排序。在DFS访问每个顶点时,会将访问过的顶点按照后序排放在栈中。由于DAG中不存在回边,那么栈中顶点的顺序 just恰好就是一个拓扑排序。
例如任务优先级图,若有任务A依赖于B,则图中有一条从A到B的有向边。如果套用拓扑排序,得到的顺序就能保证每个任务都在其依赖任务之后完成。
拓扑排序广泛应用在调度问题、项目管理任务安排、编译系统设计等场景。一般只要涉及到先后顺序依赖的问题,都可以用有向图和拓扑排序来表示和解决。
若图存在环路,则无法进行拓扑排序。可以在DFS访问过程中判断,如果访问的顶点已经被访问过,则说明图中存在回边,即存在环路。
强连通分量(Strongly Connected Component,SCC)是指 digraph 中任意两个顶点都能够相互到达的最大子图。
Tarjan算法用来找出一个有向图中所有强连通分量,时间复杂度为O(V+E)。
算法步骤:
深度优先搜索图。
为每个顶点赋予一个指数,表示被访问的顺序。
使用栈存储当前搜索路径。
当访问顶点v时,计算v的低指数low[v],定义为v各子节点w的指数min(index[w],low[w])的最小值。
如果v的指数equal到其low指数,说明找到一个强连通分量,将相应节点出栈。
对每个节点执行1-5步骤,找出所有强连通分量。
SCC不会跨分量有边相连,但一个分量内部可以相互达到。
Tarjan算法找出的每个SCC内部都是强连通的。
若图不存在SCC,那么它是一个木形图或某些特殊复杂图。
可用于文件的版本控制与合并、网络流量检测、编译系统设计等需要判定依赖关系的问题。
最小生成树(Minimum Spanning Tree)是图论中的一个概念。对于一个带权连通图,它是一棵连接该图所有顶点的树,且其边权和最小。
最小生成树唯一确定,即任何连通图都存在且只存在一个最小生成树。这为MST算法设计提供了基础。
按边权值升序排列所有的边
逐个加入未加入树中的边
在加入一条边时,检查该边两端的顶点是否已经通过其他边连接在同一树中
如果不在同一棵树中,则加入该边;如果已在同一棵树中,则跳过该边
重复步骤2至4,直至所有的顶点都被连通为止
选择图中任一顶点作为树中起始点
查找树中顶点与其他未加入树顶点的最近边
将最近边及其两个顶点加入树中
重复2-3步,直至全部顶点都被包括在树中为止
计算机网络设计、数据传输分组选择、集成电路设计等场景都可以用MST模型求解。
贪心算法是一种通用算法设计思想。它通过每次选择当前最优(贪心)的局部解来逼近全局最优解。
最小生成树(MST)贪心算法的要点:
找出图中任意一个割面,其定义为将图中的顶点分为两部分的划分方式
在该割面中,选择权值最小的横切边,将其添加到MST树中
重复执行步骤1-2,直到MST树包含V-1条边为止
任意一个割面中,MST必须包含该割面中的权值最小横切边。
由割面性质,贪心算法选择的每条边都必定在MST中
在边数未达V-1前,图中必存在未包含黑色边的割面
算法可以一直添加边,最终构建出一个MST
如果图中存在重边,MST不唯一;如果图非连通,则得到生成森林。但贪心思想仍然适用。
它们都是MST贪心算法的具体实现,区别在于选择割面和找到最小边的方法。
设计带权边Edge类,包含连接的两个顶点和边权weight
设计带权图Graph类,使用邻接表表示结构,每个顶点存储与其相连的边list
MST类用于计算并存储最小生成树,包含构造函数构建MST和提供遍历MST边的接口
测试客户端类,根据输入文件构建图对象,调用MST算法计算MST,遍历并输出MST边和总权重
包含顶点v、w和权重weight,提供构造函数、比较函数和访问顶点函数
包含顶点数量和边表,提供增加边addEdge()和遍历特定顶点相连边adj()函数
包含构造函数计算MST,提供遍历函数edges()输出MST边
根据输入文件构建Graph,调用MST算法,输出MST信息
整个API采用面向对象思想,将图、MST算法和客户端功能分离开来,便于实现和调用算法
而Graph和MST两类实现了接口,隐藏内部结构,对客户端透明,更好扩展和优化算法实现
克鲁斯卡尔算法是一种计算最小生成树的贪心算法。
将图中各边按权值从小到大排列
考虑排序后每条边,如果加入不会形成回路,则将其加入MST树中
边加入后检查是否会形成回路,如果形成回路则跳过该边
重复步骤2-3,直至所有点都连接起来为止
使用优先队列存储边,支持按权值从小到大取出边
使用并查集检测每条边是否会形成回路
将边加入MST树前,检测其两端点是否在同一并查集中
不在同一并查集则进行合并,并将边加入MST树
时间复杂度O(ElogE),适用于大规模图论问题。
通过动画 distinctly 显示算法在小图上的运行过程。
在大型随机图上运行算法,观察首先连接小权重边形成聚类,最后由大权重边连接聚类的过程。
Prim算法是另一种计算图中最小生成树的贪心算法。
从图中的任意节点开始,将其视为树中一个节点
查找当前树中节点到其他未加入节点的最短边
将该最短边和对应节点加入树中
重复步骤2-3,直至所有节点都加入树中
使用优先队列存储树中节点到未加入节点的边
按边长度从小到大取出队首元素,将对应节点加入树
更新新的最近边边入队列
重复直至优先队列为空
时间复杂度与Kruskal算法一致,为O(ElogE)
Prim算法采用“扩展树边 frontier”的策略,克鲁斯卡尔算法采用“合并树”的策略
但两者在原理和时间复杂度上都是等价的。
同Kruskal算法,适用于大规模网络、集中电路等连接问题。
计算机科学领域一个尚未解决的理论问题是是否存在线性时间复杂度的MST算法?
已有算法周期复杂度逼近O(ElogE),但没有完全解决是否存在线性时间算法这个问题。
点集在平面内,图的边表示点间距离。已有O(NlogN)的算法,利用几何性质优化普通MST算法。
给定对象集和距离函数,将对象分为k个离散群体。常见的单链聚类算法就是利用MST算法来实现。
单链聚类算法步骤:
初始化每个对象为独立聚类
找到两个最近聚类,合并之
重复步骤2,直到聚类数达到k个
可以使用Kruskal或Prim算法直接求解。
如发现疫情病源、天体分类、基因表达方式聚类等,都可以使用MST及其优化算法来处理大规模实验数据。
找出一个有向带权图中,从一个源顶点到其他顶点的最短路径。
采用有向带权图(edge-weighted digraph)作为模型,边有方向且带有正实数权重。
提供Edge、Graph和ShortestPath三个类:
用测试客户端打印出给定源点到其他每个顶点的最短路径长度和路径,以检查算法正确性。
导航、网络路由、编译优化、物流调度等都可以用最短路径建模和解决。这些经典算法也在我们周围到处使用。
使用两个数组来存储源点s到各个顶点的最短路径长度和路径信息
其中一个数组存储各顶点的最短路径长度
另一个数组记录各顶点中最后一条边,通过反向追踪找到完整路径
检查新加入的边是否可以提供一条更短的路径到终点
如果可以,则更新affected节点的最短路径长度和父亲节点信息
否则忽略这条边,保持当前数据不变
满足两个条件时算法才能确定已找到最短路径:
每个节点的最短路径长度是从源点经过一条路径而来
对每条边,终点节点的最短路径长度不大于起点节点长度加边权值
初始化:源点路径长度为0,其他节点为正无穷大
重复边松弛操作,直到满足最优性条件为止
后续将介绍不同算法的松弛优先策略,如Dijkstra、Bellman-Ford等
迪杰斯特拉算法用于在带非负边权值的图中求出点到其他每个点的最短路径。此算法通过构建一个生成树来记录到每个顶点的最短路径。
算法工作原理:
初始化,将源点距离设为0,其他点距离设为正无穷大。将源点加入优先队列。
取优先队列中距离源点最近的点出队,加入生成树。
遍历该点的所有边,使用边权值更新相邻点的距离值。如果距离值更新,则将该点的关键值在优先队列中进行下调操作。
重复执行2-3步,直到优先队列中没有点为止。
输出生成树中的点到点关系,即为各点到源点的最短路径。
迪杰斯特拉算法的时间复杂度取决于优先队列的实现。使用二叉堆实现,则时间复杂度为O(ElogV)。
迪杰斯特拉算法的正确性可以通过证明其满足最优子结构和最优性条件来证明:
每条边只被松弛一次。
松弛操作可以保证距离值单调递减,且满足松弛不等式条件。
算法结束时,路径集和生成树构成了从源点到其他每个点的最短路径。
算法使用优先队列实现,主要包含:
distTo数组记录各点到源点的距离
edgeTo数组记录各点的前驱节点
构造函数初始化数组,将源点距离设为0
循环从优先队列取出距离最小的点,遍历其相邻边进行松弛操作
松弛如果更新距离,需要调用优先队列接口下调关键值
结束条件是优先队列为空
迪杰斯特拉算法与普里姆算法实质上是相同的,但约束条件不同。
视频介绍了无向边权重有向无环图(DAG)寻找最短路径的算法。
Algortihm的步骤如下:
对图中的顶点进行拓扑排序,获取顶点的拓扑顺序。
按照拓扑顺序遍历每个顶点,放松从该顶点出发的所有边。
对每个顶点放松其出边,就是使用松弛操作更新该顶点到其下一个顶点的距离值。
松弾操作保证了源点到任意顶点的距离最小。即使边权重是负数,也能正确找到最短路径。
时间复杂度为O(V+E),其中V是顶点数,E是边数。
视频介绍了一种内容感知图像缩放算法 - 堆场成像算法。
其原理是:
建立一个大型有向图,每个像素对应一个顶点。
给边赋予权重,使用图像处理中的能量函数。
使用最短路径算法找到从顶点塔顶到底的最短路径,这就是图像中的一个“堆场”。
按照堆场顺序删除像素进行非均匀缩放,保留图像特征。
重复找到并删除堆场,实现任意缩放尺寸的图像。
利用负权重最短路径算法,可以求解有向无环图的最长路径问题:
将所有边权重取相反数
使用最短路径算法
路径和取相反数即为最长路径
将作业调度问题形式化为一个有向无环图,对每个作业建立起点和终点,起点到终点边权为作业时间。
使用最长路径算法找到每个作业的最长路径,路径值即为作业的开始时间,满足先后顺序要求。实现高效优化调度方案。
贝尔曼-福特算法用于在边权为负数的有向图中求单源最短路径问题。
算法原理:
初始化:源点到其他所有节点的距离都设置为边数+1,即最大可能距离值。
重复V-1次:遍历每条边(u,v),如果距离u加边权值小于距离v,则距离v更新为距离u加边权值。
检查是否存在权值减小,如果有,继续进行步骤2。否则算法结束。
时间复杂度为O(VE),遍历每条边一次,最多V-1次。
贝尔曼-福特算法利用负权边的松弛操作使得最短路径总能找到,不受负环影响。算法运行结束后即找到唯一 shortest paths树。
主要包含:
定义边Edge类,记录起点,终点和权值
定义图Graph类,记录节点数和边集合
定义SPSSolver类,负责实现Bellman-Ford算法
初始化distances和predecessors数组
重复V-1次遍历每条边进行松弛操作
检查是否有权值更新,更新返回最短距离和路径
算法核心是利用松弛操作重复V-1次检查是否还存在不满足松弛条件的边,找出唯一值。
计算网络端到端的传输时间
寻找零时差语音通话中的最短路径
计算电子地图或导航系统中的最短路径
计算作业任务的最早完成时间排程
可处理多种负权值情况,比如成本、耗时等,给出实际应用中的更优方案。
最小割问题是找到一种将图中顶点分为两个集合(一个包含源点s,一个包含汇点t)的方式,使得这两个集合之间连接边的容量和最小。
图割指将图顶点划分为两个集合的操作。图割的容量定义为从包含s顶点集合指向包含t顶点集合的边的容量总和。
最大流问题采用同样的图模型,但定义了流的概念。流是对边赋予值的方式,值必须在0和边容量之间,且在每个非源汇点都满足流入等于流出的约束。最大流问题是找出可以赋予边的值,使得流量最大。
最小割问题和最大流问题实际上是等价的,如果解决一个问题,就可以得到另一个问题的解。这两个问题可以互相转换。
可以用来模拟具有容量限制的网络流问题,如交通流量、资源分配、通信网络等。
福特-富尔柯森算法是求解最大流问题的通用方法。
所有边的流量初始化为0。
始终寻找源点到汇点的一条路,如果存在就增加沿路径的流量。
前向边 是从源点到汇点的边,可以增加流量。 后向边 是从汇点到源点的边,可以减少流量。
沿增广路,增加前向边的流量,减少后向边的流量,以保持每个非源汇点的流入流出平衡。
不能找到从源点到汇点的增广路时,算法终止。
福特-富尔柯森算法通过重复寻找并利用增广路,能够逐步求得网络图中的最大流量。
满流-小割定理即最大流问题和最小割问题等价。
任意流在任意割上的流量总值等于该流的总流量。
任意流的总流量≤任意割的容量。
利用等价性命题,证明满足以下三个条件等价:
在求得最大流后,对残余网络进行图搜索,求得无未填满前向边和未清空后向边的割即为最小割。
满流-小割定理适用于物流、电路、网络等领域的最大流和最小割问题。福特-富尔克森算法求解最大流,并可以从中得到最小割。
福特-富尔克森算法通过不断搜索并拓展增广路径来增加流量,直到无法找到增广路径为止,此时流量即为最大流。
如果原始网络中各边容量和流量为整数,那么福特-富尔克森算法得到的最大流也将只包含整数流量。
增广路径选择策略会影响算法运行时间。常用策略包括:
以上结果都是宽松的理论上限,实际网络中实际 augmentation 次数可能远小于这些界限。不同网络使用不同策略效率也不同。
定义FlowEdge数据类型表示边,包含从顶点V、到顶点W、容量C和流量flow。
定义FlowNetwork数据类型表示网络,包含邻接表表示结构。
在有流量的情况下,根据边的流量定义边的残余容量。
在残余网络中搜索s到t的路径,称为增广路径。
重复搜索并利用增广路径增加流量,直到无法找到增广路径为止,此时流量即为最大流。
实现FlowEdge和FlowNetwork数据类型,包含必要的方法。 实现增广路径搜索算法,采用广度优先搜索。 算法主体循环寻找增广路径增量流量,更新流网络,最终得到最大流值。
解决任务分配,交通流量,计算机网络等各种容量受限情况下的最大流问题。
在流网络中,对每条边定义其残额容量,构成残余网络。
容量减去流量,表示还可以通过该边增加的流量。
就是边上的流量,表示可以通过该边减少的流量。
在残余网络中从源点到汇点的有向路径,称为增广路径。
初始化所有边流量为0
对残余网络搜索增广路径
如果找到,增加路径上边残余容量值的流量
重复搜索并增广,直到无法找到增广路径
此时流值即为最大流
定义FlowEdge类存储边信息
定义FlowNetwork类存储网络
使用广度优先搜索算法搜索残余网络增广路径
主循环重复搜索并增广,获取最大流值
提供相关方法计算残余容量、增量流量等
解决瓶颈流量最大化问题,如生产线平衡、网络传输等。
在Java中,字符串是不可变的对象,由字符数组和长度表示。常用的操作有获取长度、索引取字符、提取子字符串都能在常数时间内完成。而构建新字符串需要线性时间。
StringBuilder是Java中的可变字符串,底层使用动态数组存储字符。常用操作如获取长度、索引取字符、添加字符时间复杂度均为O(1)。提取子字符串需要O(N)时间。
早期使用7位ASCII表示128个字符。现代Unicode采用16位表示更多字符集。Java中char为无符号16位整数。
比较两个字符串最长公共前缀长度可以使用两次循环遍历两个字符串,时间复杂度为最大公共前缀长度O(M)。
可以将字符串操作优化为特定字母表,如DNA只含四个字符。同时考虑字母表规模R,算法时间复杂度用O(R)或O(logR)表示。
利用单个字符串只建立后缀指针,而StringBuilder需要建立实际字符串, former能在线性时间内构建后缀数组,后者需O(N^2)时间。
字符串排序、生物信息学中的基因序研究、信息处理都广泛依赖字符串处理算法。
键索引计数排序是一种利用键值范围小的特点,实现线性时间复杂度排序的算法。
键值是小整数,可以作为数组下标使用
只需两次扫描数组
时间复杂度O(N+R),空间复杂度O(N+R)
R为不同键值数量,对许多实际问题而言,R远小于N
算法是稳定的
统计每个键值出现频次,使用键值作为下标,填入频次数组
计算累积和数组,每个下标值为前一个下标和之和
使用键值作为下标,将元素移动到输出数组对应的位置
将输出数组复制回原始数组
若排序元素的键值为小整数,例如电话区号、姓名首字母等,都可以使用该算法高效排序。
使用额外数组计数频次和累积和,两次数组遍历完成排序。时间复杂度O(N),空间复杂度O(R)。
LSD Radix Sort是一种针对具有固定长度的字符串进行排序的线性时间算法。
从最低有效位开始,按每个字符位置采用基数计数排序,重复每个字符位的排序直到最高字符位,即可完成排序。
19世纪人口普查使用穿孔卡存储资料,LSD Radix Sort用于排序穿孔卡上的号码,保持卡片顺序。后来计算机初期也广泛使用此算法来排序程序。
MSD(Most Significant Digit)利用字符串中的第一个字符进行排序,可以将字符串分布到不同的组中,再对每个组递归进行同样的操作,直到所有字符串排序完毕。
使用键索引计数排序统计第一个字符出现的次数并构建偏移数组
根据偏移数组将字符串分割到不同的子数组中
对每个子数组递归使用相同算法,但排序元素改为字符串的第二个字符
重复第3步,直至所有字符排序完毕
定义FlowEdge和FlowNetwork数据类型表示字符串和数组。
使用键索引计数排序统计每个字符出现的次数。利用次数构建子数组进行递归处理。
在最坏情况下为O(NL),平均情况下为O(NL/R),L为字符串长度,R为字符集范围。
大字符集会占用更多空间
小子数组效率低,采用插入排序切换
重复比较字符,采用快速排序切换
MSD字符串排序性能依赖数据,空间复杂度高,内循环操作多;快速排序时间复杂度更稳定,内循环操作少,但重复比较相同前缀字符。
该算法结合了快速排序和基于最重要位的radix排序的优点, 每次以字符串的一个字符为基准进行三路快速排序。
选择第一个字符为基准进行三路快速排序,将字符串分为小于、等于、大于基准字符的三部分
对等于部分递归使用下一个字符进行排序
对小于和大于部分进行递归调用
重复前三步,直至所有字符串字符都进行过比较
在平均情况下为O(NlogN),比快速排序少一次重复比较相同前缀字符。
时间复杂度低,性能好
不需要额外空间
适用于常见情况下带有公共前缀的字符串
缓存友好
易于实现
当元素为字符串且存在公共前缀时,该算法性能优异,如图书分类号、会员号等排序问题。
三路快速字符串排序是处理字符串排序问题的优选算法。
后缀数组可以用于快速子串搜索。给出一个文本串,可以预处理成后缀数组,然后客户端提交查询子串,使用后缀数组快速找出该子串在文本串中的所有出现位置。
这是一个早期的搜索方法。将文本构造成后缀排序,然后使用二分搜索快速定位查询关键词,再输出关键词周围的文本内容。这与我们熟悉的浏览器搜索是一致的。
给一个字符串,找出其中最长的重复子串。这对生物学研究具有重要意义,如发现基因重复序列。
尝试所有的子串对之间做最长公共前缀计算。时间复杂度为O(N^2),对大量数据不可用。
将字符串构造成后缀数组,然后对后缀进行排序。排序后,相同子串会排在一起,只需要一次遍历即可找出最长重复子串。这种方法时间复杂度为O(NlogN)。
如果重复子串过长,后缀排序也会耗费O(N^2)时间。因为重复子串会产生过多相同的后缀。
它通过指数增加比对字符数,每次轮询可以在线性时间内完成后缀排序。使用索引排序可实现常数时间字符串比较,最终以线性时间解决这个问题。
串处理算法在生物信息学、数据压缩等领域具有很重要的应用。后续还将介绍其他串处理算法。可以看出,串处理问题远非简单,需要深入研究才能找到更好的算法。
后缀数组是字符串的一个重要数据结构,它存储一个字符串所有后缀在字典序中的排名。
获取字符串所有后缀。
将后缀按照字典序排序。
记录每个后缀的原数组下标,即为后缀数组。
最长共同前缀查询,时间复杂度O(1)。
子串搜索,使用二分搜索定位,时间复杂度O(MlogN)。
最长重复子串问题,时间复杂度O(N)。
文本索引,生成关键词与位置映射。
数据压缩,重复子串表示成公共前缀和长度。
只需要一次预处理,后续查询效率很高。
对重复子串也能很好支持。
与后缀树一样,支持各种常见的串操作。
相比后缀树,后缀数组空间复杂度更低。
快速排序法,平均时间O(NlogN)但不稳定。
归并排序法,时间O(NlogN)且稳定。
Manber-Myers算法,时间线性但复杂度高。
后缀数组是解决串相关问题的重要数据结构,它支持各种常见操作,构建和使用效率也很高。
文本索引是一种将文本内容建立映射关系的数据结构,用于文本搜索。
顺序索引:直接存储文本内容及位置。查询效率低。
哈希索引:根据关键词哈希到表位置,存关键词及位置。哈希冲突严重。
后缀树:基于文本所有后缀构建的树形数据结构,支持高效内容位置查询。但构建复杂度高。
后缀数组:基于后缀排序生成的数组,支持二分定位查询,构建复杂度低于后缀树。
哈希表+倒排索引:关键词与包含它的文档构成倒排列表存入哈希表。
大多数商业搜索引擎使用的索引结构是哈希表+倒排索引,它具有很好的查询效率和空间利用率。
而在需要高效随机访问某个特定位置信息的场景,后缀数组可能是最佳选择。
字符串索引是一种将文本内容建立映射关系的数据结构,用于文本搜索。常见索引方法包括顺序索引、哈希索引、后缀树和后缀数组。
顺序索引直接存储文本内容及位置,查询效率低。哈希索引根据关键词哈希到表位置,存关键词及位置,但哈希冲突严重。
后缀树基于文本所有后缀构建的树形数据结构,支持高效内容位置查询,但构建复杂度高。后缀数组基于后缀排序生成的数组,支持二分定位查询,构建复杂度低于后缀树。
哈希表+倒排索引是关键词与包含它的文档构成倒排列表存入哈希表,给设计搜索引擎首选方法。
ries数据结构支持查找字符串前缀匹配键、通配符匹配键以及最长前缀匹配键。
前缀匹配给定前缀如”sh”时返回所有以”sh”开头的键。通配符匹配允许特定字符为通配符,返回匹配项。最长前缀匹配给定字符串,返回符号表中最长匹配前缀的键。
可以通过对tries树进行深度优先遍历实现顺序迭代,在遍历过程中记录路径节点串就可以得到所有键。
前缀匹配只需在前缀节点下递归收集子节点。通配符匹配允许指定字符为通配符。
最长前缀匹配在搜索过程中记录遇到的最长键,无链接时或节点有值时返回最长键。这在IP路由表匹配中很常用。
此外,Patricia算法和后缀树等也可以有效实现字符串搜索,并消除单向分支,在实际应用中广泛使用。整体来说,tries数据结构在大数据检索中的优势明显。
给定一条主串text和一个模式串pattern,查找模式串在主串中所有出现的位置。
字符串查找问题是给定文本和模式字符串,查找模式是否出现在文本中。
最简单的笨拙算法是首先使用两个指针分别索引文本和模式字符串,逐字符进行匹配比较。如果发现不匹配,则模式字符串指针向后移动一位,文本字符串指针不动,继续匹配比较。
这种算法实现简单,但性能很差。在最差情况下,时间复杂度可以达到O(MN),其中M和N分别为模式和文本字符串长度。
此外,每次发现不匹配都需要回溯文本,且不符合许多实际应用中流式数据的特征。
可以使用增量指针改进实现笨拙算法,在每轮匹配中同时增加文本和模式指针,直到发现不匹配时才对模式指针进行回溯。
这种改进实现明显显示了回溯的操作,但本质上时间复杂度和问题还是一样的。
字符串查找算法应解决两个重要问题:
时间复杂度是否可以做到与模式字符串长度无关,即达到O(N)线性时间?
如何避免对文本进行回溯,适应流式数据输入的特征?
后续将介绍一种算法,可以同时解决这两个问题。
Boyer-Moore算法是一种基于模式字符串的优化方法,可以在线性时间内完成字符串查找。
算法从模式字符串尾部开始逐字符进行匹配比较。如果发现不匹配,会根据模式字符串的结构信息跳过匹配的过程,直接跳到一个可能匹配的位置。
跳过的字符数取决于两个偏函数:
判断函数:尝试将模式的最后一个字符与文本比较,如果不匹配直接跳过模式长度个字符。
差异函数:计算模式中距离最后一个字符最远的不同位置,并跳过该位置右边的字符数。
使用两个数组预处理模式字符串,构建判断函数和差异函数表。
文本指针从左到右扫描,模式指针从右到左匹配。
一旦发现前面字符匹配失败,直接根据函数表获得跳过位数,模式指针往右移动相应位置。
重复匹配直到找到完全匹配或文本扫描完毕。
平均情况下可以达到O(N)线性时间,忽略了模式字符串长度因素。并且不需要对文本进行回溯。
Boyer-Moore算法以高效的 skipping 特性解决了字符串匹配问题。
Boyer-Moore算法是一种基于模式串的优化方法,可以在平均情况下实现线性时间内找到字符串匹配。
algorithms 从模式串的末尾开始逐字符进行匹配比较。匹配失败时,根据模式串的结构信息可跳过一定范围的匹配过程,直接跳到下一个可能匹配的位置。
跳过的字符数取决于两种预计算函数:
判断表:记录每个字符最后出现的位置。如果失败字符不在模式中,跳过整个模式串长度。
移动表:每个字符对应最右侧不同位置字符的偏移量。失败时以此值跳过文本子串匹配。
预处理获得判断表和移动表。
文本指针从左至右扫描,模式指针从右至左匹配。
一旦发现前缀匹配失败,根据表直接跳过文本子串,模式指针右移商定范围继续匹配。
重复直到匹配成功或文本扫描完毕。
平均情况下可以达到O(N)线性时间,忽略了模式串长度因素。并且不需要对文本进行回溯。
在一些情况下,时间复杂度甚至可以降低到O(N/M)级别,随着模式串长度增加而提高效率。
Rabin-Karp算法是一种基于哈希的字符串匹配方法,可以在线性时间内找到模式串在文本串中的所有匹配位置。
算法使用一个更高的数作为模数q,将模式串和文本子串看成数字,并对该数字求模运算得到哈希值。
只有当模式串和文本子串的哈希值相等时,才可能是匹配。此时需要进一步检查每个字符是否相等。
哈希值的计算使用Horner法则,每次只增减一个数位,可以在O(1)时间内从一个子串更新到下一个。
使用大素数q作为模数。
计算模式串的哈希值。
滑动一个窗口计算文本每个长度为模式串长度的子串的哈希值。
比较哈希值是否相等,相等再进一步比对每个字符。
找到所有满足条件的匹配位置。
时间复杂度为O(N+M),其中N和M分别为文本和模式串长度。
易于扩展,可以将其应用于寻找多个模式串或二维模式匹配等情况。
Rabin-Karp算法通过利用哈希技巧,实现了线性时间内的子串匹配。
正则表达式是一种用来描述一组字符串的符号集合。它由字母、特殊符号和元字符构成,可以用来表示多个不同的字符串。
正则表达式主要通过四种操作构建:
连接操作(连接):将多个字母一起拼接表示匹配字符串。
| 或操作( | ):使用竖条符表示或的关系,可以匹配前后任意一个字符串。 |
闭包操作(*):在字符或字符串后加星号,表示匹配0个或多个该字符或字符串。
举例:
常见的扩展元字符有:
正则表达式可以用于字符串匹配、检索、验证等方面。实际应用中,还加入了更多操作符用于简化书写。
实现子字符串搜索。
定义邮件地址、电话号码、身份证等格式。
关键词高亮、注释过滤等语法解析。
生物信息学中的基因模糊匹配。
编程语言中的标识符检查。
网页表单数据验证。
日志记录和文本处理。
搜索引擎中的pattern匹配
所以,正则表达式在字符串处理方面具有广泛的应用前景。它不仅能描述模式,还可以用来驱动相关算法解决问题。
NFA是一种抽象的状态机模型,用于描述正则表达式对应的语言。
NFA与确定性有限状态机(DFA)类似,不同在于状态之间允许存在ε过渡,即不读取输入就转移到另一个状态。
NFA接受字符串的条件是存在一条可行路径可以读取全部输入并到达接受状态。
根据Kleene定理,任意正则表达式都可以构造对应的NFA。而NFA到DFA的转换可能导致状态爆炸。
每个正则表达式字符对应一个状态。状态之间有字符匹配和ε过渡。终结状态表示匹配成功。
考虑所有可能的状态序列。如果其中一条路径读取全部输入且到达终结状态,则字符串匹配;否则不匹配。
可以采用深度优先搜索遍历所有可能路径,检查是否存在匹配路径。时间复杂度取决于NFA规模。
NFA相比DFA更通用,允许利用ε过渡省略部分状态,从而解决DFA状态数爆炸问题。是正则表达式匹配的基础模型。
NFA模拟操作需要追踪每读取一个字符后,NFA可能处于的所有状态。
使用整数表示状态,从0到M表示正则表达式中的M个字符对应状态。
用有向图表示ε转换,状态作为顶点,ε转换作为边。
初始化可能状态集{0},表示开始可到达状态。
读入第一个字符后,可能状态集添加匹配此字符状态 reachable(ε,可能状态集)中的状态。
重复4,每读入一个字符后更新可能状态集。添加字符匹配状态后ε转换到达状态。
整个过程中持续跟踪可能状态集是否包含接受状态。
若读完所有字符后可能状态集仍未包含接受状态,则输入不匹配。
该算法 time复杂度取决于文本和模式长度的乘积M×N,但实际取决于每个状态可能过渡的路径数量。
利用深度优先搜索实现ε转换到达性判断,对应图问题中单源点可达问题。实现NFA状态模拟操作的关键。
给定一个正则表达式,目标是构建其对应的非确定性有限状态机(NFA)。
将正则表达式字符映射成状态,并添加开始和结束状态。
从左到右遍历正则表达式:
左括号入栈
字母添加迁移到下一个状态
星号添加当前状态回环与下一个状态的ε迁移
右括号出栈, pops或与当前状态添加ε迁移
使用栈追踪括号嵌套层次,以添加或操作符的ε迁移。
使用图数据结构表示NFA
栈保存括号信息
每步操作时间复杂度为O(1)
构建NFA需要遍历正则表达式一次,时间和空间复杂度均为O(M),M为表达式长度
算法流程清晰,实现简单
构建NFA时间和空间效率均高
NFA覆盖正则语言,可以用于后续匹配任务
本算法通过遍历与栈操作,有效地根据正则表达式结构构建对应的NFA,为后续匹配任务提供支持。它明确定义了各种模式的处理方式。
Grep命令是Ken Thompson在早期Unix系统中实现的,用于通过正则表达式查找文件中的字符串匹配行。
它通过以下步骤实现:
将正则表达式编译成NFA网络结构
遍历标准输入或者文件,模拟NFA识别每一行是否匹配
匹配成功则打印该行
Grep命令时间复杂度与子串匹配算法一致,为O(MN)。但它可以用一个正则表达式描述无限多个模式。
Java字符串类提供matches方法验证是否匹配。
另外,Pattern和Matcher类可以将正则表达式编译为NFA,并模拟匹配过程。
这可以用来:
验证单行是否匹配(匹配标志返回true或false)
收集所有匹配子串(通过循环获取匹配结果)
例如从DNA序列中提取重复序列,或从网页中提取邮箱地址。
部分实现有可能时间复杂度呈指数级增长
引用前匹配的括号表达式实际上扩充了正则语言,但不属于正则语言范畴
使用不当可能陷入算法性能攻击
每种工具都有其应用场景,不要凡事使用正则表达式
正则表达式匹配提供了强大的文本处理能力,是编程语言不可或缺的一个功能。
有限状态机(FSM)包括有限状态自动机(DFA)和非确定有限状态自动机(NFA)。
它们可以用来描述字符串集合和实现字符串匹配。
DFA状态数决定的时间复杂度为O(N),但无法识别某些正则表达式集合。
正则表达式是描述字符串模式的一种语言,同样也可以描述字符串集合。
任何正则表达式描述的字符串集合,都可以用等价的DFA或NFA来描述。
这意味着正则表达式、DFA和NFA在识别能力上等价。
可以将正则表达式编译成NFA结构,然后通过NFA模拟匹配过程来实现字符串匹配。
这就是Grep命令中的实现方法。
在程序语言中,如Java也提供了Pattern和Matcher类来完成同样的过程。
最坏情况下,正则表达式匹配的时间复杂度与子字符串搜索算法一致,为O(MN)。
但在某些正则表达式和输入字符串下,部分实现的时间复杂度可能是指数级的。
使用引用等扩展后,正则表达式表达能力超过正规语言,无法用有限状态机实现。这可能导致效率问题。
长度编码利用位串中零和一的重复串进行数据压缩。
只记录不同位之间的切换点,以计数的形式表示重复串的长度。
从左到右扫描位串,记录连续重复的零和一。
使用固定位数(如8位)的计数器计数每个重复串的长度。
将所有计数值串联起来,即为压缩后的编码。
定义计数器位数,平衡压缩率和兼容性。
遍历原串,统计重复长度并记录到计数器。
输出所有计数值组成的新串。
长度解码时,依次读取计数值并重现对应长度的零或一。
适用于图片、文本等含有大量重复零一模的应用。
如BMP、JPG、fax等格式都使用此编码进行数据压缩。
压缩比例视原始数据重复程度而定,重复较多时压缩效果明显。
长度编码是一种简单有效的数据压缩算法。
初始化计数器并设定位数(如8位)
遍历原始数据,统计连续重复元素的个数
当重复元素改变或计数超出最大值时,写入统计结果到计数器
输出填充好的计数器数据
初始化解码指针
按计数器位数读取次计数值
根据计数值重复输出对应的元素
循环直至处理完所有计数器数据
计数器位数影响压缩效率和范围
处理超长重复串时可采用缩小计数器值+填充计数器0的方法
原数据类型决定重复元素的判断条件
输入输出数据采用字节流或二进制表示法读写
长度编码实现简单直观,但通过计数重复元素简化了原始数据结构,实际压缩比取决于输入内容重复程度。此算法适用于重复度高的数据处理。
长度编码通过统计重复像素计数,对图像数据进行有效压缩。
BMP采用无损压缩,直接存储图像像素值,占用大空间。
可对像素行/列进行独立长度编码压缩,减小文件大小。
Jpeg算法通过DCT变换分离图像空间频率信息。
对后续量化系数进行长度编码,进一步去除重复数据。
采用可变长度编码表对计数进行熵编码,获得高压缩率。
黑白扫描图像中存在大片黑白局部,可通过长度编码最大限度压缩。
统计连续重复黑色/白色像素行/列个数,仅记录计数值。
对待压缩图像进行两次长度编码处理,完全恢复原始图像。
但由于舍弃部分空间信息,压缩率优于BMP但劣于JPG。
长度编码作为前处理,在保留图像通道完整性的同时提升压缩效率。
减法是一种算法设计技巧,可以通过将一个问题转化为另一个已知如何解决的问题来解决新的问题。
如果问题X可以通过将其实例转化为问题Y的实例,利用问题Y的解法求解,然后将结果转回问题X来解决,则称问题X可以通过问题Y进行减法。
减法利用已知算法,为新问题提供高效求解思路。当转化开销较小时,可以将问题复杂度降低。它是算法设计中常用的方法之一。
凸包问题可以通过排序问题的减法得到O(nlogn)的算法。Graham扫描算法用于计算凸包。
无向图的最短路径问题可以通过将其转化为有向图问题,然后使用有向图最短路径算法。
中位数和元素唯一问题减法到排序问题。
调度问题减法到拓扑排序问题。
币发行器问题减法到最短路径问题。
匹配问题减法到最大流问题。
线性规划问题减法到最大流问题和最短路径问题。
利用已知高效算法,通过问题间的逻辑关系进行转化,将新问题转化为老问题,从而得到新问题的解法。
减法广泛应用于排序、图论和机器学习等领域,解决包括凸包、最短路径、匹配等各类问题,极大促进了算法设计技巧的发展。
减法可以通过问题间的逻辑关系,将一个问题转化为另一个已有解法的问题,从而找到新问题的解法。
如果问题A可以在线性时间内减法问题B,而问题B已知需要Θ(f(n))时间,则问题A至少也需要Θ(f(n))时间。
否则,如果问题A有比Θ(f(n))更优算法,通过减法就可以为问题B找到更优算法,与B已知下限矛盾。
可以证明排序问题在二次决策树模型下可以线性时间内减法凸包问题。
而排序问题下限为Θ(nlogn),则凸包问题下限也为Θ(nlogn)。
将排序元素映射成抛物线上的点坐标
将点集作为输入给凸包算法
根据凸包算法的输出顺序即可得到排好序的元素
因此若凸包算法复杂度小于Θ(nlogn),就可以推导排序算法复杂度小于Θ(nlogn)
减法技巧可以利用已知问题下限,推导新的问题下限,有效指导和评估算法设计。
如果问题X可以在线性时间内通过问题Y进行减法,而Y问题已知需要Θ(f(n))时间,则X问题至少也需要Θ(f(n))时间。
排序问题可以线性时间内减法凸包问题。凸包问题也可以将排序问题作为基础进行实现。这样两者难易程度等价。
通过相互减法,整数系列运算和矩阵运算系列问题难易程度等价。但其具体难度下限仍未破解。
减法用于设计高效算法、推导问题下限和帮助分类问题难易程度。但在大规模软件中可能导致问题。
许多问题通过减法归入等价难易类,构建出问题难易谱系。但随研究深入,分类难易程度也在不断优化。
减法技巧可以有效判断和分类问题难易,指导算法设计方向,构建问题知识体系。它是理解计算理论的重要手段。
如果可以证明排序问题可以在线性时间内通过凸包问题进行减法,而凸包问题下限为Θ(nlogn),则排序问题下限也为Θ(nlogn)。
同样地,如果问题A可以在线性时间内通过已经确定下限Θ(f(n))的问题B进行减法,则问题A下限也不低于Θ(f(n))。
凸包问题下限Θ(nlogn)通过与排序问题的减法得到。
元素唯一问题下限Θ(nlogn)通过与排序问题的减法得到。
其他图论和线性规划问题也利用已知问题下限通过减法推导出下限。
减法技巧通过问题间转换关系,利用一个问题的已知下限来推导另一个问题的下限,有效指导和评估算法设计难度。
简单算法是用于解线性规划问题的优化算法,由当兹在二战后提出。
简单算法以边界解的形式表示问题,从一個極值點轉移到另一個極值點,每次轉移都能增加目的函數值,直到最优解。
使用松弛变量构成初始基础,使非基变量等于0,求解基础变量的值。
选择基础和行根据最少比值法则,用行消元法消去某一列元素,将该变量纳入基础。
如果目的函数导数全为非正,说明当前点是最优解,算法结束。
简单、易实现,每次都保证增大目的函数,采用极值点移动方式,直到找全局最优解为止。它利用线性代数方法解决线性规划问题。
简单算法是线性规划重要的内点法算法,算法思想简单明了,时间复杂度低。
通过证明问题固有难度,规避低效算法设计,指导算法研究方向。
如果X问题可以在线性时间内通过Y问题进行减法,而Y问题下限已知,则X问题下限不低于Y问题。
排序问题下限Θ(nlogn)通过与凸包问题的减法得到。
凸包问题下限Θ(nlogn)也可以这样得到。
将排序问题映射成抛物线上的点坐标问题
给凸包算法,根据输出点顺序得到排好序的元素
由排序问题下限,推导出凸包问题下限Θ(nlogn)
减法技巧利用问题之间的关系,高效推导问题固有难度下限,指导研究方向选择。
基础集B表示基变量,非基集N表示非基变量。每次迭代pivot操作交换B和N中的元素。
使用松弛变量初始化B和N集,计算基础变量值。
根据最少比值法则(Minimum Ratio Test),选择下降最快的变量进入基础集B。
行消元分步进行:
如果所有目标函数增量均为非正,则当前点最优解。
C/C++(CPLEX,Gurobi),Python(PuLP,CVXPY)等语言广泛实现简单算法,应用于各类线性规划问题。
简单算法利用数据结构和数值计算的相结合,实现线性规划问题的有效求解。它是线性规划研究的基础。
可以将问题形式规范化为线性规划标准形式,如将最大化问题改写为最小化问题,将不等式改写为等式等。
可以将大于或等于符号的约束改写为等式约束,方法是添加一个非负松弛变量。
将网络中的流量作为变量,流量限制和流量守恒作为约束条件,目标函数最大化源点到汇点的流量,从而将最大流问题规范为线性规划问题。
将匹配对应关系作为变量,每个人或工作最多匹配一个作为约束,目标函数最大匹配数,将最大匹配问题规范为线性规划问题。
许多问题都可以通过添加变量和约束条件将问题规范为线性规划问题,而线性规划有高效的求解算法,从而解决更复杂的问题。
将问题规范为线性规划问题,然后利用线性规划求解器求解,是处理优化问题的通用方法。
计算问题存在三种难度:
可以在多项式时间内找到解,如线性规划问题。
可以在多项式时间内验证候选解是否正确,但未知是否可以多项式时间求解,如整数规划问题。
难以在多项式时间内解决,属于难题,如旅行商问题。
P=NP问题亟待解答,它与计算难点的本质相关:
P类问题是否等价于NP类问题?若等价,则NP类问题都有多项式算法。
否则,NP-Complete类问题就实际上需要超级多项式时间才能解决。
解答这个问题将决定算法是否能对抗所有难问题。但目前还没有定论。
将计算问题归类并指导算法研发的难度理论,为解决实际问题提供了理论基础。
寻找问题包括许多基本问题,其特征是:
输入包含许多实例
需找到实例的解或报告无解
可以高效验证答案是否正确
Lsolve问题:给线性方程组,找解。
LP问题:给线性不等式组,找解且优化目标函数。
规整线性规划:线性规划其变量限定为0或1。
真值问题:给逻辑表达式,找使表达式为True的变量赋值。
上述问题都属于寻找问题,因为:
输入规模明确
答案规模小于输入
可以快速验证答案是否正确
寻找问题理论适用于决策问题及优化问题。具体采用寻找问题类容易明确理论假设。
P类问题:可以在多项式时间内通过算法解决。
NP类问题:可以在多项式时间内验证答案是否正确,但未知是否有多项式时间算法求解。
P=NP问题是计算复杂度理论的核心问题:
P类问题是否等价于NP类问题?
如果等价,则NP类问题都存在多项式算法。
否则,NP完全问题可能没有多项式时间算法。
许多NP问题都找不到多项式时间算法,如整数规划、旅行商问题。
但尚未证明P≠NP,这关系到算法是否能对抗所有难问题。
揭示P与NP关系是理论计算机科学的重要开放问题。
P与NP问题的解答将决定算法设计的基本限制,对理论和实际都很重要。但至今仍难得到定论。
P类问题:可以在多项式时间内通过算法解决。
NP类问题:可以在多项式时间内验证答案是否正确,但未知是否有多项式时间算法求解。
寻找多项式时间算法,则该问题属于P类。
使用多项式时间还原将问题还原到SAT问题。如果SAT问题被认为没有多项式时间算法,则问题难度与SAT一致,被归为NP完全类。
通过布尔公式求值,已证明可能没有多项式时间算法。
将整数线性规划问题通过构造还原到SAT问题,则整数线性规划难度与SAT一致。
Karp证明了包括旅行商问题、独立集问题等在内的许多重要问题,都可以通过多项式时间还原将SAT问题还原成它们,从而这些问题难度与SAT一致。
问题分类明确了各类问题的难易程度,指导了算法设计方向。利用SAT问题作为基础难题进行还原法,为问题分类提供了一种统一的方法论。
NP完全问题是NP类问题中难度最大的一类,它具有以下特征:
该问题属于NP类问题。
NP类问题中任何一个问题,都可以在多项式时间内还原到该问题。
库克-利文定理证明,任何NP问题都可以还原成Sat问题。所以,Sat就是NP完全问题之一。
如果某个NP完全问题能在多项式时间内解决,那么NP类问题都可以在多项式时间内解决。
NP完全问题之间具有等价性,解决任一个问题的多项式算法,都可以用于其他NP完全问题。
证明某问题为NP完全,就表明该问题的难度与Sat问题一致,很可能不存在多项式时间算法。这对问题研究提供重要参考。
2000年证明Ising模型的3D情况下计算问题是NP完全的,解释了为什么50年无法找到多项式算法。
intractable问题指没有多项式时间算法可以求解任意实例的问题。
放弃多项式时间算法的某个限制条件,如只关心实际实例,而非任意实例。
简化问题范围,找到问题的一个特殊子类可以多项式时间解决。
放弃最优解要求,找到近似解算法。
使用概率多项式时间算法,可以在特定条件下有高概率效率求解。
通过限定输入规模降低时间复杂度,在实际范围内可求解。
如最大满意度问题有算法可以在多项式时间内找到满足 78% 子句的赋值。
给定图,找出遍历每个顶点恰好一次的环。它属于NP完全问题。
给出了深度优先搜索方法模拟所有可能路径解决,但时间复杂度为指数级。
本课程为大学计算机科学二课,主要内容为数据结构和算法分析,语言为Java。
第一周没有代码实践,内容为纯数学计算算法运行时间。
实现带有排序数组的两个数之和问题算法。给定数组和目标值,检查是否存在两个元素之和等于目标值。
利用数组排序特征,从两端 simultaneoulsy 往中间移动,依次检测两个元素之和。
实现三个递归问题:
实现一维和二维数组在Java中的表示和转换。包含矩阵到列表和列表到矩阵的转换。
本课介绍图论和贪心算法相关知识。
图论包含结点(vertex)和边(edge)两种元素。主要任务是识别关键路(critical road),即如果某条边被破坏会使结点无法相通。
采用深度优先搜索算法遍历图,删除每条边后检查结点是否还能相通。如果不能相通,则该边为关键路。
解决乘坐火车要经过多个车站的最短时间问题。
给定每个车站间的火车班次时间,需按顺序经过所有车站,计算最少时间和等待时间总和作为评判标准。
提供具体的车站间时间表作为输入,给出最短时间和等待时间总和作为输出结果。
贪心策略优先考虑时间最早的班次,如果无法到达下个车站会回溯考虑其他班次,更新结果并计算等待时间总和。
提供了更多复杂的车站间时间表作为测试用例,包括多个线路和更多车站,供学习算法原理。
给出Java代码,能正确根据提供的测试用例输入输出结果,并给出详细说明供学习参考。
本课介绍动态规划和回溯算法。
纸牌游戏跳棋,根据不同位置可以进行不同的移动,目标是以最少步数到达终点。
使用递归函数计算从每一个位置出发到终点所需要的最小步数,并记录结果避免重复计算。
提供不同场景(起始点和结构)的输入,算法给出相应场景下最小步数的输出。
给出Java代码实现递归函数和记忆数组,正确读取不同输入并输出结果。
通过迷宫寻找从起点到终点的路径。
使用深度优先搜索递归遍历每个位置,判断边界、obstacles和是否重复访问。
提供不同结构的迷宫输入,算法判断其是否能找到解以输出结果。
使用二维数组表示迷宫,给出findPath函数实现递归搜索以及主函数读取输入和输出结果。
提供更大规模和复杂结构的迷宫用例,可以测试算法性能和应用范围。
动态规划和回溯算法在Java中的实现,给出详细算法描述和代码结构,有效解决问题。
由于许多NP完全问题很难找到精确解,近似算法旨在在多项式时间内找到问题的近似解。
近似率衡量算法产生的解与最优解的比率。比如如果近似率为c,那么找到的解不超过最优解的c倍。
给定n个作业,每个作业有个截止时间和需要的处理时间。如何安排顺序使总等待时间最小。
按作业截止时间排序,优先处理紧急作业。近似率为2-1/m,m是处理方式总数。
给定元素集合和每个集合的成本,选择集合的最小子集覆盖所有元素。
选择成本效益比最高集合,移除被覆盖的元素重复操作。近似率为O(logn)。
给定带权图,找到节点总权值最大且不相邻的节点子集。
使用贪心策略从权值最大节点开始选择,避免重复选择相邻节点。
贪婪算法可以在多项式时间内找到许多优化问题的较好近似解,是解决NP难题的重要手段。
旅行商问题(traveling salesperson problem,TSP):给定一系列城市和它们之间的距离,找出访问每个城市一次且回到起点的最短路线。
第一行包含城市数量n;以下n行每行包含n个整数,其中第i行第j个整数代表城市i到城市j的距离。
最短路线总距离,保留两位小数。
用邻接矩阵存储城市间距离信息
使用回溯算法遍历所有可能路径
每一步选择下一个未访问城市,更新当前最短路径
回溯时撤销选择,继续其他路径
遍历结束输出最短路径长度
提供完整的Java代码,读取输入,实现回溯搜索算法,并输出距离。
提供不同规模城市坐标作为输入(3城市、5城市),验证代码结果与理论结果一致。
更大规模城市坐标输入
分析算法时间复杂度
使用近似算法如2-opt改进
解决TSP都是重要课题,本题给出简单实现。
给出n个字符串,将它们按照词典顺序排列。
第一行一个整数n,后面n行每个字符串一个。
按词典顺序排列的字符串,每个字符串一个行。
使用标准库排序函数sort函数比较两个字符串
字符串比较采用逐字符从前到后的顺序进行
遇到不同字符直接返回大小关系
若前n-1字符相同,则比较最后一个字符
重复此过程完成字符串排序
定义比较函数compare用于字符串排序
调用sort函数执行排序
遍历结果打印各字符串
提供不同长度和字符串组合的测试输入,验证排序结果正确。
考虑更大规模输入排序时间
使用其他排序算法如快速排序进行对比
实现忽略大小写或单词首字母的排序方式
给出简单实现和思路,解决常见排序问题。
使用遗传算法解决旅行商问题。
初始化一个个体集合,每个个体代表一个路径
评估个体路径长度 fitness
选择路径长度短的个体进行繁殖
在繁殖中交叉和变异产生新个体
更新个体集合,重复2-4步骤得到最优路径
个体编码使用排列表示路径
交叉使用部分交叉,变异使用邻座交换
轮盘赌选择、élitisme保留最优个体
设定世代数,收敛则结束
提供标准TSP实例,观察算法迭代过程和结果收敛情况。
调整算法参数如变异概率
添加局部搜索提高精度
分析时间复杂度
在大规模问题Above验证算法效果
给出遗传算法在TSP中的简单应用,提供更广泛思路。
使用遗传算法中的交叉操作解决TSP问题。
选择相邻两个父路径,交叉点随机切分成两个子路径。
路径采用List表示,交叉点随机生成
得到第一子路径,移除重复城市
第二子路径取剩余城市补充顺序
评估子路径长度作为适应度
给定5城市TSP实例,观察交叉后的子路径效果。
交叉点不在起点或终点
第二子路径需包含所有城市
路径重复性检查
适应度最小路径选择
多点交叉方式比对
混合其他遗传算子如变异
在更大规模TSP实例上测试
分析时间复杂度
给出交叉算子在遗传算法中的应用,助解TSP问题。