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

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

排序算法是由弗拉基米尔·雅罗斯拉夫斯基、乔恩·本特利和约书亚·布洛赫提出的双轴快速排序算法。该算法在许多数据集上提供了O(n log(n))的性能，这些数据集会导致其他的快速性能下降到二次性能，并且通常比传统的(单枢轴)快速排序实现更快。

因此，它将增加您的时间复杂度从O(n)到O(n log(n))。

Answer 2

它是超过O(n)时间，需要更多的O(1)空间。

Arrays.sort()在1.7中使用了一个改进的蒂姆塞德，这是最近发展起来的排序算法，它提供了复杂度x的排序，其中O(n)< x< O(nlgn)和O(n/2)的空间。

Answer 3

Arrays.sort(int[] a)在最近的JDK中是用双枢轴快速排序算法实现的，该算法具有O(n log )平均复杂度，并且在本地执行(例如不需要额外的空间)。