目录例如方法实现上述想法的步骤示例代码详细时间复杂度分析递推关系式变为代入递推式结论如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。未排序数组中第 k 个最小/最大元素 | 最坏情况下的线性时间(K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time)给定一个包含不同整数的数组arr[]和一个整数k。任务是找出数组中第 k 小的元素。为了便于理解 k指的是如果将数组按升序排列则位于第 k 个位置的元素。注意 k 始终小于数组的大小。例如输入arr[] [7, 10, 4, 3, 20, 15], k 3输出7说明排序后的数组为 [3, 4, 7, 10, 15, 20]。第三小的元素是 7。输入arr[] [12, 3, 5, 7, 19], k 2输出5说明排序后的数组为 [3, 5, 7, 12, 19]。第二小的元素是 5。输入arr[] [1, 5, 2, 8, 3], k 4输出5在之前的“未排序数组中第 k 个最小/最大元素 预期线性时间”文章中我们探讨了一种预期时间复杂度为线性的算法。本文将讨论一种最坏情况下时间复杂度为线性的方法。未排序数组中第 k 个最小/最大元素 预期线性时间C 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051233C# 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051552Java 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051446Python 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051495JavaScript 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051600方法这段代码的思路与QuickSelect()函数的基本思想相同都是通过围绕一个枢轴点对数组进行分区来找到第 k 小的元素。但与 QuickSelect() 不同的是QuickSelect() 可能会选择不好的枢轴点导致最坏情况下的时间复杂度降至O(n²)而该算法通过使用“中位数的中位数”技术精心选择枢轴点确保了最坏情况下的线性时间复杂度。我们希望枢轴点能够保证分区的合理平衡并非完全平衡但也并非极度偏斜。这意味着枢轴点应该确保数组的大部分都位于其两侧。这就是“中位数的中位数”策略的作用所在。实现上述想法的步骤1、为了找到合适的枢轴点我们将数组分成每组5 个元素。这个大小5是一个关键的观察结果它既足够小可以实现快速排序又足够大可以确保在划分过程中达到数学上可证明的平衡。2、每个组独立排序并将其中位数收集到一个名为“中位数”的新列表中。3、收集完所有中位数后我们递归地找到这个中位数列表的中位数。这个值就成为我们的枢轴值。这样做的目的是为了避免使用错误的枢轴值使其尽可能接近整个数组的真实中位数。4、确定枢轴点后我们使用标准逻辑对数组进行分区左移元素小于等于枢轴点右移元素大于枢轴点。函数 partitionAroundPivot() 将枢轴点移动到正确的位置并返回该位置。5、现在我们将这个枢轴点的位置与所需的第 k 个索引进行比较。如果匹配则直接返回该值作为答案。6、否则我们决定是在枢轴的左侧还是右侧进行递归6.1、如果枢轴位于第 k 个位置之后则答案位于左侧子数组中。6.2、如果枢轴位于第 k 个位置之前则相应地调整 k并对右侧子数组递归。示例代码// C implementation of the Worst Case Linear Time algorithm// to find the k-th smallest element using Median of Medians#include bits/stdc.husing namespace std;// Returns median of a small group (size 5)int getMedian(vectorint group) {sort(group.begin(), group.end());return group[group.size() / 2];}// Function to Partition array from index// l to r around the pivot value xint partitionAroundPivot(vectorint arr,int l, int r, int x) {// Move pivot x to endint i;for (i l; i r; i) {if (arr[i] x) break;}swap(arr[i], arr[r]);// Standard partition logici l;for (int j l; j r; j) {if (arr[j] x) {swap(arr[i], arr[j]);i;}}swap(arr[i], arr[r]);// Final position of pivotreturn i;}// Recursively finds the k-th smallest element in arr[l..r]int selectKthSmallest(vectorint arr, int l, int r, int k) {if (k 0 k r - l 1) {int n r - l 1;vectorint medians;int i;// Divide array into groups of 5 and store their mediansfor (i 0; i n / 5; i) {vectorint group(arr.begin() l i * 5,arr.begin() l i * 5 5);medians.push_back(getMedian(group));}// Handle the last group with less than 5 elementsif (i * 5 n) {vectorint lastGroup(arr.begin() l i * 5,arr.begin() l i * 5 (n % 5));medians.push_back(getMedian(lastGroup));}// Find median of mediansint pivot;if (medians.size() 1) {pivot medians[0];} else {pivot selectKthSmallest(medians, 0, medians.size() - 1,medians.size() / 2);}// Partition array and get position of pivotint pos partitionAroundPivot(arr, l, r, pivot);// If position matches k, return resultif (pos - l k - 1) return arr[pos];// Recur on left or right part accordinglyif (pos - l k - 1)return selectKthSmallest(arr, l, pos - 1, k);return selectKthSmallest(arr, pos 1, r, k - pos l - 1);}return INT_MAX;}// Function to find kth Smallest in Arrayint kthSmallest(vectorint arr, int k) {return selectKthSmallest(arr, 0, arr.size() - 1, k);}// Driver codeint main() {vectorint arr {7, 10, 4, 3, 20, 15};int k 3;cout kthSmallest(arr, k);return 0;}输出7时间复杂度O(n)最坏情况下选择时间为线性时间空间复杂度O(n)在每次选择调用中递归存储中位数需要额外的空间。详细时间复杂度分析我们逐步分析中位数算法的最坏情况时间复杂度1、将数组分成 5 个元素一组的组。共有 n/5 组这样的组。由于每组元素的大小是固定的因此求每组的中位数需要O(1) 的时间。所以这一步的总时间复杂度为O(n)。2、求中位数的中位数。递归地求 n/5 个中位数的中位数需要T(n/5)时间。3、使用标准分区操作围绕枢轴中位数的中位数对数组进行分区需要O(n)时间。4、划分完成后递归调用会根据第 k 个最小元素所在的位置向一侧左侧或右侧进行。为了解递归调用的规模我们分析有多少元素保证大于或小于枢轴值。n/5 个中位数中至少有一半大于或等于中位数的中位数。每一组中位数至少贡献 3 个大于中位数的中位数的元素。因此大于或等于枢轴值的元素个数至少为(3 * ceil(1/2 * ceil(n/5)) - 6)即至少为(3n/10 - 6)。类似地小于枢轴值的元素个数至少为 3n/10 - 6。因此在最坏的情况下递归调用最多会处理 n - (3n/10 - 6) 7n/10 6 个元素。递推关系式变为当 n 80 时T(n) Θ(1)当n 80 时T(n) T(ceil(n/5)) T(7n/10 6) O(n)。我们通过代换法证明 T(n) O(n)。假设对于某个常数 c对于所有 n 80都有 T(n) cn。代入递推式T(n) c(n/5) c(7n/10 6) O(n) cn/5 7cn/10 6c O(n) 9cn/10 6c O(n)我们可以选择足够大的 c使得 cn/10 6c O(n)因此 T(n) cn。因此最坏情况下的运行时间是线性的O(n)。结论尽管该算法在最坏情况下是线性的但由于递归开销和多次迭代涉及的常数项很大。实际上随机化的快速选择算法速度更快尽管其性能仅针对平均情况但通常仍是首选。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。