algorithm - 需要找到我的算法的时间和空间复杂度

Question

不知何故，我设法编写了一种算法，用于从中序和前序遍历数据构建二叉树。

我不确定如何计算该算法的时间和空间复杂度。

我的猜测是

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;
    }

}

Answer 1

为了估计运行时的复杂度，让我们从简单的开始，findInNode:

T_findInNode = Ο(n)

估计 constructTree 有点困难，因为我们有递归调用。但是我们可以使用这种模式将……分解为局部成本和递归成本:

对于 constructTree 的每次调用，我们的本地成本为 T_findInNode = Ο(n) 和两个使用 n-1 而不是 n 递归调用 constructTree。所以

T‍_{constructTree}(n) = T_findInNode(n) + 2 · T_{constructTree}(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·< em>n 等等。由于此递归调用树的总深度为 n(每次递归 n 递减 1)，constructTree 的总调用次数> 总结为:

2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹-1

因此:

T‍_{constructTree}(n) = (2ⁿ⁺¹-1)·n ∈ Ο(2ⁿ).

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

空间复杂度也是 Ω(2ⁿ)，因为每次递归调用 constructTree 的本地空间成本为 1。