algorithm - 时间复杂度(递归)【前序遍历的BST构造】

Question

我正在执行从给定的前序遍历构建 BST 的程序。我想到了一个递归逻辑，这是解决这个问题的幼稚方法。 对于预序，根将始终是遍历中的第一个节点。并且值开始大于根的点表示右子树，类似地小于根的值表示它们存在于左子树中。 由于两个子树中的节点不一定都是总节点的一半，因此递推关系变得有点像这样:

T(n) = T(k) + T(n-k) + c [每次递归调用的持续工作] 假设左/右子树中有 k 个节点，另一个子树中有 n-k 个节点。

这篇文章的方法 1 中表达了类似的方法:http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

该方法的时间复杂度为 O(n^2)，这让我感到困惑，因为我无法解决上述递归关系，其中每个子树中的节点数可能会有所不同，或者递归公式不正确。

我很感激任何关于这方面的指导，我在这里查找了主定理和其他类似问题以获得递归问题的时间复杂度，但仍然无法解决上述问题。谢谢。

Answer 1

T(n) = T(k) + T(n-k) + c 描述了一个O(n) 解决方案。而您的问题的最佳解决方案确实是 O(n)。帖子中描述的第二种算法 http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/是在 O(n) 中解决此问题的示例。

O(n^2) 复杂度是针对您包含的帖子中描述的第一个算法。在该算法中，每个节点都有一个 O(n) 步骤来确定左右子树之间的分区: 注意以下几行:

...
for ( i = low; i <= high; ++i )
    if ( pre[ i ] > root->data )
       break;
...

所以在这个版本中，算法应该被描述为T(n) = T(k) + T(n-k) + c + n，它描述了一个O(n^ 2)算法。