クイックソートの最良の実行時間が線形ではない理由を誰かが説明できますか？クイックソートのベストケースランタイムを線形にする方法はありますか？もしそうなら、なぜそれらは実際に通常使用されないのですか？
4 に答える
1
少なくともwikiリンクを通過する必要があります...彼らはこれを非常に理解しやすい図とアニメーションで説明しています。
于 2013-02-26T07:23:28.293 に答える
0
クイックソートは、直接比較の並べ替え方法です。このようなすべての方法では、各ステップで2値の決定（つまり、直接比較）を使用して、ソートの2つの可能な結果の間で分岐します。N個の要素の配列で可能なすべての並べ替えはNです。したがって、これらの結果のそれぞれを出力できる二分決定木の最低の高さはlog（N！）ですが、O（log（N！））= O（N * log（N））。したがって、直接比較ソートアルゴリズムは、これよりも複雑になる可能性があります。
したがって、クイックソートはそのようなアルゴリズムの例であるため、O（N * log（N））よりも複雑さを低くすることはできず、線形にすることはできません。
于 2013-02-26T09:02:11.760 に答える
0
クイックソートは、最悪の場合はO（n 2 ）時間で実行されますが、最良/平均のO（n log n）で実行されます。実際には、最悪のケースが高いにもかかわらず、ヒープソートやマージソート（最悪の場合はO（n log n）ソート）よりもパフォーマンスが優れているのが一般的です。
ソートは、すでにソートされていない限り、線形時間でのみ実行できます。これは、挿入ソートのようなベストケースのO（n）を持つソートにのみ適用されます。
于 2013-02-26T07:30:32.823 に答える
0
もちろん、最初に入力が既にソートされているかどうかを確認し、ソートされている場合はすぐに戻ることができます。これにより、線形の最良のケースの複雑さを持つアルゴリズムが得られます。しかし、その後、「Quicksort」ではなく「Modfied Quicksort」になってしまいます。
于 2013-02-26T07:32:43.533 に答える