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

Question

注：这是Cracking the Coding Interview第5版的第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;
         }
    }

我对照作者的代码检查了这段代码，它几乎完全相同。
但是我很难分析这个算法的时间复杂度。
我知道这不会运行 in O(logn) 就像 Binary Search 因为你在每个递归级别上做的工作量不同。 E.G在第一层，1个工作单元，第2层- 2个工作单元，第3层- 4个工作单元，一直到log₂(n)层- n个单元工作的。

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

看完Infinite geometric series，我评价为

或 2n 将在 O(n)

你们同意我在这里的工作吗，这个算法会 运行 在 O(n) 或者我错过了什么或者它实际上 运行s 在 O(nlogn) 或其他函数 class?

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 个节点，因此必须对 createBST 进行 n 次总调用，并且由于每次调用直接执行恒定量的工作，因此总体时间复杂度为 O(n).

Answer 2

如果您对递归感到困惑，请将递归调用（当然是在心理上）替换为循环。例如，在上面的函数中，您可以想象递归调用在 "while loop" 中。因为，现在是一个while循环，直到遍历完n个节点，复杂度为O(n)。