計算量の算出について

Question

以下のメソッドは二分木が平衡かどうか調べるメソッドです。

「二分木が平衡かどうか調べる関数を実装してください。平衡木とは、どのノードの２つの部分木も、その高さの差が１以下であると定義します。」

public  static int getHeight(TreeNode root) {
        if(root == null) return 0; //基本ケース
        return Math.max(getHeight(root.left),
                getHeight(root.right)) +1;
    }

    public static boolean isBlanced(TreeNode root) {
        if(root == null) return true; //基本ケース

        int heightDiff = getHeight(root.right) - getHeight(root.left);
        if(Math.abs(heightDiff) > 1) {
            return false;
        } else {
            return isBlanced(root.left) && isBlanced(root.right);
        }
    }

「このようにすればうまくいきますが、それほど効率的ではありません。各ノードで他の部分木を再帰していますが、これはgetHeightが同じノードで繰り返し呼び出されていることになります。ですので、このアルゴリズムはO(N^2)の計算量になってしまいます。」

同じ部分が繰り返し数えられるので、非効率なのはわかるのですが、なぜO(N^2)になるのでしょうか？
考えてみたのですが、わかりませんでした。
お分かりの方、回答お願いします。

Answer 1

return文で自身を2回呼び出しているのでO(N^2)です。

Comments

[退会済みユーザー]

どうして二乗なのでしょうか？
呼び出す回数は単に二回になるだけなので、計算量は定数倍ではないのでしょうか？

[issei.]

1回の呼び出しに対して自身を1回呼び出すのがO(N)です。換言すると、Nの定数倍のオーダーです。
一方、今回のように1回の呼び出しに対して自身を2回呼び出す場合は、Nの定数倍のオーダーとNの定数倍のオーダーの直積になります。よって、Nの2乗の定数倍なのでO(N^2)です。

[退会済みユーザー]

お返事ありがとうございます。
＞1回の呼び出しに対して自身を2回呼び出す場合は、Nの定数倍のオーダーとNの定数倍のオーダーの直積になる
結果としてはそうなのかもしれないのですが、なぜそうなるのですか？
例えば、私が示したコードでisBlanced(root.left)のみを呼び出すとした場合に、計算量はO(N)になるということになりますが、これはNに比例するとは思えません。（平衡を保つのであれば、Nに比例すると思うのですが、そうとは限らないと考えました。）
できれば、プロセスを示していただきたいです。

[issei.]

いえ、isBlancedの呼び出しについてもO(N^2)です。

[issei.]

それと、考えがどうこうではなく、ソースコードが再帰呼び出しで自身を２度呼び出すからO(N^2)となるという以上のことは言えません。平衡云々の議論は、与えられたコードからは読み取れません。

[退会済みユーザー]

return isBlanced(root.left) && isBlanced(root.right);
の部分を
return isBlanced(root.left);
と変更すると、自身を一回だけ呼び出すことになるので、O(N)になるのではないでしょうか？
しかし、これは二分木の左側だけを走査することになるので、必ずしもNに比例するとは言えないのではないでしょうか？