- 締切済み
探索木の問題について
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- kmee
- ベストアンサー率55% (1857/3366)
n個のデータから探索する、もっとも単純な方法は、「n個全部調べる」ことです。 これは、O(n)の計算量だということは、おわかりになるかと思います。 「探索効率を高めるため（探索経路を短くするため）」ということは、O(n)より小さいオーダーのアルゴリズムを必要とします。 さて。 Aだと、結局、 n分探索木となってしまいます。(ルートを探索対象とすれば (n-1)分木 ) これから探索するのは、結局は、上の「n個全部調べる」と同じことです。 ちなみに、m=2 のときの「二分木」はよく出てくるものです。 計算量の考えは同じです。
- ok-kaneto
- ベストアンサー率39% (1798/4531)
Aの場合、子がm個までしかありませんので最大m個までしか探索できません。なので計算量はo(1)ですね。 (この数に関わらず一定)・・・計算量と深さ(木の高さ)が比例すると思ってください。 答えのヒントはlogですねー。計算量をx、全部の子の数をnとすると m^xとnが比例する関係になりますね。xをmとnで表すと...
関連するQ&A
- 探索問題
ｎ個のデータがあり，その中から与えられたキー を持つデータを探索するとき,最大計算時間の下界が Ω(log ｎ)であることを証明したいのですが,どうしても わかりません．どのようにしたらよいかどなたか教えて 下さい．よろしくお願いします．
- ベストアンサー
- その他（プログラミング・開発）
- 二分探索木のパターン数
二分探索木のパターン数 二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。 例えば 6 ／ ＼ 4 9 ／＼ ／ 2 5 8 ／ 7 こんな感じです。 http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86%e6%9c%a8 で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。 というものです。図を書いて色々考えてみたのですが求め方が分かりません。 全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか？
- ベストアンサー
- 数学・算数
- ゲーム木探索について教えてください。
次のような問題が出たのですが、解けなくて困っています。 「ゲーム木の深さ（根から葉までの最大距離）がｈ、葉以外の状態の子の数が常に2個であるとしたとき、ゲーム木の状態数とｈにはどのような関係がありますか。子の数が葉を除いて常にｂ個であるとしたらどうでしょう。」 どなたか助けてください。 また、このような問題を解くのには、どのような本を参考にしたらよいのでしょうか？教えてください。
- ベストアンサー
- その他（学問・教育）
- 二分探索木と二分探索の違い
高校のときにCOBOLを用いた二分探索を習いました。 今大学でコンピューター科学を勉強しています。予習をしていたら二分探索木が出てきました。 添付画像のような二分木があるとき、a～jの各ノードに１～１０の整数のどの整数が入るか。 という問題ですが、ちんぷんかんぷんです。 二分探索木というのは、検索で用いる二分探索と同じ考えなのでしょうか。 もし、同じなら、１～１０の中央値の５がルートになりますよね。 このような問題の簡単な求め方があれば教えてください。お願いいたします。
- ベストアンサー
- その他([技術者向] コンピューター)
- 二分探索のアルゴリズム
分からない問題があります。 ・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。 ・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。 ２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが そのようになる説明をどのようにしたらいいか。また logn<n となるのは わかるのですが理由をどう説明したらいいのか分かりません。 どなたかお教え下さい。
- ベストアンサー
- 科学
- アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 経路探索
よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(n行,m列)の経路があります。 (0,0)－(0,1)－(0,2)－(0,3) (1,0)－(1,1)－(1,2)－(1,3) (2,0)－(2,1)－(2,2)－(2,3) (3,0)－(3,1)－(3,2)－(3,3) (4,0)－(4,1)－(4,2)－(4,3) スタートを(4,3)としてゴール(0,0)にたどり着く全ての経路を求めたいです。 条件としてある点から 左(例えば(4,3)⇒(4,2)) 上(例えば(4,3)⇒(3,3)) 斜め(例えば(4,3)⇒(3,2)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。
- ベストアンサー
- C・C++・C#
- 二分探索の平均探索回数
こんにちは、 二分探索の最大探索回数がlog2N+1なのは 書籍にある計算式の変換で理解できたのですが、平均探索回数がlog2Nなのが理解できません。 書籍では『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』と書かれていますが どういう意味なのか判りません。 そこで具体的に考えてみました。 例えば8個のデータの中から探す場合、 a[0]、a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7] とデータが並んでいて、 それぞれの位置に目的の値が入っていた時の探索回数は、 3回、2回、3回、1回、3回、2回、3回、4回 と考えました。 a[1]の場所に目的の数があった場合、 2回目の探索で見つかる、という意味合いです。 最大探索回数はa[7]の時に4回となり、log2N+1になっています。 この考え方でNを増やしていった所、最大探索回数はlog2N+1になりそうです。 そこで上記の場合の平均探索回数の方は、 (3+2+3+1+3+2+3+4)/8 と計算し、2.625と考えました。 この考え方でNを増やしていくと 16コ：3.375 32コ：4.21875 64コ：5.125 128コ：6.0703125 …と、 平均探索回数がlog2Nではなくlog2N-1に近づいていきます。 考え方の間違っている箇所の指摘をお願いします。
- 締切済み
- その他（プログラミング・開発）
- データ構造についての質問です。
データ構造についての質問です。 １．平均16個の子に持つようなB木があり、その深さが３である場合，記録されている データの個数はどのくらいになるか計算しなさい。 ２．B 木に利用するm 分木について，m の値を大きくすればするほど探索効率は良くなる。 正しいか，正しくないか？正しくない場合はその理由を答えなさい。 という2つの問題があります。1番は記録されているデータの個数の計算方法がわかりません。2番はmを大きくすると深さが浅くなるので効率は良くなると思うのですが合っているかわかりません。 どなたかご指導よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
