2

サイズ n の配列 A は、O(n) 個の反転がある場合、Θ(n) でソートできることを証明してください。

この質問が何を求めているのか正確にはわかりません。私の最善の推測は、事前に並べ替えられた入力に対して挿入並べ替えを使用し、その方法で並べ替えによって Θ(n) の複雑さを達成できるということです。これは質問が私に尋ねていることですか？

4

1 に答える 1

3

ヒントとして、挿入ソートの実行時間は Θ(n + I) です。ここで、n は要素の数、I は配列内の反転の数です。反転が O(n) 個しかない場合、配列を挿入ソートするとどうなるでしょうか? 時間複雑度はどうなりますか？

お役に立てれば！

于 2013-10-29T06:21:25.080 に答える