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有点困难。但是我们可以使用这种模式将 ... 拆分为本地成本和递归成本：

每次调用constructTree我们都有T findInNode = Ο( nconstructTree ) 的本地成本和两个使用n -1 而不是n的递归调用。所以

T‍ <sub>constructTree( n ) = TfindInNode ( n ) +2· TconstructTree ( n -1))

由于constructTree每次调用 的递归调用次数都会翻倍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次调用，第二步后为n +2· n +4· n，以此类推. 由于此递归调用树的总深度为n（每次递归n减 1），总调用次数constructTree为：

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

因此：

T‍ <sub>constructTree( n ) = (2 n+1 -1)· n ∈ Ο(2 n )。

所以你的算法具有指数时间复杂度。

空间复杂度也是 Ο(2 n )，因为每次递归调用的局部空间成本为 1 constructTree。

于 2012-07-02T20:54:02.280 回答
0

时间复杂度 = O(n^2)。2 次递归调用需要 O(n) 来构造二叉树，每个节点构造需要 O(n) 进行顺序搜索，即 O(n^2)。

空间复杂度 = 常数，忽略 2 个输入数组和作为输出的构建二叉树

于 2012-07-02T18:58:28.617 回答