2

すべての要素が 0...2n であり、順序付けされていないことがわかっている配列があるとします。

複雑さ O(n+k) のバケット ソート アルゴリズムを使用すると、k は要素の範囲 (この場合は 2n) で、この配列をソートする複雑さは Θ(n) になりますか?

私の論理的根拠は、ランタイムが O(n + 2n) であり、これは O(3n) と同じであり、3 は単なる係数であるため、複雑さは Θ(n) になるというものです。

この分析は正確ですか？

4

1 に答える 1

2

はい、あなたの分析は正しいです。カウントソートの実行時間は Θ(n + k) です。ここで、n は要素の数、k はバケットの数です。固定定数 c の最大値が cn の場合、前述のように、カウントソートの実行時間は Θ(n) になります。

お役に立てれば！

于 2013-10-26T18:38:40.330 に答える