这个算法是否能够以O(n)的时间复杂度运行？

Question

这个算法是否能够以O(n)的时间复杂度运行？

algorithmbig-otime-complexitycomplexity-theoryasymptotic-complexity

7

注意：这是《破解程序员面试》第五版中的问题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)内运行，因为在每个递归级别上你没有做同样数量的工作。例如，在第一级别上，1个单位的工作，第二级别-2个单位的工作，第三级别-4个单位的工作，一直到log₂(n)级别-n个单位的工作。

因此，基于此，该算法所需的步骤数将受到以下数学表达式的上限约束：

enter image description here

在观看了无限几何级数之后，我得出的评估结果是 enter image description here

或2n，这将处于O(n)中。

你们是否同意我的结论，即该算法将以O(n)的速度运行，还是我漏掉了什么，它实际上以O(nlogn)或其他函数类运行？

- committedandroider

是的，它是O(n)。如果我对构成复杂性证明的好方法有更清晰的想法，我会将其作为答案。 - Beta

@Beta 你是如何在没有证据的情况下得出结论的？ - committedandroider

1

我看到这个算法调用自身两次，每次在n/2个元素上进行，额外工作量为O(1)，并且移除一个元素。我不认为这是一个严谨的证明（比如“设f(n)和g(n)是函数...”），但足以让我在脑海中看到它，就像一条被切成碎片并展开的绳子，没有重叠。 - Beta

@Beta 为了确保一下，这里的空间复杂度是 O(log n) 吗？因为最深递归调用的高度是 log n。 - committedandroider

据我理解，“空间复杂度”一词指的是存储空间而不是堆栈深度。调用堆栈的最大深度为log(n)，但空间复杂度为O(n)，因为这是结果树的大小（而O(log(n))的开销加上了它，而不是乘以它）。 - Beta

2个回答

1

如果您在递归中感到困惑，可以将递归调用（当然是在脑海中）替换为循环。例如，在上面的函数中，您可以将递归调用想象成在“while循环”中。由于现在是一个while循环，执行时间直到遍历所有n个节点，复杂度为O(n)。

- Tejash Desai

但是这种方法在快速排序中不起作用。虽然您访问了所有元素，但运行时间仍为O(n log n)，而不是O(n)。您如何重新构思这种情况下的方法？我喜欢您使用while循环的方式。 - committedandroider

是的，我承认很难想象像快速排序这样增长对数的算法中使用循环。然而，这个想法对于所有指数增长函数如O(n^2)，O(n^3)等都非常适用。我们只需要使用嵌套循环即可。 - Tejash Desai

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

有时候，为了简化计算，可以通过计算结果中每个项目所需的时间来代替求解递归关系式。这个技巧同样适用于这里。首先将代码更改为以下明显等价的形式：

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)。