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

不知怎的，我设法写了一个算法，从它的无序和有序遍历数据构造一个二叉树。
我不知道如何计算该算法的时间和空间复杂度。
我猜是

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

}

最佳答案

为了估计运行时复杂性，让我们从简单的开始，findInNode：
tfindinnode=0（n）
由于我们有递归调用，估计constructTree稍微困难一些但我们可以使用这种模式将…分为本地成本和递归成本：
对于constructTree的每个调用，我们都有tfindinnode=0（n）的本地开销，以及两个用n-1而不是n的constructTree递归调用。
T‍构造树（n）=TfindInNode（n）+2·T构造树（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的初始调用之后的调用总数是n，递归调用的第一步之后是n+2·n，第二步之后是n+2·n+4·n，依此类推。由于这个递归调用树的总深度是n（每个递归n递减1），因此constructTree的总调用数总计为：
20+21+22+…+2n=2n+1-1
因此：
t构造树（n）=（2n+1-1）·n∈0（2n）。
因此，你的算法具有指数时间复杂度。
空间复杂度也为0（2N），因为每个递归调用的本地空间成本为1。