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

Question

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

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

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

原文由 aminy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

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

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

十有八九它将使用 ω(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) 空间，因此这可能是有用的.

原文由 Niklas B. 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

根据 Arrays.sort() 方法的java jvm 8 javadocs：

排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的双轴快速排序。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序退化为二次性能，并且通常比传统（单轴）快速排序实现更快。

所以它会将你的时间复杂度从 O(n) 增加到 O(n log(n))

原文由 pedrogonzalezj 发布，翻译遵循 CC BY-SA 3.0 许可协议