排序和排序的复杂度不同？

文章/答案/技术大牛

发布

3回答

排序算法的空间复杂度怎么可能是O(1)？

algorithm、sorting、time、complexity-theory、space

我正在学习不同的排序算法及其时间/空间复杂度，并看到冒泡排序和插入排序等算法的空间复杂度为O(1)。这让我感到奇怪，因为最低的空间复杂度肯定是O(n) (例如，存储数据集所需的内存，仅此而已)？

浏览 1提问于2017-05-10得票数 7

回答已采纳

2回答

关于尝试排序和基排序的效率

big-o、time-complexity、trie、radix-sort

基排序的时间复杂度为O(kn)，其中n是要排序的键数，k是键的长度。类似地，trie中插入、删除和查找操作的时间复杂度为O(k)。但是，假设所有元素都是不同的，难道不是k>=log(n)吗？如果是这样，则意味着基排序的渐近时间复杂度为O(nlogn)，等于快速排序，而trie操作的时间复杂度</e

浏览 3提问于2011-07-31得票数 3

回答已采纳

4回答

冒泡排序与gnome排序的区别

algorithm、sorting

冒泡排序和gnome排序在最差、最好和平均情况下具有相同的复杂度。冒泡排序和gnome排序(不是它们的名字...)有什么不同？

浏览 1提问于2012-03-04得票数 6

1回答

选择排序的最佳时间复杂度

algorithm、time-complexity、selection-sort

为什么选择排序的最佳时间复杂度是O(n)，而插入排序和冒泡排序的最佳时间复杂度是O(N)？它们的平均时间是相同的。我不明白为什么最好的情况时间是不同的。会很感谢你的帮助。

浏览 0提问于2017-04-09得票数 7

回答已采纳

2回答

堆排序空间复杂度的计算

algorithm、data-structures、heapsort

我知道堆排序的空间复杂度是O(1)。但是对于一个递归程序，在计算空间复杂度时，它的深度--也就是它进行的递归调用的次数--也是计数的。因此，相同代码的迭代和递归方法的空间复杂度不同。那么，递归处理堆排序的空间复杂度是多少呢？

浏览 2提问于2019-01-12得票数 0

回答已采纳

3回答

仅使用运行时数据查找大O时间复杂度函数

java、algorithm、sorting、time-complexity、big-o

在我为算法类准备的一个项目中，我们必须运行5种未知类型的不同排序方法，并使用加倍方法收集每个方法的运行时间数据。然后，我们必须使用运行时间的比率来计算时间复杂度的函数。使用的排序方法有选择排序、插入排序、合并排序和快速排序(随机和非随机排序)。我们必须通过实证分析来确定在程序中的</e

浏览 0提问于2018-10-03得票数 2

回答已采纳

24回答

如何在单循环中对数组进行排序？

algorithm、sorting、quicksort、insertion-sort、heapsort

所以我经历了不同的排序算法。但是几乎所有的排序算法都需要2次循环来对数组进行排序。冒泡排序和插入排序的时间复杂度在最佳情况下为O(n)，而在最坏情况下为O(n^2)，这也需要2次循环。有没有办法在单个循环中对数组进行排序？

浏览 21提问于2015-08-12得票数 7

3回答

numpy、time-complexity

在这里，我试图理解numpy数组索引的复杂性。np.sort(A)和A[b]在时间完成度上有什么不同？

浏览 32提问于2020-07-31得票数 1

1回答

合并K排序列表:效率

list、algorithm、sorting、merge、n-way-merge

我收到了一份作业，要求我有效地将包含N个元素的K排序列表合并到一个排序列表中。我偶然发现的方法是使用Min-堆对K列表中的元素进行排序，或者使用方法(成对合并)。中的注释告诉我们，除法和征服法的时间复杂度为O(NK)，而Min-堆方法的时间复杂度为O(NK)，两者的空间复杂度相同。我还访问了许多其他线程，但我无法清晰地看到图片。怀疑和</

浏览 2提问于2020-03-31得票数 0

回答已采纳

1回答

空间复杂性与辅助空间复杂性

algorithm、sorting、space-complexity

例如，合并排序、堆排序和插入排序的辅助空间为O(1)，而合并排序、插入排序、堆排序的空间复杂性为O(n)。那么，如果有人问我合并排序、堆排序或插入排序的空间复杂度是多少，那么我该怎么告诉他们O(1)或O(n)呢？另外，在选择排序的情况下，我看到它的空间复杂度是O(1)，它是

浏览 0提问于2018-06-26得票数 2

