数据结构(邓俊辉)学习笔记】排序 5——选取:通用算法

2024-09-08 00:36

本文主要是介绍数据结构(邓俊辉)学习笔记】排序 5——选取:通用算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 尝试
  • 2. quickSelect
  • 3.linearSelect:算法
  • 4. linearSelect:性能分析
  • 5. linearSelect:性能分析B
  • 6. linearSelect:性能分析C

1. 尝试

在讨论过众数以及特殊情况下中位数的计算方法以后,接下来针对一般性的选取问题,介绍优化的通用算法。
在这里插入图片描述

既然选取问题的查找目标就是在整个数据集中按大小次序秩为 k 的那个元素,所以最直接不过的方法莫过于首先对整个数据集做一次排序。之后我们只需从首元素开始,依次向后移动,当累计移动了 k 步之后,我们也就自然的抵达了查找的目标。

然而很遗憾,这里首先需要做一趟排序。我们知道在最坏情况下,我们不得不为此花费 n log n的时间,对于这样一种性能,我们是不能满意的,正如我们马上就要看到的,实际上存在更为优化的算法。
在这里插入图片描述
当我们听到选取这个词时,或许很自然地会想起堆结构。没错,堆结构的主要功能也是在做某种意义上的选取,也就是选取其中的极值元素。从这个意义上讲,选取极值就是选取问题的一个特例,而反过来选取问题也是 getmax 之类操作的一般化推广,那么是否有可能借助堆结构来实现高效的选取操作呢?

沿着这个思路你或许会想出如这个图所示的一种方法。具体来说我们需要首先将所有的 N 个元素组织为一个堆。当然这里我们需要的是一个小顶堆,也就是说堆顶元素是全局的极小值。因此每当我们调用一次 delmin 接口,就可以摘出当前的极小值。就全局而言,第一次调用将会摘出全局的最小元,也就是秩为零者。而接下来的第二次调用将会得到全局秩为1者。因此在我们连续地对这个接口调用 k 次之后,整个堆的规模将变为 n - k。而此时的堆顶也就应该恰好是全局秩为 k 的那个元素。就第一步预处理,也就是建堆操作而言,我们性能还不差,我们可以直接调用弗洛伊德算法,也就说为此我们只需花费线性的时间。

然而此后对 delmin 接口的调用累计时间却很长。具体来说,我们每次都需要花费 logn 的时间,而总共需要调用 k 次。也就是说只要 k 在数量级上与 n 同阶,这个方法的渐进性能将与全排序的方法没有什么实质区别。
在这里插入图片描述

当然,我们也可以尝试利用堆的其他方法,比如一种可行的方案是:我们首先从数据集中任选出 k 个元素,并将它们组织为一个大顶堆。接下来对于剩余的 n - k 个元素,我们分别调用一次 insert 操作,将它插入堆中,然后随即调用一次 delmax 接口,摘除掉新的堆顶。

对于这样的每一步迭代,如果此前堆的规模为 k,那么在执行 insert 的操作之后,它的规模将变为 k + 1,在随后立即执行过delmax 操作之后,堆的规模又会从 k + 1重新恢复为 k。

请注意,当每一次这个堆的规模从 k 增加到 k + 1 时,对应的堆顶元素都是迄今为止发现的秩为 k 的那个元素。因此,当所有元素都经过如此处理之后,当这个堆的规模最后一次达到 k + 1 时,堆顶元素也就是全局秩为 k 的那个元素。

由此可见,按照这种方法我们的确可以完成选取的任务,然而同样很遗憾,它的时间复杂度依然不能得到有效的控制。具体的,为了构建初始的堆,我们这里同样只需线性的时间。然而在随后的 n - k 次迭代中,无论插入或者删除,我们都需要多达 log k 的时间。

但如果 k 非常小或者反过来非常大,这个算法的性能将接近于线性。然而,当 k 取值接近中间范围时,这个算法的复杂度又将重新回到 n log n

