存在阵列相关问题,要求是时间复杂度为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()会花费更多的空间吗？
解决方法
我假设你在这里谈论Java.
So the loop will cost O(n) time,my question is that will Arrays.sort() cost more time?
是的,Arrays.sort(int[])在我所知道的所有Java标准库实现中,是基于比较的排序,因此是must have worst-case complexity Ω(n log n)的一个例子.特别是,Oracle Java 7对整数重载使用了双轴快速排序变体,实际上它具有一个Ω n2)最坏的情况.
and will Arrays.sort() cost more space?
很可能会使用ω(1)空格(这意味着另一个是,空间使用不是O(1)).虽然不可能实现基于比较的排序,只有恒定的额外空间,这是非常不切实际的.
也就是说,在某些条件下,可以按线性时间对特定类型的数据进行排序,例如：
> http://en.wikipedia.org/wiki/Counting_sort
> http://en.wikipedia.org/wiki/Pigeonhole_sort
> http://en.wikipedia.org/wiki/Radix_sort
使用恒定范围的输入整数(例如对于某些常数C),abs(A [i])<= C),则计数排序和基数排序使用的确只有O(n)个时间和O(1)空间,所以这可能是有用的.
