20180525_7_theory

(20130604)

ソーティングの計算量についての理論的な考察

n個のデータを並べた順列の個数：n!

このn!個の順列の中に、ただ１個の昇順の並びが存在する。

１回の比較（交換）で（うまくすると）、可能性がある順列の個数を半減できる。

すると、最良の場合で、log(n!) の回数の比較（交換）で昇順の並びを求められる。
また、これを上から押えて評価すると、

	n・log(n) > log(n!)

したがって、時間計算量は、n・log(n) と（上から押えて）見積もることができる。
なぜならば、

	n × n × … × n > n × (n - 1) × … × 2 × 1
	      （n個）

【参考】

（問１）
１２個の球の中に１個だけ重さの異なる球が混じっている。
天秤を３回だけ使って、重さの異なる球を見つけ出せ。

（問２）
１３個の球の中に１個だけ重さの異なる球が混じっている。
天秤を３回だけ使って、重さの異なる球を見つけ出せ。

（ヒント）
天秤の状態は３通りある。
(1) 左側の皿が下がる。
(2) 右側の皿が下がる。
(3) 左右の皿が釣り合う。
つまり、１回の天秤の使用で（うまくすると）、可能性を1/3にすることができる。
ちなみに、（問１）では12個中の１個が重い場合と軽い場合の可能性があるので、
全体で24通りの可能性があることになる。

（問２）ではどうか？