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()花费更多的空间吗？

Answer 1

我假设你在这里谈论Java.

因此循环将耗费O(n)时间,我的问题是Arrays.sort()会花费更多时间吗？

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

并且Arrays.sort()会花费更多空间吗？

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

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

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

Answer 2

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

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

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