ログイン 新規登録

お使いのブラウザ(Internet Explorer)では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ:Google Chrome(グーグル・クローム)

耐久試験において計算量を減らす方法

耐久試験において計算量を減らす方法です。


衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験をしようとしています。高さは最大でNmだと仮定します。


試験に使える生卵は2つで、衝撃吸収材の精度を知るためのアルゴリズムを考えています。


例えば、アルゴリズムの二部探索の考え方を用いると、高さの最大が3mの時、1つの生卵を高さの中間地点である1.5mから落としてみて、割れたら0m~1.499…m、割れなければ1.5m~3mの間に限界の高さがあると考えることができます。そして、狭めた範囲で最も低い高さから順番に卵を落として割れた場所が限界の高さだと言うことができます。


この場合、計算量は1+N/2でオーダ記法を用いるとO(N)になりますが、より計算量を減らせるアルゴリズムはないでしょうか。

回答(1件)

tamu先生
先生
先生 の回答 1年前
1.5m~3mだったら2.25mから落とすというように、狭めた範囲で真ん中の高さから落とす、を繰り返せば計算量は減らせます。
  • もう少し説明いただけませんでしょうか。

    例えば1.5mで落として卵が割れてしまった場合、0〜1.4999...mでは真ん中から落とすという手法は使えないと思います。

    1年前
  • 0.75mで落としてみて、割れたら0~0.75m、割れなければ0.75~1.5mと分かります。

    1年前

    tamu

    先生
  • ごめんなさい、卵は2つなんですね。

    割れるまでは真ん中、割れたら低い高さから順番が良さそうですね。



    そうすると、真ん中よりも低い方が効率が良くて

    割れるまでは1/3、割れたら低い高さから順番

    の方が効率が良くなりそうです。



    割れるまでは比率をxとして、オーダーを計算して、その最小値を求める方法でいけないですかね?

    1年前

    tamu

    先生
  • お返事ありがとうございます。

    比率をxというのは1/xということでしょうか。

    真ん中よりも低い方が効率が良いというのは、感覚的に低い方で割れたほうがその後で探索する範囲を狭められて、順番に線形探索する時の回数を減らせるということはわかりますが、なぜ1/3なのでしょうか。

    1つ目の卵を落として割れたら線形探索に切り替える、真ん中よりも低い位置の決め方がよくわかりません。

    1年前
  • 真ん中ならx=1/2、1/3ならx=1/3のつもりで書きましたが、考えやすいなら1/xとしてもいいです。



    1/3は例えです。

    切り替える位置を1/xとした時の計算量は分かりますか?

    1年前

    tamu

    先生
  • 最悪の場合の計算量は以下になると思います。

    1つ目の卵で切り替える位置を探すためにx-1回(例えばx=6のとき1/6 切り替える位置を1/xとした時、*Nx(1/x)mを下から順に線形探索するので定数回

    合わせると、x-1 + c(定数)で 計算量はO(N)  

    *1つ目の卵で切り替える位置を探したときに位置2/xで割れなくて、位置3/xで割れた場合も位置2/xから3/xの範囲をNx(1/x)m区間を順に線形探索する

    つまり、定数回   c(定数)がxの値が大きくなるほど小さくなったとしても、計算量としてはO(N)を下回る方法がなくて困っています。

    1年前
  • 定数cはN/xだと考えられます。

    1年前
  • 耐久試験において計算量を減らす方法-2のコメントに書いたのですが、耐久試験において使える生卵の個数が任意の数k個だったとしても、最悪の場合の反復回数logNよりkが小さいときの話とも関係があるでしょうか。

    1年前
  • また違う解答ですが、√Nずつの区間に分けて探索すれば2√Nですみますね。

    1年前

    tamu

    先生
  • √Nずつの区間に分けて探索すれば2√N とはどういうことでしょうか。

    もう少し詳しく教えていただけますか?

    2√Nは、計算量としてはO(N)ですよね。

    1年前
  • まず、√N,2√N,3√N,…と調べていきます。

    この時点で最悪で√N回です。



    割れたのが、例えば、2√Nだったとき、√N~2√Nで下から探索すれば、これも最悪√N回です。



    計算量としては

    2√N=O(√N)

    です。

    1年前

    tamu

    先生
  • ご説明いただきましてありがとうございます。

    試験に使える卵が2個の時はわかりました。


    補足として、卵が34、5個のように変化していくにつれて計算量はどのように変わると考えればいいのでしょうか。


    使える卵がk個の時は以下のように場合分けできると考え、



    <ol class="ol1">
  • kが十分に大きく最悪の試行回数より大きい場合、中点を分割点とする二分探索で計算量はO(logN)


  • kが最悪の試行回数より小さい場合、O(?)


    </ol>

1年前
  • 2. は、二分探索の時の最悪の試行回数がlogNなので、k&lt;logNの時のことをさしていると考えられます。

    1年前
  • k個の時は[k]√N個の区間に分割して探索を繰り返せば良いです。

    1年前

    tamu

    先生
  • ありがとうございました。

    1年前
  • 回答へコメントする
    あなたがベストアンサーに選んだ
    tamu
    さんは先生をしています

    詳しくはこちら

    他の質問・回答も見る