院試の勉強 - 丁寧だけど雑

これからは、自分が問題を解いていて「ん？」ってなったところをピックアップしてメモとして書き留めて行くことにする。

今回はこれ。

$\displaystyle n$ 個の異なる整数の最小値を求めるのに必要な比較回数の最小値を $\displaystyle C_{min}(n)$ と表す。このとき、 $\displaystyle C_{min}(n) \ge g(n)$ を証明するために示さなければならないことを述べ、 $\displaystyle C_{min}(n) \ge n-1$ を証明せよ。

問題自体は難しくなく、異なる整数から最小値を求める際の比較回数の最小は、最低でも整数の個数 $\displaystyle n$ 個よりも $\displaystyle 1$ 少ない回数の比較を行う必要があることを証明するだけである。

比較回数が最小のとき、即ち $\displaystyle n-1$ 回のときの整数の並びは、整数が昇順であるような状態で、先頭と $\displaystyle 2$ 番目〜 $\displaystyle n$ 番目の各値を比較することによって、比較回数( $\displaystyle n-1$ )回が実現される。

もし、これを下回る回数、例えば、 $\displaystyle n-2$ 回で比較が出来るときは、 $\displaystyle n$ 個の整数の中に最小値となり得る候補が2つ存在するときである。これは問題の仮定と矛盾する為、 $\displaystyle C_{min}(n)$ は $\displaystyle C_{min}(n) \ge n-1$ となる。

最初はこんな感じかなって解いたんだが、後で疑問が生じた。最小値となり得る候補が2つ存在するからと言って、比較回数は減るものなのか？

いま、以下のような整数を考える。

$\displaystyle 1,2,3,1,5,6$

このとき、 $\displaystyle n=6$ である。まずはこのまま先頭と各要素を比較していく。比較の途中で(先頭( $\displaystyle 0$ 番目)の) $\displaystyle 1$ と( $\displaystyle 3$ 番目の) $\displaystyle 1$ の比較を行う。ここで比較を行った場合、比較の回数は結局( $\displaystyle n-1$ )回になってしまうのではないだろうか？

うーん、この整数の列の $\displaystyle n$ 個を全て同じ値にしたと仮定しても、結局先頭要素と各要素の大小関係を確認する必要はあると思うので( $\displaystyle n-1$ )回の比較を行いそうなものだが…

分からないというか、僕の思い違いならそれで良いのだが、腑に落ちない…(正解は上記のものでおおよそ合ってました。)