1

通常の比較に加えて、超比較も許可されている並べ替えアルゴリズムがあるとします。超比較は 3 つの要素を取り、それらの要素を最小から最大の順に出力します。

下限を見つけたい。

可能な結果が 2 つしかない通常の比較とは異なり、スーパー比較では 3 つになります。考えられる結果は、そうあるべきだと思いますlog3(n!)。

よくわかりませんが、何かアイデアはありますか？

4

2 に答える 2

3

実際、超比較の数は ですlog_6(n!)。これは、超比較操作ごとに 3 つではなく 6 つの可能な結果があるためです (3! = 6)。したがって、ランダム順列を表すツリーでこれらの超比較を繰り返し呼び出すと、log_6(n!)比較操作内でソートされた配列が得られます。

漸近的な時間の複雑さになるとO(nlogn)、基数を簡単に切り替えることができるため、対数の基数は問題にならないことに注意してください。

log_6(n!) = log_2(n!)/log_2(6) = log_2(n!) / CONST 
=> log_6(n!) is in O(log_2(n!))
=> log_6(n!) is in O(nlogn)

PS良い直感は、「無限」で何が起こるかを見ることです。つまり、n要素を並べ替えるスーパー比較があることです。明らかに、配列をソートするにはそのような op が 1 つ必要であり、実際にlog_n!(n!) = 1は 、 while log_n(n!) > 1.

于 2013-02-04T07:56:44.187 に答える
-1

ocamlで、

let rec quicksort = function
    | [] -> []
    | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs
               in quicksort smaller @ (x::quicksort larger)
于 2013-02-04T07:38:14.287 に答える