在这里插入图片描述
当然利用堆结构来实现选取功能的方法还有很多,我们这里再来看其中的一种。具体来说,这里我们将使用两个,而不是一个堆。首先我们要从数据集中任取 k 个元素构建一个大顶堆 h。

相应的我们要将剩余的 n - k 个元素组织为一个小顶堆 g。接下来我们需要反复的比较这两个堆的堆顶,只要 h 大于 g,我们就令二者互换位置。然后分别通过一次下滤,将这两个堆重新复原,这个迭代将持续进行下去,直到最终 h 不再大于 g。

而一旦达到这种状态,对于 g 的顶元素,也就是我们要查找的目标,因为对于此时的这个元素来说,总共有 k 个元素不大于它,同时有 n - k - 1 个元素不小于它。尽管这种方法的构思非常精巧,但是同样的,它在最坏情况下的复杂度依然不能得到有效的控制。

2. quickSelect

在这里插入图片描述

我们接下来尝试方法,把将采用减而治之的策略,为此需要借用快速排序中的 partition 算法,因此这一算法也称作 quickselect。

你应该记得快速排序中的 partition 算法的功能就是在当前的序列中构造出一个轴点,我们也知道这个轴点具体的位置是随机的,取决于我们的运气,或者更准确地说取决于它相对于整个数据全集而言所拥有的秩

在此我们不妨来设想一种最好的情况,是什么呢?是的,有可能这个候选轴点就是我们在 k 选取问题中的查找目标,也就是说它的秩恰好就是 k。果真如此的话,我们的计算量只不过是一趟partition,我们知道它所对应的运行时间不过 O(n)。

在一般的情况下,我们又当如何处理呢?不要紧,在一般的情况下,尽管这个候选轴点未必就是我们要查找的目标,但是根据它我们却可以对搜索的范围进行有效的裁剪。

具体的如这个图所示,假设我们的查找目标 k 对应于这个位置,而在经过 partition 操作使得我们候选轴点变成名副其实的轴点之后。如果它所对应的 i 不是我们的目标 k,那么根据 i 与 k 的大小关系无非两种情况。

  • 我们知道在经过 partition 操作之后,这个轴点之所以成为一个名副其实的轴点,是因为在它左侧的元素都不大于它,而在它右侧的元素都不小于它。因此如果轴点的秩要比 k 更大,那么也就说明我们的目标元素必然存在于子序列 L 中,而与子序列 G 无关。这就意味着在这种情况下,我们可以将 G 减除掉。
  • 对称的也同理,如果轴点的秩要小于 k,那么由图也可看出目标元素必然来自于子序列 G 中,而与子序列 L 无关。也就说在这种情况下,我们也可大胆地减除掉子序列 L。

综合起来,无论是哪种情况,我们都可以有效地使得问题的规模得到缩减。这样一个缩减的过程将持续进行下去,在整个问题的规模退化到平凡情况之前,我们迟早会找到目标元素。

比如这就是 quickselect 算法的一种可能实现。如刚才所言,整个算法就是一个反复迭代不断减而治之的过程。在每一步迭代中,我们都需要仿照快速排序中的 partition 算法构造出一个轴点,而且我们可以确定这个轴点的秩为 i。

以下无非刚才我们所说的两种情况。如果整点的秩不小于 k,那么就意味着子序列 G 可以被减除掉。为此,我们只需将有效区间的右边界更新为 i -1 ,对称的,如果轴点的秩不大于 k,这意味着子系列 L 可以被减除掉。为此我们只需将有效区间的左边界更新为 i + 1。

很遗憾,尽管这里旨在构造轴点的内循环,每趟只需线性的时间,但是我们却不能有效地控制外循环的执行次数。尽管可以证明在通常的随机意义下,外循环平均只需执行常数次,但是我们依然不难看出在最坏的情况下它依然需要执行多达 n 次。

因此就最坏情况而言,这个算法依然不是最优的。不过好消息是这个算法已经为我们通往最优的算法打开了通路。

3.linearSelect:算法

在这里插入图片描述

