会在O（n）的算法运行？ [英] Would this algorithm run in O(n)?

问题描述

注意：这是破解编码采访第五版问题4.3

Note: This is problem 4.3 from Cracking the Coding Interview 5th Edition

问题：给定一个排序（升序排列）阵列，写一个算法来创建具有最小高度二叉搜索树

Problem:Given a sorted(increasing order) array, write an algorithm to create a binary search tree with minimal height

下面是我的算法，用Java编写的做到这一点的问题

Here is my algorithm, written in Java to do this problem

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

我查了一下这个code对提交的，它的几乎相同。
但是我有一个很难与分析算法。我知道这不会运行 O（LOGN）的如二进制搜索因为你'重新不是完成工作的相同量的递归的每个层次。 EG在第一级，1个单位的工作，第二级 - 2个单位的工作，3 - 4个单位的工作，所有的登录 ₂ （N）级别的方式 - N的工作单位。

I checked this code against the author's and it's nearly identical.
However I am having a hard time with analyzing the time complexity of this algorithm.
I know this wouldn't run in O(logn) like Binary Search because you're not doing the same amount of work at each level of recursion. E.G at the first level, 1 unit of work, 2nd level - 2 units of work, 3rd level - 4 units of work, all the way to log₂(n) level - n units of work.

因此​​，基于这关，采取的步骤，这个算法数量将通过这个数学EX pression被上界

So based off that, the number of steps this algorithms takes would be upper bounded by this mathematical expression

这看后<一href="https://www.khanacademy.org/math/$p$pcalculus/seq_induction/infinite-geometric-series/v/deriving-geometric-series-sum-formula">Infinite几何级数，我评估，以

which after watching Infinite geometric series, I evaluated to

或2N这将是的 O（N）的

难道你们对我的工作认同这里，该算法将运行在的 O（N）的或我错过了什么，或者它实际运行中的 O（nlogn）的或者一些其他的功能类？

Do you guys agree with my work here and that this algorithm would run in O(n) or did I miss something or it actually runs in O(nlogn) or some other function class?

推荐答案

有时候，你可以通过计算每个项目的时间量的结果，而不是解决递推关系简化计算。这招适用于这里。首先改变code这显然等价形式：

Sometimes you can simplify calculations by calculating the amount of time per item in the result rather than solving recurrence relations. That trick applies here. Start by changing the code to this obviously equivalent form:

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

Now every call to createBST directly creates 1 node. Since there's n nodes in the final tree, there must be n total calls to createBST and since each call directly performs a constant amount of work, the overall time complexity is O(n).

这篇关于会在O（n）的算法运行？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！