将Arrays.sort（）增加时间复杂度和空间时间复杂度？ [英] Will Arrays.sort() increase time complexity and space time complexity?

问题描述

有数组相关的问题，要求是时间复杂度为O（n）和空间复杂度为O（1）。

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).

如果我用 Arrays.sort（ARR），并使用为循环一遍环路，例如：

If I use Arrays.sort(arr), and use a for loop to one pass loop, for example:

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（）花费更多的空间？

So the loop will cost O(n) time. My question is: will Arrays.sort() cost more time? If I use Arrays.sort(), will this time complexity still be O(n)? And will Arrays.sort() cost more space?

推荐答案

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

I am assuming you are talking about Java here.

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

So the loop will cost O(n) time, my question is that will Arrays.sort() cost more time?

是，<一个href="http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort%28int%5b%5d%29"><$c$c>Arrays.sort(int[])在所有的Java标准库的实现，我知道，是一个基于比较的排序的例子，因此<一href="http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list">must有最坏情况的复杂性Ω（N log n）的。特别是，甲骨文的Java 7采用了双支点快速排序变体的整过载，这实际上有一个的Ω（N ² ）的最坏情况。

Yes, Arrays.sort(int[]) in all Java standard library implementations that I know, is an example of a comparison-based sort and thus must have worst-case complexity Ω(n log n). In particular, Oracle Java 7 uses a dual-pivot quicksort variant for the integer overloads, which actually has an Ω(n²) worst case.

和将Arrays.sort（）花费更多的空间？

and will Arrays.sort() cost more space?

在所有的可能性，将使用ω（1）空间（这意味着另一个是，占用空间是不是O（1））。虽然这不是不可能实现，唯一不变的额外空间的比较为基础的排序，这是非常不现实的。

In all likelihood it will use ω(1) space (which means another yes, the space usage is not O(1)). While it's not impossible to implement a comparison-based sort with only constant extra space, it's highly impractical.

这就是说，在一定条件下，可以对特定类型的线性时间数据的排序，参见例如：

That said, under certain conditions it is possible to sort specific types of data in linear time, see for example:

• <一个href="http://en.wikipedia.org/wiki/Counting_sort">http://en.wikipedia.org/wiki/Counting_sort
• <一个href="http://en.wikipedia.org/wiki/Pigeonhole_sort">http://en.wikipedia.org/wiki/Pigeonhole_sort
• http://en.wikipedia.org/wiki/Radix_sort

• http://en.wikipedia.org/wiki/Counting_sort
• http://en.wikipedia.org/wiki/Pigeonhole_sort
• http://en.wikipedia.org/wiki/Radix_sort

通过在一定范围的输入整数（例如，如果 ABS（A [1]）＆LT; = C 对于一些常数C），则计数排序和基数排序使用的确只有O（n）时间及O（1）空间，因此这可能是有益的。

With a constant range of input integers (for example if abs(A[i]) <= C for some constant C), then counting sort and radix sort use indeed only O(n) time and O(1) space, so that might be useful.

这篇关于将Arrays.sort（）增加时间复杂度和空间时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！