質問: 耐久試験において計算量を減らす方法 耐久試験において計算量を減らす方法です。 衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験をしようとしています。高さは最大でnmだと仮定します。 試験に使える生卵は2つで、衝撃吸収材の精度を知るためのアルゴリズムを考えています。 例えば、アルゴリズムの二部探索の考え方を用いると、高さの最大が3mの時、1つの生卵を高さの中間地点である1.5mから落としてみて、割れたら0m~1.499...m、割れなければ1.5m~3mの間に限界の高さがあると考えることができます。そして、狭めた範囲で最も低い高さから順番に卵を落として割れた場所が限界の高さだと言うことができます。 この場合、計算量は1+n/2でオーダ記法を用いるとo(n)になりますが、より計算量を減らせるアルゴリズムはないでしょうか。
回答: 1.5m~3mだったら2.25mから落とすというように、狭めた範囲で真ん中の高さから落とす、を繰り返せば計算量は減らせます。