1

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

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

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

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

画像の説明をここに入力

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

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

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

2 件の回答 2

2

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

『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です。

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

 T(n)<= alogn+b

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

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

<⑵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)

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

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

1
  • ご解説ありがとうございます。 ご指摘どおり帰納法が何なのかを十分に理解しておりませんでした。
    – sample
    Commented 2019年3月26日 12:26
2

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

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

4
  • 1
    3/21 01:42 (3)および(4)について:でミスがあったので修正しました。iT(i)≦a log(i)+1 を T(i)≦a log(i)+1 へ Commented 2019年3月20日 16:43
  • 丁寧な解説ありがとうございます。 本書を読む中で高校の数学が理解できていないことに気づきました。 とりあえず数学Bの教科書を購入し直しました。 1~k/2とk/2+1~k-1の途中式の変形も理解できなかったので数学を復習し直し再度トライしようと考えています。
    – sample
    Commented 2019年3月26日 12:21
  • 土台さえしっかりしていればその上にいろいろ築くのは楽になります。遠回りのようですがこれが一番の近道となりますので頑張ってください。また、1〜k/2とk/2+1〜k-1に分ける考え方はその手法がわかったとしても変形に手間取るかもしれません(難関大理系入試レベル?)。分からないことがあったらまた質問してくださいね。 Commented 2019年3月26日 12:38
  • ありがとうございます。基礎作りに励みます。
    – sample
    Commented 2019年3月26日 13:20

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。