回答已采纳

1回答

基排序(包括重复键)的时间复杂性

data-structures

假设我们有一个数组，在[1,n^6]的范围内包含n个不同的整数，我们希望通过基排序对它进行排序，它使用了一个具有\theta f(n)时间复杂度的辅助算法。我知道基排序的时间复杂度是theta(n^6f(n))，但是如果我们有一些重复的键，那么时间复杂度是多少？我们能猜不猜？如果有人能帮我，我会很感激的。

浏览 3提问于2022-06-17得票数 0

5回答

哪种排序算法的最坏情况复杂度与它们的平均情况不同？

algorithms、sorting

我已经做了一段时间的分类工作了，但我不能把这两个问题分开，我有点搞混了.谁来帮帮忙 ( a)哪些排序算法的最坏情况复杂度与它们的平均情况不同？( b)哪种排序算法的最佳案例复杂度与它们的平均情况不同？

浏览 0提问于2011-05-20得票数 -1

4回答

有线性时间复杂度和O(1)辅助空间复杂度的排序算法吗？

algorithm、sorting、time-complexity、space-complexity

有线性时间复杂度排序算法和O(1)辅助空间复杂度排序算法来排序正整数列表吗？我知道和具有线性时间复杂度(以k为常数时分别为O(kn)和O(n+k) )，但它们都具有O(n+k)辅助空间复杂度。最好举这样的例子。

浏览 12提问于2020-08-24得票数 3

回答已采纳

1回答

堆排序的辅助空间与空间复杂度的差异？

algorithm、sorting、heapsort、space-complexity

堆排序的辅助空间与空间复杂度的差异？如所解释的我搜索了堆排序的<

浏览 4提问于2017-06-01得票数 3

回答已采纳

1回答

C++库中未使用堆排序

c++、sorting、quicksort、heapsort

由于堆排序在所有情况下，即最好情况、平均情况和最坏情况下的时间复杂度都是O(nlogn)。而快速排序在最坏情况下的时间复杂度为O(n2)。那么，尽管在最坏的情况下复杂度较低，为什么堆排序不在C++库中实现，而是在快速排序中实现。

浏览 3提问于2017-10-01得票数 0

1回答

用快速排序算法对K排序阵列排序的时间复杂度

algorithm、sorting、time-complexity、quicksort

问题：我做了什么？但是，我没有发现任何明确提到使用快速排序对k排序数组排序的时间复杂性的内容。由于快速排序算法的时间复杂度取决于选择枢轴的策略，并且由于数据几乎排序，所以有可能面临最坏<em

浏览 0提问于2019-08-02得票数 0

1回答

按键唯一的推力排序和推力的步长复杂度

gpu、thrust

我在推力中使用sort和unique by key函数。我只是想知道在推力中排序函数的步长复杂度是多少，唯一的按键排序函数的功和步长复杂度是什么。根据我的知识，我认为排序的工作复杂度是O(NlogN)。但是我不知道unique_by_key操作是什么

浏览 1提问于2012-04-03得票数 1

1回答

快速排序和合并排序是一样的吗？

algorithm、sorting、quicksort

现在我知道任意实例在某种程度上与算法中的.I平均枢轴值有关。但是我不明白算法是如何定义任意实例的。还有，合并排序和快速排序是否相同，因为它们都有相同的时间复杂度?如果不同，有人可以给我快速排序的任意实例吗？

浏览 1提问于2014-01-21得票数 0

2回答

O(n)时间复杂度中的波排序

python、sorting

波按时间复杂度对进行排序O(n)如果输入为1, 3, 4, 2, 7, 8，则期望1, 3, 4, 2, 7, 8的输出。产出可能因执行情况不同而有所不同。主要目标是在阵列中有一个波峰和波谷，并在O(n)中这样做。

浏览 3提问于2019-10-08得票数 0

1回答

排序日志(n)排序子序列在O(n日志日志n)

sorting、time、complexity-theory、mergesort

我有日志( n)成对排序的子序列(长度可能不同)，我需要在O(n日志日志n)中排序，但我不知道如何排序。我已经考虑过使用合并排序，但是时间复杂度为O(n log )。

浏览 0提问于2018-11-04得票数 0

回答已采纳

点击加载更多

排序算法的空间复杂度怎么可能是O(1)？

关于尝试排序和基排序的效率

冒泡排序与gnome排序的区别

选择排序的最佳时间复杂度

堆排序空间复杂度的计算

仅使用运行时数据查找大O时间复杂度函数

如何在单循环中对数组进行排序？