QuickSelect平均时间复杂度O(n) [如何？]
QuickSelect是一种用于在无序数组中查找第k小元素的快速选择算法。它的平均时间复杂度为O(n)，其中n是数组的大小。
快速选择算法的基本思想是通过类似快速排序的分治法来逐步缩小搜索范围，直到找到第k小的元素。具体步骤如下：
- 选择一个枢纽元素（pivot），可以是随机选择或固定选择。
- 将数组分为两部分，小于等于枢纽元素的放在左边，大于枢纽元素的放在右边。
- 如果枢纽元素的位置恰好是k-1，则返回该元素。
- 如果枢纽元素的位置大于k-1，则在左边部分递归查找第k小元素。
- 如果枢纽元素的位置小于k-1，则在右边部分递归查找第k小元素。
通过每次将搜索范围缩小一半的方式，快速选择算法能够在平均情况下以线性时间复杂度找到第k小元素。
快速选择算法的优势在于其高效的平均时间复杂度和较低的空间复杂度。它适用于需要在无序数组中查找第k小元素的场景，例如统计学中的中位数、Top K 问题等。
腾讯云提供了多种云计算相关产品，其中与快速选择算法相关的产品包括：
- 云服务器（ECS）：提供弹性计算能力，可用于运行快速选择算法的代码。产品介绍链接：https://cloud.tencent.com/product/cvm
- 云数据库MySQL版（CDB）：提供高性能、可扩展的关系型数据库服务，可用于存储和管理快速选择算法的数据。产品介绍链接：https://cloud.tencent.com/product/cdb
- 人工智能机器学习平台（AI Lab）：提供丰富的人工智能算法和工具，可用于在快速选择算法中应用机器学习技术。产品介绍链接：https://cloud.tencent.com/product/ai
以上是关于QuickSelect平均时间复杂度O(n)的完善且全面的答案，同时满足了要求不提及其他云计算品牌商的要求。
相关·内容
1回答
我被要求在一个未排序的数组中查找前log(n)个元素。我知道我可以用一种选择算法在O(n)时间内找到-th(N)最大的元素，然后找到所有大于它的元素。但是，是否可以使用堆或其他优先级队列在O(n)时间内完成此任务？ 谢谢
浏览 27提问于2019-03-07得票数 0
2回答
目前，我有一个非常大的数组，我希望从其中得到最上面的n项，比排序数组所需的速度更快。从概念上讲，我非常肯定，无论JS解释器使用什么排序算法，都有可能胜过它。
浏览 5提问于2019-12-01得票数 1
回答已采纳
我正在学习QuickSelect来找出第k个最小的数字。我听懂了这个程序。但是我坚持认为QuickSelect的平均时间复杂度是O(n)。 我已经尝试了用Java编写代码，并且它工作了。但是我被时间复杂性所困扰。}; }
} 平均时间
浏览 21提问于2019-02-11得票数 0
回答已采纳
2回答
还有其他建议的方法，其中之一使用了quickselect算法，但据我了解，quickselect只返回未排序数组中的k-th元素。返回后，k的左和右元素仍未排序。所以应该是这样的： quickselect(int[] arr, k);}
Quickselect是O(n)，对于k时间我们这样做，所以总的时间复杂度是O(n*k)。But the dat
浏览 3提问于2014-02-20得票数 0
回答已采纳
1回答
我们一直这样做，直到q==r，但我不知道Algo真正做了什么，我最好的猜测是，它返回数组的最大值，以及这样的事情的运行时间。非常感谢!
浏览 2提问于2021-04-29得票数 0
回答已采纳
如果你有长度为N的J排序数组，找到其中kth最小的元素。这里有一些潜在的解决方案，其中一些涉及最小堆或二进制搜索，但我想知道使用quickselect的时间复杂度是多少。如果我们简单地将每个数组连接在一起，并在组合的数组上使用quickselect。Quickselect在平均情况下以线性时间运行，但数组的组合确实扩展了搜索空间，但它比使用合并策略更有效，因为如果您选择了好的轴心，quickselect必然会忽略一些元素。
浏览 6提问于2018-08-13得票数 0
ie:数组1，5，3，6，3，2，其中C=9，答案：{1，2，3，3}提示:剪枝&搜索和QuickSelect
我花了很长一段时间思考如何解决这个问题，但是这个限制使得这个问题变得非常困难我的假设是，数组不需要完全排序，因为提示建议将prune & search和QuickSelect结合起来。QuickSelect在固定时间内很容易找到(使用)，但我不确定两者的结
浏览 0提问于2018-11-14得票数 0
回答已采纳
2回答
这个问题的答案是相当直截了当的，我没有任何问题决定一个线性时间算法来解决它。
然而，在这个问题上的工作让我思考。在线性时间内，给定一个未排序的数组，能解决这个问题吗？我的第一个想法是使用堆，这会给出一个O(nlogk)时间复杂度的解决方案，但我试图确定它是否有可能想出一个O(n)的解决方案？我在考虑可能使用类似quickselect之类的东西，但问题是，这有一个预期的时间O(n)，而不是最坏的情况下
浏览 17提问于2022-10-02得票数 2
1回答
对于n个整数的数组A，数学家可以在数组上执行以下移动 2.上述dp解决方案的复杂性为: n^3k。
你能帮我找到更好的解决方案吗？
浏览 8提问于2022-11-02得票数 0
2回答
我只是不知道如何正确删除最小k次，并成功地返回组中的kth最小元素。Example test = Example(*this);
int n = test._total ;for (i = n/2; i >= 0; i--) {for(i =
浏览 3提问于2011-04-10得票数 5
回答已采纳
3回答
据我所知，其时间复杂度为O(n*log(n))和O(1)空间。
选项2:堆化数组，将其转换为min堆。然后将()弹出堆的顶部x次。据我所知，这是O(n) + O(x*log(n))。我试图测量运行时间，但我觉得我得到的结果是相互矛盾的。也许因为选择2，它取决于x有多大。也许还有一种更好的方法去实现算法。如果有人能帮上忙，我将不胜感激！
浏览 13提问于2020-06-07得票数 1
4回答
最坏情况时间复杂度列表
、、、、
我知道对于数组实现，二分查找的最佳、平均和最坏情况的时间复杂度分别为最佳O(1)；平均O(log )；最差O(log )；。同样，我知道对于数组实现，插入排序的最佳、平均和最坏情况的时间复杂度分别为最佳O(n)；平均O(n^2)；最差O(n^2)；。然而，我该如何计算单链表、
浏览 1提问于2014-01-13得票数 0
2回答
我试图在O(n)中找到一个分而治之的算法来解决这个问题，但我什么也没找到。给定一个数组A和给定的值k，找出和大于或等于k的最小子集。有人能给我一个开始解决这个问题的想法吗？
任何帮助都是非常感谢的。
浏览 58提问于2021-03-06得票数 2
回答已采纳
维基百科指出，快速选择算法()的平均运行时间为O(n)。然而，我不能清楚地理解为什么会这样。有人能给我解释一下(通过递归关系+主方法的使用)，平均运行时间是O(n)吗？
浏览 2提问于2011-05-10得票数 40
回答已采纳
1回答
我知道时间复杂度应该是O(N)。然而，当我对它进行经验测试时，我得到了奇怪的结果。有人能解释一下发生了什么事吗？array[i], array[pivot] = array[pivot], array[i] pivot = insertPivot(array, start, end)
return arr
浏览 1提问于2021-04-03得票数 1
2回答
for (int i = 0; i < k - 1; i++) { }
}然而，这是我感到困惑的地方。对于第一个例子，对于最小堆，我假设构建堆是O<
浏览 0提问于2018-10-30得票数 1
回答已采纳
4回答
这将平均复杂度从O(n log n)降低到O(n)，最坏的情况是O(n^2)。
我不明白如何将平均复杂度降低到O(n)？不是更多的O(N/2 log N)仍然是O(N log N)。最坏的情况O(n</e
浏览 6提问于2019-07-08得票数 17
回答已采纳
3回答
有没有人知道不同std::nth_element实现的预期运行时间和最坏情况运行时间？我几乎每天都在使用这个算法。一种是O(n)平均情况和O(n)最坏情况，一种是O( n )最坏情况，但在实践中速度很慢(中位数)。另请注意，。标准说，这必须是更糟糕的O(n)平均时间。
浏览 8提问于2012-06-17得票数 20
回答已采纳
2回答
例如：
显然，我可以在O(n*log(n))时通过简单的排序和分区来实现这一点，但我想知道这是否不能在线性时间内完成。我知道QuickSelect在预期的O(n)平均值情况下运行，所以我的直觉是，这个问题应该在O(p*n)时间内可以解决。我天真地认为
浏览 4提问于2015-05-03得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
