次へ: 11 増加列ブロック数の分布 上へ: sort1 前へ: 9 方法 B の整列化の例 (PDF ファイル: sort1-2.pdf)

10 方法 A, B の比較

前節までに、方法 A, B の最適手順が構成されたことになるが、 これらの方法の平均回数を比較してみることとする。 この平均回数 とは、$N$ 枚の $N!$ 種類の順列に対する手順数の平均を 意味し、それらが均等にランダムに起こるとした場合の手順数の期待値、 と言うこともできる。

例えば、$N=4$, $M=2$ の場合、増加列ブロック数 $s_1$、 減少列ブロック数 $s_2$ と方法 A、方法 B の回数は以下の関係にある:

$s_1$	$s_2$	A	B
1	4	0	0
2	3	1	2
3	2	2	1
4	1	2	1

一見、方法 B の方がかなり少ないように見えるかもしれないが、 4! 種類のすべての順列に対してその回数を書きあげてみると以下のようになる。

A 列の最終形	$s_1$	$s_2$	A	B
1 2 3 4	1	4	0	0
1 2 4 3	2	3	1	2
1 3 2 4	2	3	1	2
1 3 4 2	2	3	1	2
1 4 2 3	2	3	1	2
1 4 3 2	3	2	2	1
2 1 3 4	2	3	1	2
2 1 4 3	3	2	2	1
2 3 1 4	2	3	1	2
2 3 4 1	2	3	1	2
2 4 1 3	2	3	1	2
2 4 3 1	3	2	2	1

A 列の最終形	$s_1$	$s_2$	A	B
3 1 2 4	2	3	1	2
3 1 4 2	3	2	2	1
3 2 1 4	3	2	2	1
3 2 4 1	3	2	2	1
3 4 1 2	2	3	1	2
3 4 2 1	3	2	2	1
4 1 2 3	2	3	1	2
4 1 3 2	3	2	2	1
4 2 1 3	3	2	2	1
4 2 3 1	3	2	2	1
4 3 1 2	3	2	2	1
4 3 2 1	4	1	2	1

この総数を比較すると、平均は確かに方法 B の方が小さいが、 その違いはわずかであることがわかる:

方法	0 回	1 回	2 回	平均回数
方法 A	1 通り	11 通り	12 通り	35/24
方法 B	1 通り	12 通り	11 通り	34/24

$s_1$ と総数の関係を表にすると以下のようになるので、 これは $s_1=4$ のところの違いが出ているようにも見える。

$s_1$	1	2	3	4
総数	1	11	11	1

一般の $N$ に対する考察を行うために、 この増加列ブロック数毎の総数を求ることができれば、 平均の計算はそれに各 $s_1$ に対する回数をかければよい。 よって、今度はその増加列ブロック数毎の総数の計算を行なう。

次へ: 11 増加列ブロック数の分布 上へ: sort1 前へ: 9 方法 B の整列化の例