接下来将要介绍这个选取算法,就是在刚才 quickselect 算法的基础上进行的改进,因为这个算法即便在最坏情况下也只需渐进的线性时间,因此我们也称之为 Linearselect。

这个算法需要用到一个常数 Q,它的数值不大,我稍后就会具体来确定它的取值。这个Linearselect 算法将以递归形式给出,因此我们首先需要准备好递归基,也就是当问题的规模已经足够小时,不妨调用任何一种平凡的选取算法。

  1. 接下来我们需要将整个数据集均匀的切分为若干组,每一组依然是一个随机的序列。它们的规模都统一取做刚才引入的那个常数 Q。如此我们将得到 n/Q 个子序列。

  2. 接下来对于每一个这样的子序列,我们都分别对它们进行排序。没错,排序,而且在这里,你可以不必过于在意排序的效率。比如可以直接采用插入排序算法,而在经过如此排序之后,我们也就可以直接得到每一个子序列所对应的中位数。既然总共有 n/Q 个子序列,所以这里中位数也总共应该有 n/Q 个。

  3. 接下来我们再从所有这些中位数中去找到它们的中位数,也就是中位数的中位数(median of the medians) ,具体如何来找到呢?通过递归,也就是调用 Linearselect 算法本身,我们将这个中位数的中位数记作大写的 M。

  4. 接下来我们需要以这个中位数的中位数为基准,对整个数据集中的所有元素进行分类,具体来说,所有小于 M 的元素都归入 L 中,所有大于 M 的元素都归入到 G 中,而所有与之相等的元素都归入到集合 E 中。

    此时的状态以及可能的情况可以由这组图来表示。既然这三个集合之间有明确的大小关系,所以无论如何,从大到小,它们必然是 L 在最左侧,E 居中以及 G 在最右侧。当然它们的规模大小可能有所不同。

    不要忘了我们的查找目标是在全局秩为 k 的那个元素。所以接下来我们可以沿用 quickselect 算法的思路,根据不同的情况相应的对问题的规模进行裁剪,从而实现有效的减而治之。

  5. 具体来说,根据目标元素具体应该落在 L、E 或者 G 中。无非三种情况。如果 L 足够长,以致 k 应该落在其中。那么不难看出,E 以及 G 都可以被减除掉。

    因此在这种情况下,我们只需将查找的范围缩减到子集 L,然后递归的进行查找。对称的,如果 G 足够大,则意味着 E 以及 L 都可以被减除掉。因此在这种情况下,我们同样可以将搜索的范围缩小到子集 G,并同样通过递归来完成后续的查找。

    需要注意的是,如果子集 G 是以序列形式给出的,那么在这个序列中原先秩为 k 的那个目标元素在 G 中所对应的秩将有所减少。在这里我们不要忘了对它及时地更新。那么最后一种情况无非就是目标元素落在子集 E 中。不要忘了 E 中的元素都等于全局的那个中值,这意味着什么呢?没错,意味着全局的这个中值恰好就是我们的查找对象。也就说我们在这个位置已然命中,因此可以直接将其返回,这也是算法的最终出口。

这个 Linearselect 算法尽管略显复杂,但是我不难验证它在功能上的正确。因此我们接下来需要回答的关键问题就是,它的时间复杂度有多高,是否如它的名字所暗示的那样,即便在最坏的情况下也能保证不超过渐进的线性。

4. linearSelect:性能分析

在这里插入图片描述

