23

有一个数组相关的问题，要求时间复杂度为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()花费更多空间吗？

4

5 回答 5

39

我假设您在这里谈论Java。

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

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

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

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

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

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

于 2014-03-21T23:59:38.753 回答
7

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

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

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

于 2018-03-19T10:12:38.733 回答
2

最近的 JDK 中的 Arrays.sort(int[] a) 是使用 Dual-pivot Quicksort 算法实现的，该算法具有 O(n log n) 平均复杂度并且在原地执行（例如，不需要额外的空间）。

于 2014-03-22T00:22:03.047 回答
2

它超过 O(n) 时间并且需要超过 O(1) 空间。

Arrays.sort()在 1.7 中使用了改进的Timsort，这是一种相对较新开发的排序算法，它提供复杂度 x 的排序，其中 O(n)< x < O(nlgn) 和 O(n/2) 的空间

于 2014-03-22T00:00:27.430 回答
0

既然你用Java语言谈论它，时间复杂度肯定会从O(n)增加到O(nlogn)。那是因为在 Java 8 中， Arrays.sort() 是在 Dual-pivot 快速排序算法中实现的，而不是 single-pivot 。所以需要额外的时间。O(1) 的空间复杂度是不可能的，因为它需要更多的空间，我猜是 O(n/2)。

于 2021-06-01T02:54:21.653 回答