次のコードのメモリの消費量について

Question

次のコードのメモリの消費量について質問です。
「数百万のノードを持つT1と、数百のノードを持つT2の、２つの部分木があります。この時、T2がT1の部分木になっているかどうかを判定するアルゴリズムを作ってください。」

（解答例）
T1のノードを順に調べておき、そのノードとT2のルートが一致したら、treeMatchを呼び出します。treeMatchは2つの部分木が一致するかどうかを調べるメソッドです。

boolean containsTree(TreeNode t1, TreeNode t2) {
        if(t2 == null) { //空の木は常に部分木
            return true;
        }
        return subTree(t1,t2);
    }

    boolean subTree(TreeNode r1, TreeNode r2) {
        if(r1 == null) {
            return false; //大きい方の木が空で、部分木がまだ見つかってない
        }
        if(r1.data == r2.data) {
            if(matchTree(r1,r2)) return true;
        }
        return (subTree(r1.left,r2) || subTree(r1.right,r2));
    }

    boolean matchTree(TreeNode r1, TreeNode r2) {
        if(r2 == null && r1 == null) //両方が空の場合
        return true; //部分木に何も残ってない

        //両方ではなく、片方がからの場合
        if(r1 == null || r2 == null) {
            return false;
        }

        if(r1.data != r2.data)
            return false; //データが不一致
        return (matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right));
    }

この解法のメモリの消費量はO(log(n) + log(m))らしいのですが、なぜそうなるのでしょうか？
そもそもコードを見渡しても、データを保持する入れ物は見当たりませんが、最初にノードを受け取っているからメモリを消費するということなのでしょうか？
お分かりの方、回答お願いします。

Answer 1

すでに回答にあるように、メソッドを呼び出すたびに「どこから呼び出して、引数が何か」などの情報がスタックに積まれていきます。この時、最大でどれだけのメモリを消費するかというのがこの問題だと思われます。
一番深いところに行くまではsubTreeメソッドの条件分岐に引っかからず、

return (subTree(r1.left,r2) || subTree(r1.right,r2));

が繰り返し実行されるという状況を考えます。

基本的に式は左から右へと順番に処理されていくため、return文の||の左側、subTree(r1.left,r2)が処理されます。このメソッド起動のため、新たにスタックが積まれます。
そして起動したsubTreeでもまたsubTree(r1.left,r2)が呼び出されます。これを繰り返し、一番下に到達するまで、すなわち**最初のr1の深さの回数分スタックが積まれます。**平衡木ならばノードが2倍になって深さが1増えるので、ノード数nに対し深さはlog(n)です。つまり、**subTreeの過程で最大で積まれるメソッドの回数がlog(n)**という事になります。

目的のノードが見つかればmatchTreeで部分木の一致を探るわけですが、基本的な考え方はsubTreeの時と一緒です。「目的のノードを見つける」ことが「一致しないノードを見つけるまで繰り返す」ことに置き換わっただけで、仕組みは全く一緒です。したがってこれもr2の深さ分、r2のノード数をmとすればlog(m)回、このメソッドが積まれる事になります。

以上より、このアルゴリズムのメモリ消費量はlog(n) + log(m)と結論付けられるのです。

Comments

[退会済みユーザー]

大方理解できました。
細かい点ですが、「平衡木ならばノードが2倍になって深さが1増える」が疑問です。
rootがあって、それが右と左に子を持っている状態を考えると、トータルのノードの数は3になります。
この二分木において、右の子ノードと左の子ノードにさらにノードをそれぞれ二つずつ持たせることを考えます。
そうすると、4つのノードを追加するということになりますが、この時のトータルのノードの数は7であり、3の二倍にはなっていません。
平衡木という言葉の定義の問題でしょうか？

[swordone]

大体の話です。深さとノード数の関係性を見たとき、1程度は誤差です。ノード数が極端に多くなればわかります。

Answer 2

専門的に勉強はしておらずネット上の知識をつぎはぎしたものなので間違いがあったらすみません。

そもそもコードを見渡しても、データを保持する入れ物は見当たりませんが、最初にノードを受け取っているからメモリを消費するということなのでしょうか？

maisumakunさんが既に回答されてる通り、関数がコールされる度にその引数に関するメモリを確保するためでしょう。再帰関数は収束が始まるまで全ての実行中の関数のメモリを展開しているので最終的に必要なメモリが大きくなる傾向があります。

---

O(log(n) + log(m))らしいのですが、なぜそうなるのでしょうか？

