java – 将Arrays.sort()增加时间复杂性和时空复杂度?

前端之家收集整理的这篇文章主要介绍了java – 将Arrays.sort()增加时间复杂性和时空复杂度?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
存在阵列相关问题,要求是时间复杂度为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)空间,所以这可能是有用的.

原文链接:https://www.f2er.com/java/122654.html

猜你在找的Java相关文章