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

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

ただいまの
回答率

90.49%

  • Java

    16139questions

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

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

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 790
退会済みユーザー

退会済みユーザー

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

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

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

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

public void findSum(TreeNode node, int sum, int[] path, int level)  {
        if(node == null) {
            return;
        }

        /*現在のノードをパスに挿入*/
        path[level] = node.data;

        /*このノードで終わり和が一致する経路を探す*/
        int t = 0;
        for(int i = level; i >= 0; i--) {
            t += path[level];
            if(t == sum) {
                print(path, i, level);
            }
        }

        /*現在のノード以下の頂点を探索*/
        findSum(node.left, sum, path, level + 1);
        findSum(node.right, sum, path, level + 1);

        /*現在の頂点の値を配列pathから削除する。
        削除しなくても、無視されるため必ずしも必要ではないが、そうしておく方がいい習慣と言える
         */
        path[level] = Integer.MIN_VALUE;

        public void findSum(TreeNode node, int sum) {
            int depth = depth(node);
            int[] path = new int[depth];
            findSum(node, sum, path, 0);
        }

        public static void print(int[] path, int start, int end) {
            for(int i = start; i <= end; i++) {
                System.out.print(path[i] + " ");
            }
            System.out.println();
        }

        public int depth(TreeNode node) {
            if(node == null)  {
                return 0;
            } else {
                return 1 + Math.max(depth(node.left), depth(node.right));
            }
        }
    }

このアルゴリズムの計算量について考えます。深さ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))のようにして、それぞれの深さの和を取る必要があると思うのです。

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

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

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

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

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

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

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

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

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

0

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/09/05 23:18

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

    キャンセル

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

  • Java

    16139questions

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