排序和排序的复杂度不同？
排序是将一组数据按照特定规则进行排列的过程，排序的复杂度是衡量排序算法执行效率的指标。
排序的复杂度可以分为时间复杂度和空间复杂度两个方面。
- 时间复杂度：表示排序算法执行所需的时间。常见的时间复杂度有：
- 最好情况时间复杂度（Best Case Time Complexity）：表示在最理想情况下，排序算法执行所需的最少时间。
- 最坏情况时间复杂度（Worst Case Time Complexity）：表示在最不利情况下，排序算法执行所需的最长时间。
- 平均情况时间复杂度（Average Case Time Complexity）：表示在所有可能情况下，排序算法执行所需的平均时间。
- 空间复杂度：表示排序算法执行所需的额外空间。常见的空间复杂度有：
- 原地排序（In-place Sorting）：排序算法只需要使用常数级别的额外空间，不需要额外的辅助空间。
- 非原地排序（Not In-place Sorting）：排序算法需要使用额外的辅助空间来存储中间结果。
排序的复杂度不同会影响排序算法的选择和应用场景。一般来说，我们希望排序算法具有较低的时间复杂度和空间复杂度，以提高排序效率和节省资源消耗。
以下是一些常见的排序算法及其复杂度：
- 冒泡排序（Bubble Sort）：
- 时间复杂度：最好情况O(n)，最坏情况O(n^2)，平均情况O(n^2)
- 空间复杂度：原地排序
- 插入排序（Insertion Sort）：
- 时间复杂度：最好情况O(n)，最坏情况O(n^2)，平均情况O(n^2)
- 空间复杂度：原地排序
- 选择排序（Selection Sort）：
- 时间复杂度：最好情况O(n^2)，最坏情况O(n^2)，平均情况O(n^2)
- 空间复杂度：原地排序
- 快速排序（Quick Sort）：
- 时间复杂度：最好情况O(nlogn)，最坏情况O(n^2)，平均情况O(nlogn)
- 空间复杂度：原地排序
- 归并排序（Merge Sort）：
- 时间复杂度：最好情况O(nlogn)，最坏情况O(nlogn)，平均情况O(nlogn)
- 空间复杂度：非原地排序
- 堆排序（Heap Sort）：
- 时间复杂度：最好情况O(nlogn)，最坏情况O(nlogn)，平均情况O(nlogn)
- 空间复杂度：原地排序
- 基数排序（Radix Sort）：
- 时间复杂度：最好情况O(d(n+r))，最坏情况O(d(n+r))，平均情况O(d*(n+r))
- 空间复杂度：非原地排序
排序算法的选择取决于数据规模、数据特点、排序稳定性要求等因素。在实际应用中，可以根据具体需求选择合适的排序算法。
腾讯云相关产品和产品介绍链接地址：
- 云服务器（CVM）：https://cloud.tencent.com/product/cvm
- 云数据库 MySQL 版（CDB）：https://cloud.tencent.com/product/cdb
- 云原生应用引擎（TKE）：https://cloud.tencent.com/product/tke
- 云存储（COS）：https://cloud.tencent.com/product/cos
- 腾讯云区块链服务（Tencent Blockchain）：https://cloud.tencent.com/product/tencentblockchain
相关·内容
我知道空间复杂度从O(n)下降到O(log )。但是时间复杂度又如何呢？执行Quick Sort的时间是否与常规版本相同？
浏览 0提问于2011-11-06得票数 0
/*
Returns true is the two strings are permutations of each other.
Time Complexity; O(nlog n) -> because of the java utils array sort
Space Complexity; O(1)
*/
public boolean isPermutationOptimized(String one, String two) {
if (one.length() != two.length()) {
return
浏览 17提问于2021-10-05得票数 0
回答已采纳
2回答
渐近分析问题
、、、
我在geeksforgeeks.org上发现了几个我似乎无法理解的问题(#1和#3)。我希望有人能帮我弄清楚答案：
澄清true/valid或false
1. QuickSort的时间复杂度为Θ(n^2)
我的回答是正确的，但它是错误的，为什么？如果快速排序的时间复杂度为O(n^2)，并且我们知道快速排序(g(N))={ f(n)，其中c1*g(n) <= f(N) <=c2*g(n)和n >= n0}，那么这不是证明它是真的吗，因为c2*g(n)作为上界可以等于f(n)？
2. QuickSort的时间复杂度为O(n^2) -真
3.所有计算机算法的时间复杂度可以写成Ω(1
浏览 1提问于2014-01-23得票数 3
4回答
快速排序时间复杂度
、、、、
我最近读到了关于时间复杂性的文章，我发现快速排序的平均时间复杂度为O(nlog(n))。
问题1:我不明白的是，日志(N)是如何在时间复杂性方程中出现的？
问题2:为什么我们总是使用大O表示法来寻找算法的时间复杂性？我们为什么不用其他符号呢？
浏览 7提问于2012-08-15得票数 1
回答已采纳
这个问题已经出现在我的算法课上了。我的想法是：
我认为答案是否定的，具有O(n)的最坏时间复杂度的算法并不总是比O(n^2)的最坏时间复杂度的算法更快。
例如，假设我们有总时间函数S(n) = 99999999n和T(n) = n^2，那么很明显，S(n) = O(n)和T(n) = O(n^2)，但对于n< 99999999，T(n)比S(n)更快。
这样的推理有效吗？我有点怀疑，虽然这是一个反例，但它可能是错误想法的反例。
非常感谢！
浏览 5提问于2016-06-15得票数 3
回答已采纳
基于和和上的问题，算法的空间复杂度是解决问题所需的空间，包括输入占用的空间，辅助空间是算法除输入本身需要的任何额外存储空间。
现在，我得到气泡排序的辅助空间是O(1)，因为它只需要一个变量来跟踪我们正在进行的交换的数量，以查看列表何时排序(如果我错了，请纠正我)，但是为什么说气泡排序的总空间复杂度也是O(1)？
考虑到输入本身，它不是应该是O(n)吗？
浏览 1提问于2021-03-21得票数 2
回答已采纳
1回答
为什么自顶向下合并排序的最佳情况的时间复杂性在O(nlogn)中？我认为自上而下合并排序的最佳情况是1，只需比较1次。在最坏情况、最佳情况和平均情况下，自下而上合并排序的时间复杂度如何？
还有一个问题是，为什么每次迭代都要取O(n)？有人能帮忙吗？
浏览 1提问于2012-10-12得票数 3
7回答
合并排序时间和空间复杂度
、、、
让我们以合并排序的实现为例
void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m); ------------(1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);
这种合并排序的时间复杂度是O(n lg(n))。并行化(1)和(2)会带来实际收益吗？从理论上讲，在并行化它们之后，您也将在O(n lg(n))中结束。但实际上我们能得到任何收益吗？
( b)这种合并排序的空间复杂性在这
浏览 0提问于2012-04-26得票数 46
回答已采纳
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
回答已采纳
2回答
我编写了一个函数来查找目标值在给定数组中应该插入的位置。我们假设数组有不同的值，并按升序排序。我的解决方案必须在O(log )时间复杂度内
public static int FindPosition(int[] A, int target) {
int a = A.length / 2;
System.out.println(a);
int count = a;
for (int i = a; i < A.length && A[i] < target; i++) {
count++;
}
for
浏览 3提问于2017-04-24得票数 1
4回答
路径和
给定二叉树和和，找到每条路径的和等于给定和的所有根到叶路径。
例如，： sum = 11。
5/4 8//2 -2 1
答案是：
[ 5、4、2、5、8、-2 ]
我个人认为，时间复杂度= O(2^n)，n是给定二叉树的节点数。
谢谢Vikram Bhat和David Grayson，紧时间复杂度= O(nlogn)，n是给定二叉树中的节点数。
算法对每个节点进行一次检查，从而导致O(n)
“向量one_result( subList );”每次都会将整个路径从subList复制到one_result，这会导致O(logn)，因为高度是O(logn)。
浏览 6提问于2014-07-06得票数 4
回答已采纳
我想知道在JavaScript中这种快速排序实现的时间和空间复杂性是什么。它有比理想的时间和空间复杂度更快的排序还是相同的？(理想的快速排序在最坏的情况下有TC O(n^2)和SC O(log n) )
function quickSort(arr)
{
if(arr.length == 1)
return arr
let pivot = arr[arr.length-1];
let left = [], right= [];
for(let i=0; i<arr.length-1; i++)
arr[i] &l
浏览 4提问于2022-10-26得票数 -2
回答已采纳
我了解到，在Stream中，方法 sort ()可能使用合并排序(mergesort)。
然后将时间复杂度用于这类排序：
BigΘ (n (log n) )-最佳
BigΩ (n (log n) )-平均
大O (n (log n) )-最坏的
空间完备性-O (n) -最差
如果我们使用自定义对象的多个字段进行排序，使用then.comparing()构建比较链，那么时间复杂度是什么？
在这种情况下，你如何计算时间复杂度？
浏览 3提问于2021-04-20得票数 0
回答已采纳
C#的List<T>.Sort()的时间复杂度是什么
我猜是o(N)
但在我搜索了很多次之后，我没有得到任何准确的结果。
浏览 7提问于2012-03-08得票数 17
回答已采纳
存在一个与数组相关的问题，要求时间复杂度为O(n)，空间复杂度为O(1)。
例如，如果我使用Arrays.sort(arr)，并将for循环用于一个pass循环：
public static int hello(int[]A){
Arrays.sort(A);
for(int i=0;i<A.length;i++){
....................
}
return ....;
}
因此，循环将花费O(n)时间。我的问题是：Arrays.sort()会花费更多时间吗？如果我使用Arrays.sort()，这一次的复杂性还会是O(n)吗？Arrays.s
浏览 0提问于2014-03-21得票数 26
回答已采纳
1回答
对于一个算法的平均时间复杂度，您使用了什么符号？在我看来，正确的方法是使用大θ来引用一组结果(即使特定的尝试可能不同)。例如，平均数组搜索将是n+1(Θ)/2。
是这样的吗？
对平均搜索时间的解释是/2:在n个第一个整数的访问时间和为n(n+1)/2的情况下，大量随机访问数组的平均时间为(n (n+1)/2 )/n =(n+1)/2，在这种情况下，我认为Θ(n+1)/2将是平均访问时间。这(对我来说)很有意义，但由于我对渐近符号(以及一般的编程)还不熟悉，我想知道这是否是一种常见的做法。
我之所以问这个问题，是因为我很困惑地发现，在像http://bigocheatsheet.com这样的页面
浏览 0提问于2013-05-11得票数 1
回答已采纳
当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
回答已采纳
4回答
我遇到了如下的算法难题：
给定(名称，开始时间，结束时间)形式的事件数组，例如
(a，1，6) (b，2，4) (c，7，8) ...
根据事件的开始时间对事件进行排序。我被要求将事件转换为另一种形式(名称，时间)，
例如(a，1) (b，2) (b，4) (a，6) (c，7) (c，8)
请注意，每个事件现在被分成两个事件，并且它们需要按时间排序。
最天真的方法是O(n log n)，我还想到了其他几种方法，但没有一种方法比O(n log n)更快。
有人知道解决这个问题最省时省力的方法吗？
浏览 0提问于2014-09-12得票数 0
2回答
壳牌排序的时间复杂性？
、、、
首先，下面是我的Shell排序代码(使用Java)：
public char[] shellSort(char[] chars) {
int n = chars.length;
int increment = n / 2;
while(increment > 0) {
int last = increment;
while(last < n) {
int current = last - increment;
while(current >= 0) {
浏览 0提问于2012-10-07得票数 7
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
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
