

二分探索木の平均の計算量を示す方法について  
下記画像の結果よりすべてのnについてT(n)<4logn+1が示せたことになり、木の平均深さがO(logn)であることがわかるそうです。  
下記画像の二分探索木の平均の計算量を示す方法について5点不明な箇所がございます。  
⑴ T(n)<= alogn+bを仮定する理由について  
上記のように仮定する理由は最終的に計算量はaとbを除いて考えれるからでしょうか。

⑵n=1のときはb=1とすれば成立する  
上記の記載についての意図が理解できません。

⑶画像下の式で<=としている箇所についてです。  
なぜ<=としているのでしょうか。

[![二分探索木の計算量の簡単な証明](https://i.stack.imgur.com/MIu2O.jpg)](https://i.stack.imgur.com/MIu2O.jpg)  
⑷式の2行目と3行目のシグマの右側ailogi+iをシグマの左側2a/k^2に変化する意図が理解できません。（途中式が浮かびません）

[![画像の説明をここに入力](https://i.stack.imgur.com/4P0mp.jpg)](https://i.stack.imgur.com/4P0mp.jpg)

⑸ここで1~k/2とk/2+1~k-1に分けるの式がほぼ全く理解できません。

疑問点をうまくまとめれませんでしたが、ご解説いただければ幸いです。

参照：新情報/通信システム工学 データ構造とアルゴリズム


CC BY-SA 4.0
2019-03-19T23:09:39.110
53560
2019-03-20T09:37:34.430
32396
question
アルゴリズム 数学
二分探索木の平均の計算量を示す方法について


「解を仮定してその正しさを帰納法で示す方法をとる」という説明が理解できない、より具体的には『帰納法』が何なのかを十分に理解していらっしゃらないのだと思われます。

『１から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の時にも正しい  
の２つを示せば足ります。

(a)で、nが一番小さい自然数である1の時に成り立つことが示され、  
(b)で、nが１の時に正しいのだから、nが2の時も正しい  
さらに、(b)で、nが2の時に正しいのだから、nが3の時も正しい  
...というように(b)を繰り返し使っていくと、すべての自然数で成立することが示せます。

このように、  
・ある値で成立する事と、  
・値を変更（上の例では"１増やす"）しても成り立つ、  
・値の変更（"１増やす"）を繰り返す事で、公式が適用できる範囲が一般化できる  
をもって公式の証明をする方式を帰納法と言います。

＝＝＝  
「２分木探索」について考えてみましょう。  
２分木は「左の子の値＜親の値＜右の子の値」が成り立つような値をノードが持つ木構造です。  
２分木探索は、２分木を使った検索で、根のノードから初めて、探す値と一致するまでノードを辿っていきます。値が一致するノードが見つかるまでに値の比較をした回数が計算量になります。

２分木が左右均等である場合、木の高さがMなら、ノードの数は(2 ^ M)-1になります。  
ノード数はほぼ2のM乗ですから、ノード数nの左右均等な２分木の高さは log2(N)ほどになります。log2は、２を底とする対数。  
２分木の高さは、計算量の上限（最悪値）ですから、左右均等な２分木の場合は計算量の上限はO(log(N))といえます。左右均等な場合が、計算量の上限が最小です。

計算量の上限が大きいのは、一方にだけ枝が伸びた２分木（一直線状の木）で、計算量の上限はNです。

＜⑴ T(n)<= alogn+bを仮定する理由について＞  
どちらが支配的であっても大丈夫なように両方の場合を勘案して上限と仮定されたのが

> T(n)<= alogn+b

という式です。  
a*log(n)の部分が左右均等な木の場合の上限値、bが一方にだけ枝が伸びた木の場合の上限値で、両方を加えたものは、どちらが支配的でも実際の上限より小さくならない事を表しています。

aやbといった値は、帰納法による証明を始める時点では未定です。

＜⑵n=1のときはb=1とすれば成立する＞  
例えば、２分木が１つのノードだけの場合、計算量(T(n))は１（比較するノードは１個だけ）、ノードの個数(n)は1、一方に枝が伸びた木の場合の上限値(b)は１。そして、log2(0)は１。  
T(1) = a*0 + 1 = 1 となるので、T(n)<= alogn+bがn=1の時に成立する。（その時のbは１）

＜⑶画像下の式で<=としている箇所についてです。＞  
alogn+bは計算量(T(n))の上限なので、 T(n) < 計算量の上限(alogn+b)が成り立つ。  
しかし、(2)のように等号が成り立つ場合もある。  
なので、"<"ではなく"<="としている。

＝＝  
このような道筋で考えていくと理解できるのではないでしょうか。


CC BY-SA 4.0
2019-03-20T02:46:53.903
53568
2019-03-20T02:46:53.903
217
53560
answer


回答がかなり長くかつ数式を含むものなので回答の PDF を作成しそれへのリンクを貼ります。  
参考になれば  
[回答 PDF
へのリンク](https://drive.google.com/open?id=1QHhrCu4-2Sn48rYnyawEruyxINansKCg)  
<https://drive.google.com/open?id=1QHhrCu4-2Sn48rYnyawEruyxINansKCg>

正直に申し上げるとこの書籍を読み続ける前に高校の数学の復習(今回は数列分野)を最低でも章末問題を完答できる程度に勉強をなさったほうがよりスムーズにこの書籍を読み込めるようになると思います。


CC BY-SA 4.0
2019-03-20T09:37:34.430
53589
2019-03-20T09:37:34.430
27509
53560
answer