[解決済み] JavaでCollections#sortメソッドの時間的複雑さは何ですか？[重複しています]。

質問

の時間的複雑性はどの程度でしょうか？ Collections#sort メソッドをJavaで作成できますか？どのようなアルゴリズムが使われていますか？

は Collection#sort をソートするための良い方法です。 ArrayList の10^6？

どのように解決するのですか？

使用するJavaのバージョンに依存します。 しかし、最終的にBig-Oの時間複雑度はO(N*log(N))のままです。

Java 6の場合は、mergesortの修正版です。説明はこちらで確認してください。 Collections#sort Java 6用

ソートアルゴリズムは、修正マージソート(lowサブリストの最大要素がhighサブリストの最小要素より小さい場合、マージが省略される)です。このアルゴリズムは、n log(n)の性能を保証している。指定されたリストは変更可能でなければならないが、サイズ変更可能である必要はない。この実装では、指定されたリストを配列にダンプし、配列をソートして、配列の対応する位置から各要素をリセットしてリストを反復処理します。これにより、リンクリストをその場でソートしようとした場合に生じる n2 log(n) のパフォーマンスを回避することができます。

Java 7では、改良されました。 Collections#sort Java 7用 により エンハンスメント . なお ティムソート はO(N)のベストケースを持ち、以前の実装よりも高速であることが証明された。

実装上の注意：この実装は安定した適応型反復マージソートであり、入力配列が部分的にソートされている場合はn lg(n)よりはるかに少ない比較しか必要とせず、入力配列がランダムに並んでいる場合は従来のマージソートの性能を提供する。入力配列がほぼソートされている場合、この実装では約n回の比較が必要です。一時的なストレージの必要量は，ほぼソートされた入力配列の小さな定数から，ランダムに並べられた入力配列の n/2 オブジェクトリファレンスまで様々です．

この実装では、入力配列の昇順と降順を等しく利用し、同じ入力配列の異なる部分でも昇順と降順を利用することができます。2 つ以上のソート済み配列を結合するのにも適しており、 配列を連結してその結果をソートします。

この実装は Tim Peters のリストソート for Python ( ティムソート ). Peter McIlroyの "Optimistic Sorting and Information Theoretic Complexity", Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993 のテクニックを使っているのだそうです。

この実装では、指定されたリストを配列にダンプし、その配列をソートし、配列の対応する位置から各要素をリセットしながらリストを反復処理します。これにより、リンクリストをその場でソートしようとした場合に生じる n2 log(n) の性能を回避することができます。

をソートするのに適した方法なのでしょうか？ ArrayList の10^6？

理屈では、十分使えます。しかし、これでは、なぜメモリ上でデータをソートする必要があるのか、疑問が残ります。もしデータがデータベースから来るのであれば、インデックス付きのカラム/フィールドを使ってソートします。そうでなければ、ソートに使うフィールドの特性をいくつか知っているかどうか、そしてO(N)時間の複雑さのアルゴリズムが使えるかどうか確認してください。 バケットソート または 基数ソート . 他に方法がない場合は Collections#sort .