No. 4≫ No.5 ≫No. 6
nn)/
2010/06/11 17:10
どうも難しい問題なようですので，ネットで調べてみました．
2007 年現在で知られている真の最小比較回数 a(N) (N= 2, 3, ..., 14, 20, 21, 22) を
m(N) = ceil(log_2 N!), n(N) = Σ[k＝1〜N]ceil(log_2 k) と並べました．
N: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 20, 21, 22
a: 1, 3, 5, 7,10,13,16,19, 22, 26, 30, 34, 38, 62, 66, 71
m: 1, 3, 5, 7,10,13,16,19, 22, 26, 29, 33, 37, 62, 66, 70
n: 1, 3, 5, 8,11,14,17,21, 25, 29, 33, 37, 41, 69, 74, 79
m と n の間にあって，知られている範囲では，m に等しいか +1 です．
これ以外の N について a(N) が求まれば，論文が書けるのではないでしょうか．
追記: Ford-Johnson アルゴリズムを用いれば，比較回数
N ceil(log_2(3N/4)) - [2^[log_2(6N)]/3] + [log_2(6N)/2]
で整列できるとのことです．なお，[ ] はガウス記号です．
上記の範囲では全て a(N) に一致します．ただし，N がある程度以上大きい
とき (N ≧ 47 ?) には，もっと良い方法があるらしいです．
2007 年現在で知られている真の最小比較回数 a(N) (N= 2, 3, ..., 14, 20, 21, 22) を
m(N) = ceil(log_2 N!), n(N) = Σ[k＝1〜N]ceil(log_2 k) と並べました．
N: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 20, 21, 22
a: 1, 3, 5, 7,10,13,16,19, 22, 26, 30, 34, 38, 62, 66, 71
m: 1, 3, 5, 7,10,13,16,19, 22, 26, 29, 33, 37, 62, 66, 70
n: 1, 3, 5, 8,11,14,17,21, 25, 29, 33, 37, 41, 69, 74, 79
m と n の間にあって，知られている範囲では，m に等しいか +1 です．
これ以外の N について a(N) が求まれば，論文が書けるのではないでしょうか．
追記: Ford-Johnson アルゴリズムを用いれば，比較回数
N ceil(log_2(3N/4)) - [2^[log_2(6N)]/3] + [log_2(6N)/2]
で整列できるとのことです．なお，[ ] はガウス記号です．
上記の範囲では全て a(N) に一致します．ただし，N がある程度以上大きい
とき (N ≧ 47 ?) には，もっと良い方法があるらしいです．