23

配列に関連する問題があります。要件は、時間の複雑さが O(n) で、空間の複雑さが O(1) であることです。

をArrays.sort(arr)使用し、forループを 1 つのパス ループに使用すると、たとえば次のようになります。

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()より多くのスペースがかかりますか?

4

5 に答える 5

39

ここでJavaについて話していると仮定します。

したがって、ループには O(n) の時間がかかります。私の質問は、Arrays.sort() にかかる時間が長くなるということですか?

はい、Arrays.sort(int[])私が知っているすべての Java 標準ライブラリの実装では、比較ベースの並べ替えの例であるため、最悪の場合の複雑さ Ω(n log n) が必要です。特に、Oracle Java 7 は整数のオーバーロードにデュアル ピボット クイックソート バリアントを使用しますが、実際にはΩ(n 2 )の最悪のケースがあります。

Arrays.sort() はより多くのスペースを必要としますか?

おそらく、それは ω(1) スペースを使用します (つまり、別のyesを意味します。スペースの使用は O(1) ではありません)。一定の余分なスペースのみを使用して比較ベースの並べ替えを実装することは不可能ではありませんが、非常に非現実的です。

とはいえ、特定の条件下では、特定のタイプのデータを線形時間で並べ替えることができます。たとえば、次を参照してください。

入力整数の範囲が一定の場合（たとえば、abs(A[i]) <= C定数Cの場合）、カウントソートと基数ソートは実際にO（n）時間とO（1）スペースしか使用しないため、役立つ場合があります。

于 2014-03-21T23:59:38.753 に答える
2

最近の JDK の Arrays.sort(int[] a) は、平均複雑度が O(n log n) で、その場で実行される (たとえば、余分なスペースを必要としない) デュアルピボット クイックソート アルゴリズムで実装されています。

于 2014-03-22T00:22:03.047 に答える