単連結リストの整列 #84 基本選択法での所要時間のプロット

さて、前回の結果から冪関数への回帰分析を行い、結果をプロットしてみよう。
比較、交換回数の性質は数値による結果だけでも明白なので、
ここでは整列に要した時間に関するものだけを表示する。
'plot2.dat'は隣接交換法による双方向連結リストの整列の結果、
'slink.dat'は基本選択法による単連結リストの結果、
'dlink.dat'は基本選択法による双方向連結リストの結果である。

f(x,a,b) = a * x + b
fit f(x,a5,b5) 'plot2.dat' using (log($1)):(log($4)) via a5, b5
fit f(x,a6,b6) 'slink.dat' using (log($1)):(log($4)) via a6, b6
fit f(x,a7,b7) 'dlink.dat' using (log($1)):(log($4)) via a7, b7

show variables a
show variables b

g(x,a,b) = exp(b) * x ** a

set key right bottom
set logscale xy
set pointsize 1.5
set xlabel "number of elements in a list"
set ytics format "10^%L"
set ylabel "elapsed time of 100 trials / ms"
plot [100:2000] [10:4000] \
  'slink.dat' using 1:4 title "s-linked elapsed time", \
  'dlink.dat' using 1:4 lc rgb "forest-green" title "d-linked elapsed time", \
  'plot2.dat' using 1:4 title "bubble sort, d-linked elapsed time", \
  g(x,a6,b6) title sprintf("s-linked elapsed scaling exponent %.4g", a6), \
  g(x,a7,b7) lc rgb "forest-green" title sprintf("d-linked elapsed scaling exponent %.4g", a7), \
  g(x,a5,b5) lc 3 title sprintf("bubble sort, d-linked elapsed scaling exponent %.4g", a5)

        Variables beginning with a:
        a5 = 2.00612884132541
        a6 = 1.94991052619515
        a7 = 2.00631825454668

        Variables beginning with b:
        b5 = -6.87292540725565
        b6 = -6.76016276967951
        b7 = -7.36274206821751

基本選択法の場合、対象リストが単連結リストか双方向連結リストかに関係なく、
要素数の二次オーダで所要時間が増加している。
単連結リストにおける要素の交換は要素数の一次オーダの時間計算量が必要であるため、
交換に要する総時間は二次オーダとなる。
比較に要する時間も二次オーダであるため、整列全体の所要時間は要素数の二次オーダとなる。
交換時における単連結リストの原理的な欠点があっても、
隣接交換法による双方向連結リストの整列よりも時間性能がよいのは交換回数の少なさによるものだろう。

双方向連結リストでは一回の交換は定数時間で処理でき、
交換に要する総時間は一次オーダになるので、
整列全体の所要時間は比較処理に支配されているのだろうと思う。
単連結リストより処理時間が短いのは交換一回当たり定数時間で処理できるからであろう。