次へ: 13 最後に 上へ: sort1 前へ: 11 増加列ブロック数の分布 (PDF ファイル: sort1-2.pdf)

12 平均回数の数値計算結果

整列化に必要な手順数は、A 列の増加列ブロック数によって決まり、 命題 1, 3, 6, 7 より、 $s_1=k$ のとき、

$$\left\{\begin{array}{lll} \mbox{方法 A}: & M^{j-1}<k\leq M^... ... \Rightarrow \mbox{(手順数)}=\min\{2j,2l+1\}\end{array}\right.$$

である。この増加列ブロック数 $k$ に対する方法 A の手順数を $a^N_k$, 方法 B の手順数を $b^N_k$ と書くことにする。

例えば、$M=2$, $N=5$ の場合は

$k$	1	2	3	4	5
$a^N_k$	0	1	2	2	3
$2j$	0	2	2	2	4
$2l+1$	3	3	3	1	1
$b^N_k$	0	2	2	1	1

$N=10$ の場合は

$k$	1	2	3	4	5	6	7	8	9	10
$a^N_k$	0	1	2	2	3	3	3	3	4	4
$2j$	0	2	2	2	4	4	4	4	4	4
$2l+1$	5	5	3	3	3	3	3	3	1	1
$b^N_k$	0	2	2	2	3	3	3	3	1	1

となる。よって、11 節の表により、$N=5$ の場合方法 A ($a^N_k$) の平均 $\bar{a^N}$ は、

$$\bar{a^N} =\frac{1\times0 + 26\times1 + 66\times2 + 26\times2+1\times3}{5!} =\frac{213}{120} =1.775$$

方法 B ($b^N_k$) の平均 $\bar{b^N}$ は、

$$\bar{b^N} =\frac{1\times0 + 26\times2 + 66\times2 + 26\times1+1\times1}{5!} =\frac{211}{120} =1.758$$

となり、大きな違いはない。$N=10$ の場合は 3) より、

$$\begin{eqnarray*}\bar{a^N} &=& \frac{A^{10}_2+2(A^{10}_3+A^{10}_4) +3(A^{10}_... ...=& \frac{A^{10}_1+3A^{10}_2+5A^{10}_3+5A^{10}_4+6A^{10}_5}{10!},\end{eqnarray*}$$

となり、値がかなり大きい $k=N/2$ 付近の $A^N_k$ については両者の係数が一致し、 異なるのは値がかなり小さい $A^N_k$ なので、 それほど違いがないことになる。実際、数値でみると、 $N=10$ の場合は

$$\left\{\begin{array}{cll} \bar{a^N} & = \displaystyle \frac... ...le \frac{2029}{3628800} &= 5.59\times 10^{-4}\end{array}\right.$$

となる。

同様に、 $N=10,20,50,100$ での値をコンピュータに数値計算させた結果は 以下の通りである。

$N$	10	20	50	100
$\bar{a^N}$	2.8611	3.9390	5.000	6.000
$\bar{b^N}$	2.8605	3.9390	5.000	6.000
$\bar{a^N}-\bar{b^N}$	$5.59\times 10^{-4}$	$8.47\times 10^{-7}$	$3.60\times 10^{-6}$	$1.03\times 10^{-10}$

$M=2$, $N=100$ くらいでも 6 回くらいで終わり (最悪でも 7 回)、 方法 B の方がごくわずかに速いが、ほとんど違いはないことがわかる。

なお、この表に見られるように、この差は $N$ に関して単調減少ではない。 それについては今後さらに調べてみたいと思う。

また、$N=100$ のようにかなり大きな $N$ に対する $A^N_k$ の計算は 実はコンピュータでも容易ではなく、 計算式としては (4), (5) の どちらを使っても、 それらの式を普通に計算すると桁落ちなどによるものと思われる 誤差が大きく発生してしまう。

例えば、$A^{100}_{50}$ の (4), (5) の 最初の項である $50^{100}$ は $100\log_{10}50=169.9$ より 170 桁であるが、 実際の $A^{100}_{50}$ は 158 桁しかなく、 つまり (4), (5) の 第 2 項目以降の項による引き算により上位の桁が下がってしまう。 単純な倍精度計算で計算したところ、 本来は 1 になるべき $\sum_{k=1}^{100}A^{100}_k/100!$ の値が 1 を大きく超えてしまった。

このような場合、桁落ちが起きないような、同符号のみの項からなるような 計算式を求めるか、あるいは多倍長演算を行なう、などの必要があるが、 今回は 170 桁の多倍長整数演算を用いて (4) により 計算を行なった。 しかし、同符号のみの項による展開式があれば計算は容易になるはずなので、 それについても今後考えてみたいと思う。

次へ: 13 最後に 上へ: sort1 前へ: 11 増加列ブロック数の分布