[データ構造・アルゴリズム]ソーティングについて

質問

以下の空欄に入る言葉がわからないのでどなたか教えてください．

n個のデータをソートすることを考える．n個のデータの大小関係は(1)通りある．1回の比較操作で，上手くいけば比較対象のデータは1/2になる．従って，k回の比較操作で，比較対象のデータは(2)になる．従って，k回の比較操作で全てのデータの大小関係を知るためには，(3)という関係が必要である．
2を底とした両辺の対数をとるとk≧log(n!)という関係が成立する．
Stirlingの公式 n!≒√2πnn^ne^(-e)を利用して
log(n!) = (中略) = n log n - n log e + 1/2 log(2πn)となる．
このうち(4)に比べて他の項は急速に小さくなるので，最終的には
log(n!) ≒ n log n と考えてよい．つまり，並べ替えには最低(5)の計算の手間が必要であることがわかる．

自分で考えた答えは
(1)log(n!)
(2)n^-k
(3)k ≧ log(n!)
(4)n log n
(5)n log n

なのですが・・・どうでしょうか？非常に困っているので，よろしくお願いします！

回答No.1

Tacosan · ベストアンサー

(1), (2) は間違っています. 多分, ちょっとした勘違いをしてるんだと思う. (3) は合っているといえば合っているんだけど, 流れからは間違いでしょうね.
(1): 例えば n=3 のとき, n個のデータの大小関係は何通りあるか数えてみましたか? その答えは, log n! で表すことができますか?
(2): どこから n が出てきたのでしょうか? 「1回の比較操作で, 上手くいけば比較対象のデータは 1/2 になる」とありますね. じゃあ, 2回の比較操作ではどれだけになりますか?
(3): その下に「2 を底とした対数をとると」とあるので, そのあとの式の「2 を底とした対数をとる前の式」が入るはずですよ.

お礼

回答ありがとうございます！
考え直したのですが
(1) n!
(2) 2^-k
(3) 2^k ≧ n!
でしょうか？

回答No.2

Tacosan

はい, それで OK です.
ただ, 問題の文面が若干あやしいけど....

お礼

おかげさまで大変助かりました、本当にありがとうございました！
>>問題の文面が若干あやしい
そうなんですか！驚きです…