接下来,就来对 Linearselect 算法的复杂度做一界定,按照我们习惯,将该算法所对应的运行时间记作 Tn,以下对照这个算法的各个步骤分别进行估算。

  1. 首先是作为递归基的第 0 步,我们讲过当问题规模已经降至足够小时,将直接采用任何一种平凡的算法,比如直接借助排序的方法,当然所对应的时间复杂度也自然就是 Q logQ。然而因为这里 Q 是取做一个常数,所以 Q logQ 实质上也是一个常数。
  2. 我们再来看算法有效的第一步,也就是对整个集合的均分,如果数据集合表示为序列,那么这一步只需对整个序列做一趟线性的扫描,因此我们也只需线性的时间。
  3. 接下来是对每一组元素进行排序并进而找出其中的中位数。同理,因为此时每个子序列的长度都不超过 Q,因此我们也可以认为每个子序列的排序都可以在常数时间内完成。考虑到总共有 n/Q 个子序列,因此所有这些子序列的排序,以及从中找出中位数,累计所需要的时间也依然不过是线性。
  4. 再来考察第三步,也就是从上一步所得到的 n/Q 个中位数中递归地去找到全局的中位数,也就是那个大写的 M。我们知道这一步是通过递归来完成的,但问题规模已经缩减到 n/Q,所以对应的时间复杂度也可以表示为 T(n/Q)。
  5. 再接下来的第四步是根据全局中位数将整个集合划分为三个子集,并分别计数。不难看出,只需一趟线性扫描,这项工作即可完成。因此,这一步所需要的时间累计也不过线性。
  6. 以下是最关键的第五步,这一步任务是递归的求解规模已经缩小的新问题。在这里我们宣称无论如何,新问题的规模都会得到有效的压缩,具体来说,它们的规模至多是原问题的75%。

5. linearSelect:性能分析B

在这里插入图片描述

那么新问题规模为何必然会得到有效的削减呢?回顾一下,你应该记得新问题都是在原问题的基础上削减掉子序列 E + G 或 E + L 而得的,而 L 和 G 都是以全局的中位数是那个大写的 M 来确定。

实际上这个大 M 虽然未必就是整个集合的中位数,但就某种意义而言,它的确不会过小或者反过来过大。具体来说,在整个集合中必然有不少于25%的元素不小于这个 M,而且另外还有25%的元素在数值上不大于这个大 M。

这一性质,通过这幅图可以很清楚地看出来。这里我将所有的 n/Q 个子序列垂直摆放并平行地罗列于此。以它们各自的中位数为界,每个子序列都可以相应的分为更大的一半以及更小的一半。每个子序列都是如此。

如果将所有子序列中的中位数由大到小排列于此,那么它们当中的那个中位数也就是大 M,大致应该在这个位置。现在可以看到以这个大 M 为界,整个序列的确可以分为三个部分。

首先是这些白色的部分,不难看出,它们在数值上都不会小于大 M。从数量上讲,这些白色部分至少占据整体的1/4。对称的,你也可以注意到这些深色的部分。它们组合也至少占整个集合的1/4,而且其中的元素在数值上也绝对不会超过大 M。

进一步的不难看出,所有这些白色部分都应该属于此时的子集 G 或 E ,反之对称的所有的深色部分也都应该属于此时的子集 L 或 E。

这样我们就证明了我们此前的那个断言,也就是无论我们每次剪除的是 L + E 或 G + E,新问题的规模都不会超过此前问题规模的75%。

6. linearSelect:性能分析C

好了,现在我们就可以来准确地界定 Linearselect 算法的渐进复杂度。
在这里插入图片描述

实际上,根据此前的分析,我们可以得出这样一个递推式,难道不是吗?为了利用这个算法来完成选取,除了需要花费线性的时间做一系列的准备工作,最实质的计算无非两次递归调用,第一次递归是为了从 n/Q 个中位数中确定全局中位数,也就是那个大 M。

第二次递归则是针对规模已经缩小的新问题,我们刚刚证明过新问题的规模至少会缩减25%。

不要忘了我们目标是线性,而为了使得我们能够从这递推式解出一个线性函数,我们只需保证这两个递归项的参数之和严格的小于线性,也就是说1/Q与3/4的总和必须严格的小于1。这一点并不难做到。

比如我们只要将 Q 取作5,就能保证这一点。针对于 q 等于5 时的这个递推式,你不妨在课后做一细致地推导。你将会发现,尽管就渐进意义而言,它的确是一个线性函数,但其中的常系数却相对很大,也就是说,这里的 Linearselect 算法更具有理论意义。

这篇关于数据结构(邓俊辉)学习笔记】排序 5——选取:通用算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146609

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c