探索木の問題について

質問

探索木について。
探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。
説明してください。

という問題なのですが
画像のA,Bのタイプのどちらで考えればいいのかわかりません
そこで、どちらのタイプで考えればいいのか
あわよくば、問題についても答えを教えてください

よろしくおねがいします

回答No.2

kmee

n個のデータから探索する、もっとも単純な方法は、「n個全部調べる」ことです。
これは、O(n)の計算量だということは、おわかりになるかと思います。

「探索効率を高めるため（探索経路を短くするため）」ということは、O(n)より小さいオーダーのアルゴリズムを必要とします。

さて。
Aだと、結局、 n分探索木となってしまいます。(ルートを探索対象とすれば (n-1)分木 )
これから探索するのは、結局は、上の「n個全部調べる」と同じことです。

ちなみに、m=2 のときの「二分木」はよく出てくるものです。
計算量の考えは同じです。

回答No.1

ok-kaneto

Aの場合、子がm個までしかありませんので最大m個までしか探索できません。なので計算量はo(1)ですね。
(この数に関わらず一定)・・・計算量と深さ(木の高さ)が比例すると思ってください。

答えのヒントはlogですねー。計算量をx、全部の子の数をnとすると
m^xとnが比例する関係になりますね。xをmとnで表すと...