1

どういうわけか、順不同および事前順トラバーサルデータから二分木を構築するためのアルゴリズムを書くことができました。

このアルゴリズムの時間と空間の複雑さを計算する方法がわかりません。

私の推測では

first pass  --> n(findInNode) + n/2 (constructTree) + n/2 (constructTree)
second pass --> n/2(findInNode) + n/4 (constructTree) + n/4 (constructTree)
etc..

したがって、約（3logn）になるはずです

私が間違っている場合は修正してください。

public class ConstructTree {
    public static void main(String[] args) {
        int[] preOrder = new int[] { 1, 2, 3, 4, 5 };
        int[] inOrder = new int[] { 2, 1, 4, 3, 5 };

        int start = 0;
        int end = inOrder.length -1;
        Node root =constructTree(preOrder, inOrder, start, end);

        System.out.println("In order Tree"); root.inOrder(root);
        System.out.println("");
        System.out.println("Pre order Tree"); root.preOrder(root);
        System.out.println("");

    }

    public static int preInd = 0;
    public static Node constructTree(int[] pre, int[] in, int start, int end) {
        if (start > end) {
            return null;
        }

        int nodeVal = pre[preInd++];
        Node node = new Node(nodeVal);
        if (start != end) {
            int ind = findInNode(nodeVal, in, start, end);
            node.left = constructTree(pre, in, start, ind-1);
            node.right = constructTree(pre, in, ind+1, end);
        }
        return node;
    }

    public static int findInNode(int nodeVal, int[] in, int start, int end) {
        int i = 0;
        for (i = start; i <= end; i++) {
            if(in[i] == nodeVal)
            {
                return i;
            }
        }
        return -1;
    }

}
4

2 に答える 2

1

実行時の複雑さを見積もるには、簡単なものから始めましょうfindInNode。

T findInNode =Ο（n）

再帰呼び出しがあるため、見積もりconstructTreeは少し難しくなります。ただし、このパターンを使用して、…をローカルコストと再帰コストに分割できます。

の呼び出しごとに、 T findInNode =Ο（nconstructTree ）のローカルコストと、 nの代わりにn -1を使用した2つの再帰呼び出しがあります。それでconstructTree

T‍ <sub>constructTree（n ） = T findInNode（n）+ 2・TconstructTree（n -1））

の再帰呼び出しの数は、のconstructTree呼び出しごとに2倍になるconstructTreeため、再帰呼び出しツリーは、再帰ステップごとに次のように大きくなります。

                  n                    | 2^0·n = 1·n
         _________|_________           |
        |                   |          |
       n-1                 n-1         | 2^1·n = 2·n
    ____|____           ____|____      |
   |         |         |         |     |
  n-2       n-2       n-2       n-2    | 2^2·n = 4·n
  / \       / \       / \       / \    |
n-3 n-3   n-3 n-3   n-3 n-3   n-3 n-3  | 2^3·n = 8·n

constructTreeしたがって、の最初の呼び出し後の呼び出しの総数constructTreeはnであり、再帰呼び出しの最初のステップの後はn + 2・n呼び出し、2番目のステップの後はn + 2・n + 4・nというようになります。 。また、この再帰呼び出しツリーの合計の深さはnであるため（各再帰nは1ずつデクリメントされます）、合計の合計呼び出しの数は次のconstructTreeようになります。

2 0 + 2 1 + 22 + …+ 2n = 2 n + 1 -1

したがって：

T‍ <sub>constructTree（n）=（2 n + 1 -1）・n∈Ο（2n）。

したがって、アルゴリズムには指数関数的な時間計算量があります。

の再帰呼び出しごとに1のローカルスペースコストがあるため、スペースの複雑さもΟ（2 nconstructTree ）です。

于 2012-07-02T20:54:02.280 に答える
0

時間計算量 = O(n^2)。2 回の再帰呼び出しでは、O(n^2) である順次検索に O(n) を使用する各ノード構成で、バイナリ ツリーを構築するのに O(n) が必要です。

空間の複雑さ = 2 つの入力配列と出力である構築されたバイナリ ツリーを無視する定数

于 2012-07-02T18:58:28.617 に答える