質問: 数字の並び換えの最適手順 n個の異なる数字があります。これを大小の順にならべ換えます。 最適手順数は計算上はlog(n!)/log(2)です。 その最適手順の一般化は可能でしょうか。 例1:n=4のとき a、b,c,dと4個の数字があって 1回目 aとbを比較 結果a>bが判明 2回目 cとdを比較 結果c>dが判明 3回目 aとcを比較 結果a>cが判明 4回目 bとcを比較する b>cのときは、a,b,c,dとなって並び替え終了。 こういう都合の良い結果での並び換え終了は手順からはずします。 c>bのとき 5回目 bとdを比較する b>dのとき a、c,b,d で終了 d>bのとき a,c、d、b で終了 例2:n=5のとき a、b,c,d、eと4個の数字があって 1回目 aとbを比較 結果a>bが判明 2回目 cとdを比較 結果c>dが判明 3回目 aとcを比較 結果a>cが判明 4回目 eとcを比較 5回目 e>cのときeとaを比較、c>eのときeとdを比較 6回目 ここから場合わけひどくなります。 例としてa>e>c>dのときbとcを比較 7回目b>cのときbとeを比較、c>bのときbとdを比較 例3:n=6であれば10回、n=7であれば13回でした。 これらはn=5の手順のあと6個目、7個目の位置決めするだけ。
回答: や, 私の方もうろ憶えで「理論上の最小回数ではできない例があるってどこかで読んだ記憶があるなぁ」くらいで書いてますので. ところで, これと p=np とどのように関係しているのか見えないのですが....