■

• Algorithm ゼミで出てきた話題で気になっていたことがあったので、考えていました。
  • コップの強度は 1 から n とする。強度が i とは、高さ i-1 から落としても壊れないが i から落とせば割れる。コップの強度を確定したい。2分探索なら log n (底は2)回落とせば、コップの強度が分かる。ここでコップは k 個しかないとする。したがって k 個しか割ることができない。
  • Stragety: n を n^(1/k) 段階に分ける。それぞれの段階には n^(1-1/k) レベルの強度が含まれる。1個めのコップを下から順に落とす。割れたら n^(1/k) 段階のどこかが特定される。その段階をさらに n^(1/k) 段階に分けて同じようにテストしていく。
  • これを繰り返せば、k個のコップを k n^(1/k) 回落とせば、強度が特定される。
  • 上の方法と2分探索の関係：k n^(1/k) を最小にする k は ln(n)。このとき落とす回数は e ln(n) = 1.88 log(n)。k ≦ log(n) なら k を増やすごとに、落とす総数は減るのですね。k=O(log(n)) なら各ステップで O(1) 段階に分けるので、2分探索と同じ。