質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

解決済

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

削除済ユーザー
削除済ユーザー

総合スコア0

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

3回答

0評価

0クリップ

1312閲覧

投稿2016/09/04 08:01

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

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

Java

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))らしいのですが、なぜそうなるのでしょうか?
そもそもコードを見渡しても、データを保持する入れ物は見当たりませんが、最初にノードを受け取っているからメモリを消費するということなのでしょうか?
お分かりの方、回答お願いします。

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。