企业官网建设流程全解析

目录

例如

方法

实现上述想法的步骤

示例代码

详细时间复杂度分析

递推关系式变为

代入递推式

结论

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

未排序数组中第 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/163051233
C# 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051552
Java 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051446
Python 未排序数组中第 k 个最小/最大元素 预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051495
JavaScript 未排序数组中第 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++.h>
using namespace std;

// Returns median of a small group (size <= 5)
int getMedian(vector<int> &group) {
sort(group.begin(), group.end());
return group[group.size() / 2];
}

// Function to Partition array from index
// l to r around the pivot value x
int partitionAroundPivot(vector<int> &arr,
int l, int r, int x) {

// Move pivot x to end
int i;
for (i = l; i < r; i++) {
if (arr[i] == x) break;
}
swap(arr[i], arr[r]);

// Standard partition logic
i = 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 pivot
return i;
}

// Recursively finds the k-th smallest element in arr[l..r]
int selectKthSmallest(vector<int> &arr, int l, int r, int k) {
if (k > 0 && k <= r - l + 1) {
int n = r - l + 1;
vector<int> medians;
int i;

// Divide array into groups of 5 and store their medians
for (i = 0; i < n / 5; i++) {
vector<int> 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 elements
if (i * 5 < n) {
vector<int> lastGroup(arr.begin() + l + i * 5,
arr.begin() + l + i * 5 + (n % 5));
medians.push_back(getMedian(lastGroup));
}

// Find median of medians
int 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 pivot
int pos = partitionAroundPivot(arr, l, r, pivot);

// If position matches k, return result
if (pos - l == k - 1) return arr[pos];

// Recur on left or right part accordingly
if (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 Array
int kthSmallest(vector<int> &arr, int k) {
return selectKthSmallest(arr, 0, arr.size() - 1, k);
}

// Driver code
int main() {
vector<int> 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)。

结论

尽管该算法在最坏情况下是线性的，但由于递归开销和多次迭代，涉及的常数项很大。实际上，随机化的快速选择算法速度更快，尽管其性能仅针对平均情况，但通常仍是首选。

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。