Arrays.sort（）会增加时间复杂性和时空复杂性吗？

arrays time-complexity sorting java space-complexity

2022-09-01 18:25:59

有一个与数组相关的问题，要求是时间复杂度为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）时间。我的问题是：会花费更多的时间吗？如果我使用，这个时间的复杂度还会是O（n）吗？会花费更多的空间吗？Arrays.sort()Arrays.sort()Arrays.sort()

答案 1

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

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

是的，在我所知道的所有Java标准库实现中，Arrays.sort（int[]）都是基于比较的排序的一个例子，因此必须具有最坏情况的复杂性Ω（n log n））。特别是，Oracle Java 7使用双透视快速排序变体来表示整数重载，这实际上具有Ω（n²）最坏的情况。

Arrays.sort（）会占用更多空间吗？

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

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

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

答案 2

根据 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））的时间复杂度

Arrays.sort（） 会增加时间复杂性和时空复杂性吗？