java - Arrays.sort() 会增加时间复杂度和空间时间复杂度吗？

Question

有个数组相关的问题，要求时间复杂度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.sort() 会占用更多空间吗？

Answer 1

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

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

是， Arrays.sort(int[]) 在我所知道的所有 Java 标准库实现中，是基于比较的排序的一个示例，因此 must have worst-case complexity Ω(n log n) .特别是，Oracle Java 7 为整数重载使用了双枢轴快速排序变体，这实际上有一个Ω(n²)最坏的情况。

and will Arrays.sort() cost more space?

十有八九会用到ω(1)空间(也就是说又是是，空间使用不是O(1))。虽然仅用恒定的额外空间实现基于比较的排序并非不可能，但这是非常不切实际的。

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

• 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) 空间，因此这可能很有用。