|
通りすがり |
|
すべての順序を求めることは、要素の整列（ソート）問題に帰着します。
N 個の要素を整列するための比較回数 M は、 以下を満足する必要があります。 2^M >= N! つまり、2 の M 乗は、N の階乗と等しいか大きくなければいけません（必要条件）。 ここで、ceil は切り上げを、log2 は 2 を底とするの対数を表す関数とすると、 M の最小値（下限）は、以下の式から求まります。 M = ceil(log2(N!)) しかし、現在までに、確認（証明）されている最小の比較回数を K とすると、 以下の表のようになっています。 N: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ------------------------------------------------------------------- M: 0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 53 57 62 66 70 K: 0 1 3 5 7 10 13 16 19 22 26 30 34 38 42 46 50 54 58 62 66 71 気づかれると思いますが、N が 12 〜 19 と 22では、K = M + 1 になっています。 もっと詳しく知りたい方は、皆さんおなじみの数列辞典（OEIS）の A036604 や A001768 あたりを見て下さい。 |
|
10月9日（木） 6:38:53
42506 |