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

发布时间：2020-12-14 05:25:12 所属栏目：Java 来源：网络整理

导读：存在阵列相关问题,要求是时间复杂度为O(n),空间复杂度为O(1). 如果我使用Arrays.sort(arr),并将一个for循环用于一个循环,例如： public static int hello(int[]A){ Arrays.sort(A); for(int i=0;iA.length;i++){ .................... } return ....; } 所以

存在阵列相关问题,要求是时间复杂度为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)空间,所以这可能是有用的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!