这种在二叉树中寻找最大有效 bst 的蛮力方法的时间复杂度是多少？

Question

    
int size(Node* root){
    if (root == nullptr) {
        return 0;
    }
    return size(root->left) + 1 + size(root->right);
}
bool isBST(Node* node, int min, int max)
{
    if (node == nullptr) {
        return true;
    }
    if (node->data < min || node->data > max) {
        return false;
    }
    return isBST(node->left, min, node->data) &&
        isBST(node->right, node->data, max);
}
int findLargestBST(Node* root)
{
    if (isBST(root, INT_MIN, INT_MAX)) {
        return size(root);
    }
 
    return max(findLargestBST(root->left), findLargestBST(root->right));
}

这是一个在二叉树中寻找最大bst的代码。所以根据 this post 暴力解决方案的最坏情况时间复杂度是 O(n^2) 但是如何呢？应该是 O(n^3) 否？因为我们也传递了大小函数

Answer 1

大小函数只用过一次，为O(n)。所以复杂度是O(n^2 + n) == O(n^2).

更新：让我重新表述一下，因为我的推理根本不清楚。

size 函数被多次调用。当每个子树调用 findLargestBST 时，要么是因为树是 BST，要么是因为每个子树在某处。 size 函数也被 size 本身递归调用。

但是每个节点最多调用一次size。所以累积起来就是O(n)。要看到这一点，您必须查看 findLargestBST.

中的两个案例

如果树是 BST，那么 size 会为整棵树调用并在内部递归到树的每个元素。

如果树不是 BST 则树被分裂并且可以为每个子树调用 size。但最多只查看左树中的每个元素和右树中的每个元素。对 size 的两次（或更多次）调用永远不会重叠并多次查看一个元素。

累计就是O(n).

这种在二叉树中寻找最大有效 bst 的蛮力方法的时间复杂度是多少？

What will be the time complexity of this brute force apporach of finding largest valid bst in a binary tree?

c++

time-complexity