Collections.sort(list)がすでにソートされているかどうか、またはlist他の理由で O(1) であるかどうかを確認しますか?
または、フラグを並べ替えて、/リストに要素を追加する呼び出し時にtrue/に設定することをお勧めしますか?falsesort()
1937 次
4 に答える
9
リストを見ずにソートされているかどうかをどのように判断できますか? それはありませんO(1)。リストがソートされているかどうかを判断するには、少なくともO(n).
つまりCollections.sort、リストが最初にソートされているかどうかをわざわざチェックした場合、各ソート操作の平均はO(n) + O(n log n).
于 2012-04-28T21:26:56.993 に答える
7
実際のところ、Java7 では、Java はいくつかのソート タスクについて、mergesort からTimSort (最初に cpython 用に実装した Python 開発者 Tim Peters にちなんで名付けられました) に切り替えました。
O(1) ではありませんが、TimSort を使用して既に並べ替えられた、または部分的に並べ替えられたリストを並べ替えると、完全にランダムなデータ セットを並べ替えるよりもはるかに効率的です (後者については、比較並べ替えよりも効率的な方法はありO(n log n)ません。ランダムデータではありません)。
于 2012-04-28T21:36:16.960 に答える
3
それが O(1) であるはずがありません。コレクションが O(n) よりも速くソートされているかどうかを確認することはできません。フラグを持つことは問題ないはずですが、正確に何をしているのかを知らずに確実に言うのは難しいです.
于 2012-04-28T21:26:46.563 に答える
2
一般的に言えば、既にソートされたリストをソートしても速くなることはありません (バブルソートのような単純なソートを除く)。
Collections.sort() の場合、ソートされたリストをソートしても高速ではありません。
于 2012-04-28T21:28:00.357 に答える