こっちは関数が実行される回数。つまりステップ数計算だと考えれば良いと思います。
ステップ数計算参考リンク　[初心者向け] プログラムの計算量を求める方法
関数が実行された回数その引数(他あるなら)のコストが展開メモリ量です。
ただ上記サイトを見た感じステップ数はかなーりざっくり計算するみたいです。
そしてざっくりルールに倣うなら、一回の関数実行に必要なメモリ量など無視していいくらい少ない固定係数値なので(多分)無視。
関数の収束が始まるとメモリも開放されていくと思うので、実行回数関数コストは最大値で実際は少ないと思いますが、それも(多分)ざっくりルールによって無視
それでステップ数=必要メモリ量。なのかな？
(後方に行くほど自信無いですが...)

Comments

[退会済みユーザー]

すいません、後半がよくわかりませんでした。
>そしてざっくりルールに倣うなら、一回の関数実行に必要なメモリ量など無視していいくらい少ない固定係数値なので(多分)無視。

つまり、一回の呼び出し時のメモリ量を無視していいってことでしょうか？
そうすると、一回は無視できるのだから、全部無視できるってことになってしまいませんか？

＞関数の収束が始まるとメモリも開放されていくと思うので、実行回数*関数コストは最大値で実際は少ないと思いますが、それも(多分)ざっくりルールによって無視

関数コストというのは「一回の呼び出しで必要なメモリ量」という意味でまちがいないでしょうか？
そして、「無視」と書かれていますが、何を無視するのでしょうか？

[hirohiro]

ちょっと私に勘違いがあったらすみませんね。
>　一回の呼び出し時のメモリ量を無視していいってことでしょうか？
引数がt1,t2のメンバーへのメモリアドレスなら、おそらく8バイト(16?)程度だと思いますが、そうすると必要なメモリの量は、関数呼び出し回数×8byteってことになります。
しかしリンク先の記事をみてもらったらわかりますが、計算において一桁程度の係数は排除して計算しています。(桁上がりもしない程度の係数は誤差って印象)
例えば計算式が2*log(x)になるなら、ステップ数はlog(x)だといった形です。

>関数コストというのは「一回の呼び出しで必要なメモリ量」という意味でまちがいないでしょうか？
これはYes

>　そして、「無視」と書かれていますが、何を無視するのでしょうか？
関数をコールするときに引数のデータ（かデータのアドレス)が新規にメモリに確保されます。再帰関数は、自分の子供が実行されてる間は処理を終了しないので、そのメモリは確保されたままになります。
変わって末端で呼ばれた関数(それ以上再帰呼び出しの必要が無かった関数)は直ぐにreturnが実行されてそれのために確保された引数は参照されなくなり、GCに回収される(?)んじゃないかと思います。
となると、あるタイミングで瞬間的に確保が必須で手放せない量こそが、処理のために必要なメモリの量といえるのではないでしょうか？
というわけで、瞬間的に必要になるメモリの量は実は「関数呼び出し回数*2byte」では無いといえるかも知れません。(一番多く関数を展開している瞬間でも処理全般にわたって必要な関数全部が展開中ではなく閉じたものもあるだろうという意味で)
でも、それで結果が1/2だろうが1/4だろうが誤差なのでそのことも考慮しないというワイルドなルールなんじゃないかな。。とそんな風に思いました。

Answer 3

Javaでは同じ関数を再帰呼び出ししても、呼び出しごとに引数が別々に取られますが、その分メモリを消費している、ということになります。また、内部で変数を使わなくても、「次にどこから処理を再開するか」を覚えておく必要があります（コールスタック）。

こういった経緯で利用するメモリの使用量は呼び出しの深さ=（この場合は）木の深さに比例しますので、理想的に分岐した木であれば、O(log(n)+log(m))となります。

ただし、木のバランスが悪いと分岐せずに再帰が深くなって、O(n+m)になってしまうこともありえます。

Comments

[HogeAnimalLover]

特段の断りがないならば、計算量は普通「最悪の場合」を意味するはずです。題意には「理想的に分岐した木」と書かれていないので対数計算量であることにはならないと思います。

[退会済みユーザー]

とりあえずは平衡木と思って問題ないと思いますので、メモリの必要量はO(log(n) + log(m) )で問題ないと思います。
回答の中で、木の深さに比例するので、O(log(n) + log(m))となると書かれていますが、木の深さに比例すると、どうしてO(log(n) +log(m))になるのでしょうか？