計算量について

[piro]

計算量の導出方法についての質問です。

添付しました”関数insertの最悪時間計算量を２分木の節点数nを用いたオーダ表記で示しなさい、
ただし、関数insertの引数nは３５、３６行目のように０から始まり、関数insertの実行の度に１ずつインクリメント
される”
、という問題で解法手順がわからずに困っています。

どなたかアドバイス、ご教授をしていただけるとありがたいです。
よろしくお願いします。

[Poco]

insert関数が何をする関数か、理解されてますか？

[piro]

ぽこさん＞

はい、insert関数は、引数である*Aのn番目にxの値を代入するという動作ですよね。
返り値は、nをインクリメントした値です。
それで、exhange関数は、大まかに言うと配列内の並びを適せつに並び替えるという処理をしていると
考えています。

[Poco]

適切な並びとは、どういった状態ですか？

[dic]

木構増で詳しい内容を書いてください
http://ja.wikipedia.org/wiki/%E6%9C%A8% ... %E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)

木構造にも種類があって、色々と回答が異なってきます

[piro]

ぽこさん＞＞
返信遅くなりすみません。
関数exchangeでは、左の節、右の節、左右共通の上位節を比較し、その後この３つの節で一番小さい値を所持している
節を左右共通の上位節の値と交換する、という処理を行います。

すなわち、左右共通の節＜左の節、右の節というならびになるように並び替えていると考えています。

[piro]

dicさん＞＞

返信遅くなりましてすみません。
このプログラムは、2分木を実装しています。

よろしくお願いします。

[Poco]

> 左右共通の節＜左の節、右の節というならびになるように並び替えていると考えています。

そうですね。
加えて重要なのは、「全ての節で」その条件を満たさなければならないことです。
そのために、exchange()の中でexchnage()を呼んでいます。

それを踏まえた上で、新しい要素を木の末端に追加したたとき、この新しい要素は
最大でどこまで移動することが考えられますか？

＃ちなみに、こういう性質をもった木をヒープ（二分）木といいます。

[piro]

ぽこさん＞＞

例1：
　　　2
　　4　　6
　5　7　8　9
　
このヒープ木の一番左のルートに1を追加するとき、3回ノード交換が行われます。

例2：
　　　2
　　4　　6
このヒープ木の一番左のルートに1を追加するとき、２回ノード交換が行われます。

これらの例から最大でｎ回ノード交換が行われると推測できます。
ｎは、新規ノードを追加する階層の場所を表わします。


このような考えでよろしいでしょうか？
よろしくお願いします。

[Poco]

合っています。
では最後。
木の要素数nに対する木の階層dをnの式で表わしてください。
それが最大計算量のオーダとなります。

[piro]

ぽこさん＞＞

迅速な返信ありがとうございます。
完全2分木のノード数と階層の関係ならば、

ｎ＝2＾(d+1) -1
ということを判断できるのですが・・・・

ヒープ木の場合は、完全2分木とは構造が異なるので、上記の式はヒープ木には当てはまりませんですよね？

[Poco]

計算量のオーダの話なんで、細かい係数を考えなければヒープ木に当てはまりますよ。
なので、
n=2^dで良いと思います。
これをd=の式に変換すれば、求める計算量オーダが出ます。

[piro]

ぽこさん＞＞

返信遅くなりすみません。
ヒープ木にもあてはまるのですか。

では、d＝log2(n)が今回の問題の最悪計算量となるのですね。

[Poco]

> では、d＝log2(n)が今回の問題の最悪計算量となるのですね。

そうなります。
思考の流れは、私とpiroさんのやりとりを参考にしてください。

----おまけ
ｎ＝2＾(d+1) -1をdについて解くと、
d＝log2(n+1)-1

となりますんで、dの計算量オーダーはO(log(n)）となります。
＃なので、オーダに関しては細かい係数は気にする必要はありません。

[piro]

単純に答えだけを教えるのでなく、１から考え方を教えてくださり本当にありがとうございます。
とてもわかりやすく、理解することができました。

色々ありがとうございました。