时间复杂度（递归）【前序遍历的BST构造】
Time complexity (Recurrence) [BST construction from preorder traversal]
我正在执行从给定的前序遍历构造 BST 的程序。我想到了一个递归逻辑，这是解决这个问题的幼稚方法。
对于预序，根将始终是遍历中的第一个节点。并且值开始大于根的点表示右子树，类似地小于根的值表示它们存在于左子树中。
由于两个子树中的节点不一定都是总节点的一半，因此递推关系变得有点像这样：
T(n) = T(k) + T(n-k) + c [每次递归调用完成的持续工作]
假设 left/right 子树中有 k 个节点，另一个子树中有 n-k 个节点。
此 post 的方法 1 中表达了类似的方法：http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
该方法的时间复杂度为 O(n^2)，这让我很困惑，因为我无法解决上述递归关系，其中每个子树中的节点数可能会有所不同，或者可能制定的递归不正确。
我很感激任何关于这方面的指导，我在这里查找了主定理和其他类似问题以获得递归问题的时间复杂度，但仍然无法解决上述问题。谢谢
T(n) = T(k) + T(n-k) + c 描述了一个 O(n) 解决方案。而你的问题的最佳解决方案确实是O(n)。 posthttp://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/中描述的第二种算法是解决O(n)中这个问题的一个例子。
O(n^2) 复杂度是针对您包含的 post 中描述的第一个算法。在该算法中，每个节点都有一个 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)算法。
我正在执行从给定的前序遍历构造 BST 的程序。我想到了一个递归逻辑，这是解决这个问题的幼稚方法。 对于预序，根将始终是遍历中的第一个节点。并且值开始大于根的点表示右子树，类似地小于根的值表示它们存在于左子树中。 由于两个子树中的节点不一定都是总节点的一半，因此递推关系变得有点像这样：
T(n) = T(k) + T(n-k) + c [每次递归调用完成的持续工作] 假设 left/right 子树中有 k 个节点，另一个子树中有 n-k 个节点。
此 post 的方法 1 中表达了类似的方法：http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
该方法的时间复杂度为 O(n^2)，这让我很困惑，因为我无法解决上述递归关系，其中每个子树中的节点数可能会有所不同，或者可能制定的递归不正确。
我很感激任何关于这方面的指导，我在这里查找了主定理和其他类似问题以获得递归问题的时间复杂度，但仍然无法解决上述问题。谢谢
T(n) = T(k) + T(n-k) + c 描述了一个 O(n) 解决方案。而你的问题的最佳解决方案确实是O(n)。 posthttp://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/中描述的第二种算法是解决O(n)中这个问题的一个例子。
O(n^2) 复杂度是针对您包含的 post 中描述的第一个算法。在该算法中，每个节点都有一个 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)算法。