快速选择最坏情况(Θ(n^2)或O(n^2)?)
快速选择最坏情况的时间复杂度为Θ(n^2)或O(n^2)。
快速选择是一种用于在无序数组中查找第k小或第k大元素的算法。它基于快速排序算法的思想，通过每次选择一个基准元素将数组分为两部分，并只对包含目标元素的那一部分进行递归操作，从而减少了排序的时间复杂度。
在最坏情况下，快速选择算法的时间复杂度为Θ(n^2)或O(n^2)。这种情况发生在每次选择的基准元素都是当前数组中的最小或最大元素时。这样，每次递归只能排除一个元素，需要进行n次递归操作，导致时间复杂度为n乘以n，即n^2。
然而，在平均情况下，快速选择算法的时间复杂度为Θ(n)或O(n)。这是因为在平均情况下，基准元素的选择是随机的，每次递归都能将数组的规模减半。因此，平均情况下只需要进行log(n)次递归操作，时间复杂度为n乘以log(n)，即nlog(n)。但是，由于快速选择算法不涉及实际的排序操作，所以时间复杂度表示为Θ(n)或O(n)。
快速选择算法适用于需要在无序数组中查找第k小或第k大元素的场景。例如，在一个包含大量数据的数组中，可以使用快速选择算法快速找到第k大的元素，从而实现快速的数据分析和处理。
腾讯云提供了多种云计算相关产品，其中包括云服务器、云数据库、云存储等。这些产品可以帮助用户快速搭建和管理云计算环境，提供稳定可靠的计算、存储和数据库服务。具体产品介绍和链接地址可以参考腾讯云官方网站：https://cloud.tencent.com/
相关·内容
2回答
因此，我正在学习QuickSort，并且对运行时间有一点困惑。输入有三种类型:升序、降序和随机序。如果我们从子数组的第一个位置( input )选择pivot，我知道按升序或降序对输入进行排序需要O(n^2)。对随机顺序输入进行排序需要O(nlogn)还是仍然需要O(n^2)时间？
浏览 10提问于2020-11-30得票数 0
2回答
快速排序算法可分为以下步骤
1)确定枢轴。
2)基于枢轴的链表划分。
3)递归地将链表划分为两部分。
现在，如果我总是选择最后一个元素作为枢轴，那么识别pivot元素(第一步)需要O(n)时间。
在识别了pivot元素之后，我们可以存储它的数据并将其与所有其他元素进行比较，以确定正确的分区点(第二步)。当我们存储枢轴数据时，每个比较将花费O(1)时间，而每个交换则需要O(1)时间。因此，总的来说，n个元素需要O(n)时间。
所以递推关系是
T(n) = 2T(n/2) +n，为O(nlogn)，与链表合并排序相同。
那么，为什么对于链接列表来说，合并排序比快速排序更可取？
浏览 5提问于2017-11-30得票数 1
回答已采纳
1回答
我想在未排序的列表中找到近似的中位数，我知道两个算法
算法1-快速选择
算法2-中位数
我不能在我的项目中使用quickselect，因为它在最坏的情况下需要O(n^2)。我听说过中位数，但我的同事建议它需要O(n)和一些常数factor.therefore，它的时间复杂度是Cn，常数因子is比快速选择大。我想知道与中位数相关的常数因子是什么?为什么中位数不使用9元素的伪中位数？
或者他们有没有其他算法可以在线性时间O(n)内找到近似的中位数？
浏览 10提问于2014-02-18得票数 0
2回答
我在找出平均和最坏情况的时间复杂度方面有一点困难。因此，我使用以下逻辑删除了这个BST节点
删除二叉树中的节点时，有3种情况
1> The node to delete has no children. That's easy: just release its resources and you're done. Time complexity O(1)
2> The node has a single child node. Release the node and replace it with its child, so the child holds t
浏览 1提问于2012-08-10得票数 0
2回答
我想就这个问题再提一次：
考虑随机快速排序算法的一种变化，其中选择支点是随机的，直到数组被分割时，较低的子阵L和较大的子阵G都包含3/4的数组元素。例如，如果随机选择的枢轴以L包含1/10元素的方式划分数组，则随机选择另一个pivot。分析了该算法的预期运行时间。
一开始，我把这个问题当作只是一个常规的快速排序问题，并提出了一个重复的问题：
T(n) = T(3/4n) + T(n/4) + Θ(n) (where Θ(n) comes from the partition)
如果我们有一个算法，它的分割总是1/4 : 3/4，那么这是有意义的。但是，我们在这里使用随机枢轴，并且每次不满足分
浏览 2提问于2020-04-10得票数 1
嘿，有谁能帮我确定一下复杂性吗？我们班给出的一个例子是
气泡分类
int main() {
int a[10] = {10,9,8,7,6,5,4,3,2,1};
int i,j,temp;
for (j=0;j<10;j++) {
for (i=0;i<9;i++) {
if (a[i] > a[i+1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
}
fo
浏览 3提问于2009-10-28得票数 2
我做了一个排序算法，但我想也许我只是重新发明了快速排序。
然而，我听说快速排序是O(N^2)个最坏情况；我想我的算法应该只有O(NLogN)个最坏情况。
这和快速排序是一样的吗？
该算法的工作原理是交换值，以便将所有小于中值的值移动到数组的左侧。然后它在每一端递归地工作。
该算法从i=0开始，j= n-1
I和j相互移动，如果需要，listi和listj将被交换。
下面是递归之前第一次迭代的一些代码：
_list = [1,-4,2,-5,3,-6]
def in_place(_list,i,j,median):
while i<j:
a,b = _list[i
浏览 1提问于2012-03-20得票数 3
回答已采纳
1回答
问题：
我必须分析排序的时间复杂性(使用快速排序)，一个整数值的列表，这些值几乎是排序的。
我做了什么？
我读过，，和。
但是，我没有发现任何明确提到使用快速排序对k排序数组排序的时间复杂性的内容。
由于快速排序算法的时间复杂度取决于选择枢轴的策略，并且由于数据几乎排序，所以有可能面临最坏的情况，为了避免最坏的情况，我使用了三个值的中值(第一、中、最后三个值)作为参考。
，我怎么想？
因为在一般情况下，快速排序算法的时间复杂度是O(n log(n))，而且正如前面提到的，“对于n的任何非平凡值，一个分治算法将需要很多O(n)的传递，即使数组几乎被完全排序”，
如果没有出现最坏的情况，我认为使用
浏览 0提问于2019-08-02得票数 0
使用randomize_quicksort()，我们知道平均情况复杂度是O(nlgn)，因为我们选择了随机过程的支点。然而，当我研究随机化选择算法时，我们也随机选择了类似于randomize_quicksort()的支点，在最坏的情况下，我们得到了O(n^2)的复杂性。我不明白是什么使它在二次时间内运行，尽管我们使用相同的策略来选择支点元素。
谢谢
浏览 3提问于2016-11-28得票数 1
.NET的List<T>.Sort文档提到了渐近运行时：
平均而言，这种方法是O(n log n)操作，其中n是计数的；在最坏的情况下是O(n^2)操作。
它还提到它是使用Array.Sort实现的，它在：上也有一个运行时声明
对于使用Heapsort和Quicksort算法排序的数组，在最坏的情况下，此方法是O(n log )操作，其中n是长度。
它还提到，内向排序在2012年开始与.NET 4.5一起使用。
为什么List<T>.Sort在最坏的情况下仍然是O(n^2)？或者，这只是文档中的一个错误，实际上是O(n log )？
浏览 0提问于2018-11-17得票数 4
回答已采纳
2回答
我真的不明白为什么我们不总是选择中值元素作为轴心。这可以在O(n)中完成，从而导致总运行时间为O( n )。
我只是假设在中值搜索的O(n)中可能隐藏了一个很大的常量。
浏览 1提问于2011-03-31得票数 4
6回答
快速排序最坏情况
、、
为了更好地理解它，我正在编写下面所需的程序。
快速排序的最坏情况运行时间是多少，什么可能导致这种更糟糕的情况性能？我们如何修改快速排序程序来缓解这个问题？
我知道它有最坏的情况，我知道它发生在O(n^2)唯一的最小或最大元素时。我的问题是，我如何修改程序来缓解这个问题。
一个好的算法就好了。
浏览 2提问于2010-10-26得票数 34
当pivot始终是子列表中第二小元素时，快速排序的时间复杂度。
还是O(NlogN)吗？
如果我解递归方程
F(N) = F(N-2) + N
= F(N-2(2)) + 2N -2
= F(N-3(2)) + 3N - (2+1)(2)
= F(N-4(2)) + 4N - (3+2+1)(2)
这是O(N^2)，但不知何故我怀疑我的答案，有人能帮我澄清一下吗？
浏览 5提问于2018-07-23得票数 0
回答已采纳
例如，当我们考虑函数f(n)=O(g(n))或类似于Big Theta时，我知道Big O是一个上界，Big Theta是一个紧界。但是，我们如何知道使用Big theta表示法而不是Big O表示特定的算法会更好呢？
例如，选择排序的时间复杂度是N^2的Big Theta而不是N^2的Big O，为什么？
浏览 0提问于2017-02-02得票数 0
如果我使用修改后的quicksort版本来查找数组中最小的kth项，为什么预期的运行时间O(n) (如Programming Pearls book所述)？
我使用的算法如下：
1) Runs quick sort on the array
2) If k is > the correct location of pivot, then run quicksort on the 2nd half.
Otherwise run it on the first half.
我的印象是，这将需要O(n * logn)的工作。
浏览 0提问于2013-07-29得票数 2
回答已采纳
6回答
快速排序优于堆排序
、、、、
堆排序的复杂度在最坏的情况下是O(nlogn)，而快速排序的复杂度是O(n^2)。但经验证据表明，快速排序更优越。为什么会这样呢？
浏览 0提问于2009-12-06得票数 48
回答已采纳
2回答
了解合并排序和快速排序的运行时间
、、、、
对于合并排序和快速排序，我都在尝试想出它们成为最坏情况的场景。如果我是正确的，合并排序的最坏情况是O(nlogn)，当所有东西都排序好的时候。快速排序的最坏情况是，当pivot位于最不理想的位置时，数组被排序，因此它变成O(n^2)。首先，我想知道这是否正确，如果不正确，请纠正我。我真正的问题是，如果快速排序的轴心在数组的中间，那么该数组必须是什么样子才能达到O(n^2)？
浏览 33提问于2017-03-09得票数 2
public static int partitionsimple_hoare(int[] arr,int l , int h){
int pivot = arr[l];
int i = l-1;
int j = h+1;
while(true){
do{
i++;
}while(arr[i]<pivot);
do{
j--;
}while(arr[j]>pivot);
if(i<j){
s
浏览 0提问于2017-09-21得票数 1
2回答
假设在快速排序的情况下，我们选择一个pivot作为数组的第一个元素。现在最好/最坏情况下的复杂度是O(n^2)，而在平均情况下是O(nlogn)。这是不是很奇怪(最好的情况下的复杂性大于最坏的情况下的复杂性)？
浏览 0提问于2013-06-05得票数 0
能否将快速排序的最坏情况时间复杂度从O(n2)更改为O(nlogn)，方法是修改(without converting it to mergsort)
浏览 5提问于2019-05-26得票数 0
3回答
在最坏的情况下，快速排序递归深度需要O(n)的堆栈空间。为什么在最坏的情况下，它不会导致大集的堆栈溢出？(颠倒顺序)
浏览 1提问于2012-10-19得票数 2
回答已采纳
4回答
尝试理解快速排序的复杂性
、、、、
我知道当轴心是最小或最大的元素时，最坏的情况会发生。然后，其中一个分区是空的，我们对N-1个元素重复递归
而是如何计算到O(N^2)
我已经读了几篇文章，但仍然不能完全理解它。
同样，最好的情况是轴是数组的中值，并且左右部分的大小相同。但是，值O(NlogN)是如何计算的呢？
浏览 1提问于2016-10-28得票数 1
4回答
假设我有两个案例：
案例1:我总是选择第一个元素作为枢轴。在这种情况下，最糟糕的情况是O(n2)已经对数组进行排序或反向排序。
案例2:我选择一个随机元素作为枢轴。在这里，当随机枢轴总是子阵中的最大或最小元素时，O(n2)可能是最坏的情况。
如果给我们一个随机数组，那么P(O(n2)在情况1中)= P(O(n2)，在第2种情况下)，难道我不能争辩吗？因为直觉上P(排序数组或反向排序数组)=P(随机枢轴总是子数组中的最大或最小元素)？
如果是这样的话，第二种情况有什么好处，因为我们需要额外的努力来选择随机枢轴吗？我们需要第二个案例，只有当数据将遵循一定的模式。我说的对吗？请开导。
浏览 0提问于2016-06-28得票数 0
我知道空间复杂度从O(n)下降到O(log )。但是时间复杂度又如何呢？执行Quick Sort的时间是否与常规版本相同？
浏览 0提问于2011-11-06得票数 0
好吧，我想对给定的3值使用快速排序，不管是什么值，我如何才能得到最坏的情况，也就是9操作？
有没有人可以画一棵树，并展示它是如何显示nlogn和n^2操作的？我试着在网上找过了，但我还是没能画出一幅合适的画来说明这一点。
浏览 7提问于2016-09-07得票数 0
1回答
我正在为即将举行的考试做准备。提供给我的图表具有以下算法复杂性，对具有N个节点和E边的图的邻接列表进行了总结。
查找边- O(E/N)
插入边- O(E/N)
删除edge - O(E/N)
节点- O(E/N)的枚举边
我理解邻接列表是什么-我们使用一个列表数组来存储与每个顶点相邻的顶点。但为什么这些行动是O(E/N)？在我看来，如果我们用一个图来绘制每个可能的边(例如，如果图是无向的，我们有n(n - 1)/2边)，那么数组中的每个列表都会有N-1项来存储每一个其他节点。
在我看来，这将是“最坏的情况”，不是吗？我不明白边缘和节点的比率是如何得到的。
谁能解释一下吗
浏览 0提问于2019-05-01得票数 0
回答已采纳
1回答
就我个人而言，我认为中位数不是真正的中位数。对，是这样?
那么，如果上面的陈述是真的，为什么要用中值的中位数作为支点来划分数组，以求出第k个最小元素的时间复杂度最坏的情况是O(n)？"n“是元素的数目。
浏览 10提问于2014-04-07得票数 0
2回答
我们知道，在快速排序中，最坏的情况是O(n^2)，我可以解决以下数组： 1 2 3 4 5 6 7 8 9 10 当我把n的值放在最坏情况的方程中时，答案是100，但在试运行时，它可以在51步内求解。这有很大的不同，原因是什么？
浏览 22提问于2019-12-15得票数 0
2回答
基排序的时间复杂度为O(kn)，其中n是要排序的键数，k是键的长度。类似地，trie中插入、删除和查找操作的时间复杂度为O(k)。但是，假设所有元素都是不同的，难道不是k>=log(n)吗？如果是这样，则意味着基排序的渐近时间复杂度为O(nlogn)，等于快速排序，而trie操作的时间复杂度为O(logn)，等于平衡二叉树的时间复杂度。当然，常数因素可能有很大的不同，但渐近时间复杂性不会。这是真的吗?如果是这样的话，基数排序和尝试比其他算法和数据结构有其他优势吗？
编辑：
Quicksort和它的竞争对手执行O(nlogn)比较；在最坏的情况下，每个比较将花费O(k)时间(键只在最后检查
浏览 3提问于2011-07-31得票数 3
回答已采纳
4回答
根据，基于分区的选择算法(如quickselect )具有O(n)的运行时，但我对此并不信服。有人能解释一下为什么是O(n)吗
在通常的快速排序中，运行时是O(n log n)。每次我们将分支划分为两个分支(大于支点和小于支点)时，我们都需要在中继续处理两个分支，而quickselect只需要处理一个分支。我完全理解这些观点。但是，如果您在二进制搜索算法中考虑，在我们选择中间元素之后，我们也只搜索分支的一个一侧的。那么，这是否使算法O(1)呢？不，当然，二进制搜索算法仍然是O(log N)而不是O(1)。这与二进制搜索树中的搜索元素也是一样的。我们只搜索一个端，但我们仍然考虑O(log n)而
浏览 4提问于2012-01-09得票数 47
回答已采纳
1回答
中位快速排序中值的最坏情况时间复杂度是多少(枢轴是由需要O(n)时间查找的中间值的中位数决定的)？
浏览 1提问于2014-11-22得票数 0
回答已采纳
1回答
我正在研究CLRS的第三章，它是关于运行时间的，我想通过一些例子来研究。因为我没有报名参加算法课，所以我需要求助于www。
1) n^2 =大欧米茄(n^3)
我认为这条语句是错误的:如果最佳情况运行时间为n^3，则算法不能是n^2，。即使是最好的情况也比这慢。
2) n+ log n=大-Theta (n)
我认为这个说法是正确的，我们可以忽略log的下一项，这给了我们一个最坏的运行时间大-哦( n )。和一个最好的运行时间的大欧米茄(n)。不过，我不太确定。如能作出更多澄清，将不胜感激。
3) n^2 log n=大-Oh (n^2)
我认为this.statement是
浏览 2提问于2012-11-25得票数 0
回答已采纳
我必须实现快速排序，但最坏的情况是O(n log )。我可以实现在文献中发现的任何东西，但到目前为止，我只能找到一个叫做BSort的东西，它对我来说没有多大意义。有没有人知道对容易实现的算法的引用？还是关于这个问题的论文？
是的，这是为了上课，但这部分我可以得到帮助，我只需要自己实现它。
谢谢
浏览 4提问于2014-09-25得票数 0
回答已采纳
1回答
我一直在尝试实现Hoare分区方法，但我和计算机似乎都不能理解它，因为它是在科尔曼和维基百科中编写的。这两个源代码中的算法看起来如下所示：
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
j := j - 1
while A[j] > pivot
do
i := i + 1
while A[i] < pivot
浏览 1提问于2015-12-20得票数 0
2回答
最近我有一个朋友要求我解决他在求职面试中看到的一个问题：
N个元素被分成k个数组。找到一个算法，返回在(k，log，N)时间内任何元素是否相同。
请不要给出答案，我真的很想自己解决它。
我的问题是:是否有一个类似regexpal的网站来测试我算法的复杂性？如果没有，是否有人对如何真正发现复杂性有任何建议？
我有一个大致的想法，但我上次尝试做这样的问题已经有一段时间了。
编辑:新的问题添加到这里。当K为1时，K Log N与N log N相比是怎样的？--它只是log N，比O(n)更有效，但如果K >= n比N log N还要差，对吗？
浏览 4提问于2012-11-13得票数 3
回答已采纳
1回答
如何使用快速排序从未排序的数组中找到k个最小元素(除了排序和获取k个最小元素之外)？最坏的运行时间是相同的O(n^2)吗？
浏览 1提问于2014-07-03得票数 0
回答已采纳
5回答
如何分析算法？是什么使quicksort具有O(n^2)最坏情况的性能，而merge sort具有O(n log(n))最坏情况的性能？
浏览 1提问于2010-04-23得票数 5
回答已采纳
我试图编写一个快速排序程序，结果如下所示。它是用Javascript编写的，它明确地对列表进行排序。然而，我意识到我在网上看到的大多数快速排序算法与此非常不同，我觉得我的算法与我在网上看到的相比太容易编程了，因此我产生了怀疑。
我完全意识到这个算法在内存方面效率非常低，因为它创建了新的列表(新的内存分配)，而不是进行就地排序。但我更感兴趣的是把这个算法教给一个朋友，这就是为什么我试图编写尽可能简单的版本。所以我的问题是，这是快速排序算法的合法(正确实现)吗？或者它做了其他的事情？(请记住:我不是在问这是否有效，因为我知道它不是有效的！)
另外，这个算法的复杂度是多少？我试着计算它，我的分析是:
浏览 0提问于2016-09-27得票数 0
5回答
在尝试评估程序的性能时，我总是将sort()函数视为性能最差的-n^2函数。然而，我偶然看到了维基百科的一个页面：
它指出GNU C Library sort()首先使用某种称为Introsort的混合排序算法，然后执行插入排序。Introsort的对应页面声称该算法的最坏情况性能为nlogn。但是，由于我不熟悉这个算法，所以我仍然对sort()有以下担忧：
1) GNU sort()使用的混合算法能保证O(nlogn)的性能吗？如果是这样，nlogn的恒定开销能有多大？
2)有没有其他实现可能导致sort()的性能比这个更差(或者更好，这会更好)？
编辑:回复Kevin:提到的sort()
浏览 3提问于2011-06-04得票数 4
回答已采纳
3回答
我知道最坏的/avg/最好的情况是用来确定算法的复杂度时间成一个函数，但是它是如何用于渐近分析的呢？我理解上/紧/下界(大O，大欧米茄，大θ)是用来比较两个函数，并看到它的极限(增长)是从另一个角度看的，随着n的增加，但我很难看出最坏/avg/最佳情况大O和渐近分析之间的区别。把我们的最坏/avg/最佳情况大O计算到渐近分析和测量界，我们到底能得到什么呢？我们会用渐近分析来具体比较最坏/avg/最佳情况下的两种算法吗？如果是这样的话，我们是否对算法1和算法2使用函数f(n)，或者对算法1为f(n)的每一种算法进行单独的渐近分析，并试图找到一些c*g(n)，使得=> f(n)和c*g(n)
浏览 5提问于2013-08-11得票数 0
回答已采纳
2回答
快速排序的最佳情况是n log(n)，但每个人都使用Big-O表示法将最佳情况描述为O(n log (n))。根据我对符号的理解，Quicksort有Big-Omega(n log (n))和O(n^2)。这是正确的，还是我误解了Big-Omega符号？
浏览 2提问于2018-05-22得票数 0
5回答
我正在学习算法分析。我很难理解O、Ω和Θ之间的区别。
定义它们的方式如下：
f(n) = O(g(n))意味着c · g(n)是f(n)的上界。因此，存在一些常量c，使得f(n)总是≤c · g(n)，对于足够大的n (即，对于某些常数n0来说，n ≥ n0 )。
f(n) = Ω(g(n))意味着c · g(n)是f(n)的下界。因此，存在一些常量c，因此对于所有n ≥ n0，f(n)总是≥c · g(n)。
f(n) = Θ(g(n))意味着c1 · g(n)是f(n)的上界，而c2 · g(n)是f(n)上的下界，对于所有n ≥ n0都是这样。因此，存在常数c1和c2
浏览 8提问于2009-12-25得票数 34
回答已采纳
2回答
查找元素小于S的子集
、、、
我必须为以下问题找到一个算法：
输入是自然数的两个数字S和k，以及n对向不同数的未排序集合。
在O(n)中决定是否有一个k数的子集与<=S相加。注意:k不应该是时间复杂性的一部分。
algorithm({x_1, ..., x_n}, k, S):
if exists |{x_i, ..., x_j}| = k and x_i + ... x_j <= S return true
我找不到具有时间复杂度O(n)的解。
我所能得到的是O(kn)，当我们搜索k乘以最小值，和是向上的：
algorithm(a={x_1, ..., x_n}, k, S):
sum = 0
浏览 1提问于2019-02-27得票数 1
回答已采纳
2回答
快速排序的内存复杂性
、、、、
Quicksort的空间复杂度为 O(logn)。
但是- Quicksort可以在不使用任何额外内存的情况下进行处理:在每次迭代时，在分区过程中，条目最终被交换到基于所使用的枢轴的左分区和右分区中。这种递归交换--从而形成--分区可以在列表本身上完成，而不需要在递归调用干扰的一个级别上进行分区，也不需要对不同级别的干扰调用进行快速排序。
Quicksort中额外内存的用途是什么？
蒂娅。
//=。
编辑：
与注释/答案中的堆栈空间一致
不过，
在预期的情况下，Quicksort在O(nlogn)时间内执行--在每个递归级别形成(几乎)大小相等的分区。
所使用的堆栈空间是一棵二叉树，在最佳情况
浏览 2提问于2015-04-20得票数 6
回答已采纳
2回答
渐近符号有缺陷吗？
、、、
任何算法的最佳情况复杂度都是该算法完成其任务所需的最短时间。我们知道，合并排序、快速排序等算法的最佳情况复杂度是Ω(n log(n))，它定义了这些算法的下界。
我们知道，在渐近符号中-
O(n) + O(n log(n)) = O(n log(n))
还有，
Ω(n) +Ω(n log(n)) =Ω(n log(n))
因此，如果在这些排序算法中，我们首先在O(n)时间内遍历整个数组，以确定数组是否已经按升序或降序排序，则它们的平均情况和最坏情况的复杂性将保持不变。但它们的最佳情况复杂性现在将成为Ω(n)。
从逻辑上讲，在我理解这些渐近符号的方法上肯定有一个缺陷，否则，当渐近符号被开发或流行
浏览 2提问于2021-02-01得票数 2
如果一个函数的复杂度为O(N)，并且在If语句中调用它，那么它仍然是O(1)吗？
例如：
f(x);
if (f2(x))
f3(x);
其中f(x)是O(N)，f2(x)是O(N)，f3(x)是O(Nlog2N)。
那么，在条件为真的最坏情况下，这个片段的总体复杂度会是O(Nlog2N)吗？
浏览 0提问于2012-10-21得票数 1
回答已采纳
维基百科的这篇文章建议O(logn)是in place sort和的时空复杂度这个面试站点表明它是O(n)。我想答案是O(n)，但想知道我是否正确。
浏览 0提问于2013-02-23得票数 5
回答已采纳
3回答
提取k个最大元素
、、、
如果我有n个整数，是否可以在O(k+logn)时间内列出n个值中k个最大的元素？我得到的最接近的结果是构造一个最大堆并提取最大k次，这需要O(klogn)时间。我也在考虑使用顺序遍历。
浏览 0提问于2017-10-03得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
