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备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
