java - QuickSelect 平均时间复杂度 O(n) [HOW?]
问题描述
我正在学习快速选择以找到第 K 个最小的数字。我理解了这个程序。但我对 QuickSelect 的平均时间复杂度是 O(n) 感到困惑。
我已经尝试了 Java 中的代码并且它有效。但我被时间复杂性困住了。
public class KthSmallestNumberUsingQuickSelect {
int findKthNumber(int arr[], int left, int right, int k ) {
if(k > 0 && k <= right - left + 1) {
int pos = partition(arr,left,right);
if(pos - left == k - 1)
return arr[pos];
if(pos - left > k - 1)
return findKthNumber(arr, left, pos - 1, k);
System.out.println(k - pos + left - 1);
return findKthNumber(arr, pos + 1, right, k - pos + left - 1);
}
return Integer.MAX_VALUE;
}
int partition(int arr[], int left, int right) {
int i = left ;
int j;
int x = arr[right];
int temp = 0;
for(j=left; j<right; j++ ) {
if(arr[j] <= x) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
temp = arr[i];
arr[i] = x;
arr[right] = temp;
return i;
}
public static void main(String[] args) {
KthSmallestNumberUsingQuickSelect kq = new KthSmallestNumberUsingQuickSelect();
int arr[] = {7,10,4,3,20,15};
int k = 3;
System.out.println(kq.findKthNumber(arr,0,arr.length-1, k));
}
}
平均时间复杂度 O(n) 是多少?任何人都可以向我详细解释一下吗?
解决方案
我认为您的问题不是 QuickSelect 特定的。您在问大 O 符号和平均 Theta (Θ) 符号之间有什么区别。
大 O 表示法描述了算法将使用的最大潜在复杂性。
另一方面,Θ 表示法是问题输入的所有可能组合的平均复杂度。
还有用于最佳情况复杂度的欧米茄 (Ω) 表示法。
快速选择算法遵循与快速排序相似的复杂性,你是对的,两者的大 O 表示法都是 O(n^2),但在平均情况下它们更好。
如果您需要更具体的解释为什么平均情况是线性的,请阅读这篇文章中的答案。
推荐阅读
- android - 如何让我的 Places api 在自动完成片段上设置一个始终可见的选项?
- html - "not" 伪类被忽略
- c - 为什么我不能创建不透明的数据类型?
- python - 在 Jupyter 中使用 cx_Oracle 连接到本地 oracle 数据库时出错
- laravel-5.8 - Laravel 5 使用 GET 方法的简单搜索框
- javascript - 我可以在 HTML 的 iframe 中添加复选框吗
- javascript - 匹配字符串中的第二个句子
- javascript - 如何使预取链接与 JavaScript 文件一起使用?
- visual-studio-code - 源代码管理 VSCode 中的事件处理
- python - 卸载 distutils 安装项目失败