Arrays.sort() 会增加时间复杂度和空间时间复杂度吗? [英] Will Arrays.sort() increase time complexity and space time complexity?

问题描述

有一个数组相关的问题，要求时间复杂度为O(n)，空间复杂度为O(1).

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).

如果我使用 Arrays.sort(arr)，并使用 for 循环到一次循环，例如:

If I use Arrays.sort(arr), and use a for loop to one pass loop, for example:

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.sort() 会占用更多空间吗?

So the loop will cost O(n) time. My question is: will Arrays.sort() cost more time? If I use Arrays.sort(), will this time complexity still be O(n)? And will Arrays.sort() cost more space?

推荐答案

我假设您在这里谈论的是 Java.

I am assuming you are talking about Java here.

所以循环将花费 O(n) 时间，我的问题是 Arrays.sort() 会花费更多时间吗?

So the loop will cost O(n) time, my question is that will Arrays.sort() cost more time?

是，Arrays.sort(int[]) 在我知道的所有 Java 标准库实现中，都是基于比较的排序的一个例子，因此 必须具有最坏情况复杂度Ω(n log n).特别是，Oracle Java 7 对整数重载使用了双轴快速排序变体，它实际上具有 Ω(n²) 最坏情况.

Yes, Arrays.sort(int[]) in all Java standard library implementations that I know, is an example of a comparison-based sort and thus must have worst-case complexity Ω(n log n). In particular, Oracle Java 7 uses a dual-pivot quicksort variant for the integer overloads, which actually has an Ω(n²) worst case.

Arrays.sort() 会占用更多空间吗?

and will Arrays.sort() cost more space?

它很可能会使用 ω(1) 空间(这意味着另一个是，空间使用不是 O(1)).虽然仅使用恒定的额外空间来实现基于比较的排序并非不可能，但这是非常不切实际的.

In all likelihood it will use ω(1) space (which means another yes, the space usage is not O(1)). While it's not impossible to implement a comparison-based sort with only constant extra space, it's highly impractical.

也就是说，在某些条件下，可以在线性时间内对特定类型的数据进行排序，例如:

That said, under certain conditions it is possible to sort specific types of data in linear time, see for example:

• http://en.wikipedia.org/wiki/Counting_sort
• http://en.wikipedia.org/wiki/Pigeonhole_sort
• http://en.wikipedia.org/wiki/Radix_sort

对于恒定范围的输入整数(例如，如果 abs(A[i]) <= C 对于某些常量 C)，那么计数排序和基数排序实际上只使用 O(n) 时间和 O(1) 空间，所以这可能有用.

With a constant range of input integers (for example if abs(A[i]) <= C for some constant C), then counting sort and radix sort use indeed only O(n) time and O(1) space, so that might be useful.

这篇关于Arrays.sort() 会增加时间复杂度和空间时间复杂度吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！