0

この種のクイックソートの実装があるとします。これはおそらく標準のものとは少し異なります。

qsort(list):
if list is of length 1 or lower - 
     return list
else - 
     choose a random pivot 
     smaller - get all elements that are smaller than the pivot
     equal - get all elements that are equal to the pivot, including the pivot itself
     greater - get all elements that are greater than the pivot
     return qsort(smaller) + equal + qsort(greater)

その関数の最良のシナリオは、関数がすべての要素が同じリストを受け取った場合ではないでしょうか。その場合、O(n)最良のケースの時間の複雑さは、標準の最良のケースの時間の複雑さよりも優れています。クイックソートのバージョンはO(n log n)?

その理由は、関数がこれらのパーティションを一度だけ作成するためです。小さいリストと大きいリストは空になるため (すべての要素が同じであるため)、これにより再帰が終了しqsort(smaller)、qsort(greater)空のリストが返されるだけです。

あれは正しいですか？

4

1 に答える 1

1

はい、あなたが説明した場合、時間の複雑さは になりますO(n)。

O(n)ただし、新しいリストequalを作成する必要があるため、スペースも使用できます。これは、その場でソートする qsort がO(1)（一定の）スペースを必要とすることよりも悪いことです。

の qsort 時間の複雑さO(n lg(n))は、統計的にランダムなデータを想定して計算された平均的なケースです。あなたの適応は、すべての値が等しいというエッジケースでのパフォーマンスに役立ちますが、これは非常にまれです (ただし、データについて事前に知っている可能性が高くなります)。

標準の qsort とは対照的に、このアルゴリズムの使用を検討している場合は、使用しないことをお勧めします。追加のリストを使用すると、要素の追加と連結にオーバーヘッドが追加されるため (このオーバーヘッドがどこにあるかは、リストの実装によって異なります)。qsort はその場でソートされるため、このオーバーヘッドは qsort には存在しません。

于 2013-07-11T12:40:03.283 に答える