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

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

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

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

Q&A

解決済

1回答

1767閲覧

以下のコードの計算量について

退会済みユーザー

退会済みユーザー

総合スコア0

Java

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

0グッド

0クリップ

投稿2016/09/04 12:37

以下のコードの計算量についての式の展開が理解できません。
誤植とも思えませんので、非常に混乱しております。

「各ノードにある値を持った二分木が与えられた時、合計値が与えられた値になる全ての経路を出力するアルゴリズムを設計していください。経路の始まりと終わりは、二分木のどのノードであっても構いませんが、片方のノードがもう片方のノードの祖先になっているもののみを考えることとします。」

方針
全てのノードにおいて合計値になるかどうかを「さかのぼって」調べていきます。そのノードを始点とするパスを考えるのではなく、そのノードを終点とするパスを考えるということです。

ノードnから再帰的に探索する際、関数にはノードnまでの、ルートからのパスを渡すようにします。関数内ではノードnから上位ノードに向かって合計値を計算し、sumと一致した場合は出力するようにしておきます。

Java

1public void findSum(TreeNode node, int sum, int[] path, int level) { 2 if(node == null) { 3 return; 4 } 5 6 /*現在のノードをパスに挿入*/ 7 path[level] = node.data; 8 9 /*このノードで終わり和が一致する経路を探す*/ 10 int t = 0; 11 for(int i = level; i >= 0; i--) { 12 t += path[level]; 13 if(t == sum) { 14 print(path, i, level); 15 } 16 } 17 18 /*現在のノード以下の頂点を探索*/ 19 findSum(node.left, sum, path, level + 1); 20 findSum(node.right, sum, path, level + 1); 21 22 /*現在の頂点の値を配列pathから削除する。 23 削除しなくても、無視されるため必ずしも必要ではないが、そうしておく方がいい習慣と言える 24 */ 25 path[level] = Integer.MIN_VALUE; 26 27 public void findSum(TreeNode node, int sum) { 28 int depth = depth(node); 29 int[] path = new int[depth]; 30 findSum(node, sum, path, 0); 31 } 32 33 public static void print(int[] path, int start, int end) { 34 for(int i = start; i <= end; i++) { 35 System.out.print(path[i] + " "); 36 } 37 System.out.println(); 38 } 39 40 public int depth(TreeNode node) { 41 if(node == null) { 42 return 0; 43 } else { 44 return 1 + Math.max(depth(node.left), depth(node.right)); 45 } 46 } 47 }

このアルゴリズムの計算量について考えます。深さrのノードであれば、さかのぼる方法で探索するときにr回分の処理が必要になります。全部でnノードあるとすれば、1つのノードにつき、平均log(n)回の処理になりますから、平均計算時間はO(n log(n))と考えることができます。
数学的に見ると、深さrには2^r個のノードがあることに注意して、
1 * 2^1 + 2 * 2^2 + 3 * 2^3 +...+ d * 2^d
= 2 * (d -1) * 2^d + 2

n = 2^d
d = log(n)
したがって、
O(2 * (log(n) - 1) * 2^(log(n)) + 2)
= O(n log(n) )

以上の計算量の導出について質問が2点あります。

質問1:
「深さrのノードではr回分の処理が必要となる」と書いていますが、正確にはr+1回ではないでしょうか?(自身の分もカウントするので)
それはカウントする必要はないのでしょうか?

質問2:
n = 2^d
という等式が理解できません。
仮定によると、nというのはノードの総数のはずなのですが、ここではいきなり末端の葉の数になっていますよね?
nがノードの総数ならば、計算量は上の導出で問題ないと思うのですが、nが末端の葉の数とすれば、追加の操作が必要になると思います。
すなわち、深さdの点での計算量はO(n log(n))、深さd-1での計算量は0( m log(m)) (m = 2^(d-1))のようにして、それぞれの深さの和を取る必要があると思うのです。

お分かりの方、回答お願いします。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

質問1:

「深さrのノードではr回分の処理が必要となる」と書いていますが、正確にはr+1回ではないでしょうか?(自身の分もカウントするので)
それはカウントする必要はないのでしょうか?

カウントしても良いと思います。ただ、オーダーの議論をする際には1回分は誤差です。

質問2:

n = 2^d
という等式が理解できません。
仮定によると、nというのはノードの総数のはずなのですが、ここではいきなり末端の葉の数になっていますよね?

nはノードの総数ではありません。おっしゃるとおり、この場合は末端の葉の数を指しているだけです。末端のノードから遡るという趣旨から、始点のノード数(今回の計算量の基準)を求めているようです。

あと、余計なお節介かもしれませんが、この文献はお世辞にも丁寧な解説とは言いがたいので、参考文献を変えた方が良いと思います。

投稿2016/09/04 16:04

issei.

総合スコア326

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/09/05 14:18

回答ありがとうございました。 >余計なお節介かもしれませんが、この文献はお世辞にも丁寧な解説とは言いがたいので、参考文献を変えた方が良いと思います。 うーん、そうですか。 でも、あと少しで終わるので、もう少しだけ辛抱するつもりです。 ご心配ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問