|
Halt0 |
|
#42508 Mr.ダンディさん
1回の比較につき, どちらが重いかについて2通りの可能性があるので, M回比較したとき, 全比較結果のパターンとして考えられるものは2^M通り 一方, 分銅の重さの順序として考えられるものはN!通り 2^M通りの結果を用いて, N!通りの結果を全て区別するためには 2^M ≧ N でなくてはならない. よって M ≧ ceil(log_2(N!)). という感じかと思います. #42511 uchinyanさん 私も不安でしたが, 一般の n の場合に最小の評価回数が n+ceil(log_2(n))-2 (ceil は切り上げ)であることが証明できるっぽいです. ちゃんと読んでないですが↓ http://math.stackexchange.com/questions/1601/lower-bound-for-finding-second-largest-element |
|
10月9日（木） 12:09:30
42512 |