0

我试图编写一个程序来使用前序序列构造一个二叉搜索树。我知道有很多解决方案：最小/最大算法、经典（或“明显”递归）甚至迭代而不是递归。

我尝试实现经典递归：前序遍历的第一个元素是根。然后我搜索所有小于根的元素。所有这些元素都将成为左子树的一部分，而其他值将成为右子树的一部分。我重复这一点，直到我构建所有子树。这是一种非常经典的方法。

这是我的代码：

public static TreeNode constructInOrderTree(int[] inorder) { 
    return constructInOrderTree(inorder, 0, inorder.length-1);
}

 private static TreeNode constructInOrderTree(int[] inorder, int start, int end){
 if(start>end){
        return null;
 }

int rootValue = inorder[start];
TreeNode root = new TreeNode(rootValue);

int k = 0; 
for (int i =0; i< inorder.length; i++){
    if (inorder[i]<= rootValue){ 
        k=i;
    }
}

 root.left = constructInOrderTree(inorder, start+1, k);
 root.right= constructInOrderTree(inorder, k+1, end);

    return root;
   }

我的问题是：这个算法的时间复杂度是多少？是 O(n^2) 还是 O(n * log(n) ) ？

我在stackoverflow中搜索了这里，但我发现了许多相互矛盾的答案。有时，有人说它是 O(n^2)，有时是 O(n*log(n))，我真的很困惑。

我们可以在这里应用主定理吗？如果是，“也许”我们可以考虑每次我们将树分成两个子树（相等部分），所以我们会有关系：（O（n）是在数组中搜索的复杂度）

T(n) = 1/2 * T(n/2) + O(n)

这会给我们带来O(n*log(n)). 但是，我认为这不是真的，我们不会将树分成相等的部分，因为我们在数组中搜索直到找到足够的元素，不是吗？

是否可以在这里应用主定理？

4

1 回答 1

1

远见：

不，它既不是O(n^2)，也不O(nlogn)是 WC。由于树的性质以及您不对每个元素执行任何复杂操作的事实。您所做的只是输出它，而不是使用一些比较算法对其进行排序。

那么 WC 将是O(n).

那是当树倾斜时，即根的子树之一是空的。然后你就有了一个简单的链表。然后要输出它，您必须至少访问每个元素一次给O(n).

证明：

让我们假设右子树是空的，并且每次调用的努力是恒定的（仅打印出来）。然后

T(n) = T(n-1) + T(0) + c
T(n) = T(n-2) + 2T(0) + 2c
.
.
T(n) = nT(0) + nc = n(T(0) + c)

因为T(0)和c是常数，所以你最终在O(n).

于 2016-05-11T22:50:24.873 回答