0

非比較ベースの並べ替えアルゴリズムと比較ベースの並べ替えアルゴリズムの主な欠点を理解しようとしています。

それは主に、非比較ベースのソートアルゴリズムが非固定長入力に対してうまく機能しないためですか?

たとえば、4 つの要素 [1, 10000000000000000024, 3, 5] があるとします。

比較ベースのソート アルゴリズムは、4 * log(4) で解決します。

非比較ベースのソートアルゴリズムは、キー 0 から 9 を使用し、LSD や MSD などのアルゴリズムを使用すると仮定すると、4 * length_of("10000000000000000024") で解決します。

または、数値が 0 から 100000000000000000024 の間にあることがわかっているとします。0 から 100000000000000000024 までのキーを持つことができますが、比較ベースの並べ替えアルゴリズムをインプレースで実行できるため、これは非常にスペース効率が悪くなります。

ありがとう、ウェイリー

4

1 に答える 1

3

非比較ソート アルゴリズムでは、多くの場合、入力データに関する多くの仮定が必要になります (カウント ソートの場合は狭い範囲の整数、バケット ソートの場合は均一に分散されるなど)。

時間の計算量は、多くの場合、入力サイズのみに依存します。たとえば、カウントソートは、基数ソートと同様に範囲に依存します。

于 2013-09-15T20:32:49.447 に答える