这个算法会在O(n)中运行吗？

Question

注意:这是Cracking the Coding Interview 5th Edition的问题4.3

问题:给定排序(递增顺序)数组,编写算法以创建具有最小高度的二叉搜索树

这是我的算法,用Java编写来解决这个问题

  public static IntTreeNode createBST(int[] array) {
         return createBST(array, 0, array.length-1);
   }
   private static IntTreeNode createBST(int[] array, int left, int right) {
        if(right >= left) {
            int middle = array[(left + right)/2;
            IntTreeNode root = new IntTreeNode(middle);
            root.left = createBST(array, left, middle - 1);
           root.right = createBST(array, middle + 1, right);
            return root;
         } else {
             return null;
         }
    }

我对作者的代码检查了这个代码,它几乎相同.
但是,我很难分析此算法的时间复杂度.
我知道这不会像二进制搜索一样在O(logn)中运行,因为你没有在每个递归级别做同样的工作量.EG在第一级,1个工作单元,第2级 - 2个工作单元,第3级 - 4个工作单元,一直记录₂(n)级 - n个工作单元.

因此,基于此,此算法所采用的步数将受此数学表达式的限制

看完无限几何系列之后,我评价了

或2n将在O(n)

你们同意我在这里的工作吗？这个算法会在O(n)中运行,还是我错过了一些东西,或者它实际上是在O(nlogn)或其他函数类中运行的？

Answer 1

有时,您可以通过计算结果中每个项目的时间量而不是求解递归关系来简化计算.这个技巧适用于此.首先将代码更改为明显等效的形式:

private static IntTreeNode createBST(int[] array, int left, int right) {
    int middle = array[(left + right)/2;
    IntTreeNode root = new IntTreeNode(middle);
    if (middle - 1 >= left) {
        root.left = createBST(array, left, middle - 1);
    }
    if (right >= middle + 1) {
        root.right = createBST(array, middle + 1, right);
    }
    return root;
}

现在每次调用都createBST直接创建1个节点.由于最终树中有n个节点,因此必须进行n全部调用,createBST并且由于每个调用直接执行一定量的工作,因此总体时间复杂度为O(n).