質問: 二分探索木の平均の計算量を示す方法について 下記画像の結果よりすべてのnについてT(n)<4logn+1が示せたことになり、木の平均深さがO(logn)であることがわかるそうです。 下記画像の二分探索木の平均の計算量を示す方法について5点不明な箇所がございます。 (1) T(n)<= alogn+bを仮定する理由について 上記のように仮定する理由は最終的に計算量はaとbを除いて考えれるからでしょうか。 (2)n=1のときはb=1とすれば成立する 上記の記載についての意図が理解できません。 (3)画像下の式で<=としている箇所についてです。 なぜ<=としているのでしょうか。 ![二分探索木の計算量の簡単な証明](https://i.stack.imgur.com/MIu2O.jpg) (4)式の2行目と3行目のシグマの右側ailogi+iをシグマの左側2a/k^2に変化する意図が理解できません。(途中式が浮かびません) ![画像の説明をここに入力](https://i.stack.imgur.com/4P0mp.jpg) (5)ここで1~k/2とk/2+1~k-1に分けるの式がほぼ全く理解できません。 疑問点をうまくまとめれませんでしたが、ご解説いただければ幸いです。 参照:新情報/通信システム工学 データ構造とアルゴリズム
回答: 「解を仮定してその正しさを帰納法で示す方法をとる」という説明が理解できない、より具体的には『帰納法』が何なのかを十分に理解していらっしゃらないのだと思われます。 『1からnまでの自然数の和は(n*(n+1))/2 で求められる』という公式を例にして、帰納法による証明がどんなものか示します。 (自然数というのは、0より大きな整数の事。1,2,3,4,5,....というような数) この公式が正しい(nがどんな自然数であっても成立する)ことを示すには、 (a) nが1の時、正しい (1*(1+1))/2 = (1*2)/2 = 2/2 = 1 (b) nがXの時に正しければ、nがX+1の時にも正しい の2つを示せば足ります。 (a)で、nが一番小さい自然数である1の時に成り立つことが示され、 (b)で、nが1の時に正しいのだから、nが2の時も正しい さらに、(b)で、nが2の時に正しいのだから、nが3の時も正しい ...というように(b)を繰り返し使っていくと、すべての自然数で成立することが示せます。 このように、 ・ある値で成立する事と、 ・値を変更(上の例では"1増やす")しても成り立つ、 ・値の変更("1増やす")を繰り返す事で、公式が適用できる範囲が一般化できる をもって公式の証明をする方式を帰納法と言います。 === 「2分木探索」について考えてみましょう。 2分木は「左の子の値<親の値<右の子の値」が成り立つような値をノードが持つ木構造です。 2分木探索は、2分木を使った検索で、根のノードから初めて、探す値と一致するまでノードを辿っていきます。値が一致するノードが見つかるまでに値の比較をした回数が計算量になります。 2分木が左右均等である場合、木の高さがMなら、ノードの数は(2 ^ M)-1になります。 ノード数はほぼ2のM乗ですから、ノード数nの左右均等な2分木の高さは log2(N)ほどになります。log2は、2を底とする対数。 2分木の高さは、計算量の上限(最悪値)ですから、左右均等な2分木の場合は計算量の上限はO(log(N))といえます。左右均等な場合が、計算量の上限が最小です。 計算量の上限が大きいのは、一方にだけ枝が伸びた2分木(一直線状の木)で、計算量の上限はNです。 <(1) T(n)<= alogn+bを仮定する理由について> どちらが支配的であっても大丈夫なように両方の場合を勘案して上限と仮定されたのが > > T(n)<= alogn+b > > > という式です。 a*log(n)の部分が左右均等な木の場合の上限値、bが一方にだけ枝が伸びた木の場合の上限値で、両方を加えたものは、どちらが支配的でも実際の上限より小さくならない事を表しています。 aやbといった値は、帰納法による証明を始める時点では未定です。 <(2)n=1のときはb=1とすれば成立する> 例えば、2分木が1つのノードだけの場合、計算量(T(n))は1(比較するノードは1個だけ)、ノードの個数(n)は1、一方に枝が伸びた木の場合の上限値(b)は1。そして、log2(0)は1。 T(1) = a*0 + 1 = 1 となるので、T(n)<= alogn+bがn=1の時に成立する。(その時のbは1) <(3)画像下の式で<=としている箇所についてです。> alogn+bは計算量(T(n))の上限なので、 T(n) < 計算量の上限(alogn+b)が成り立つ。 しかし、(2)のように等号が成り立つ場合もある。 なので、"<"ではなく"<="としている。 == このような道筋で考えていくと理解できるのではないでしょうか。