Какова будет временная сложность этого метода грубой силы для поиска наибольшего действительного bst в двоичном дереве?
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 в двоичном дереве. Итак, согласно сообщению это, временная сложность решения грубой силы в худшем случае составляет O (n ^ 2), но как? Должно быть O(n^3) нет? так как мы также передаем функцию размера
давайте просто скажем, что значения меньше, чем всегда: p
как насчет деревьев с повторяющимися значениями?
да, я забыл поставить здесь <= и >=, но на другом портале (gfg) я использовал его, я думаю, что для этого конкретного кода они предполагают, что он не имеет повторяющихся элементов
Ответы 1
Функция размера используется только один раз и обозначается O(n). Итак, сложность O(n^2 + n) == O(n^2).
Обновление: позвольте мне перефразировать это, поскольку мои рассуждения совсем не ясны.
Функция size вызывается много раз. Либо потому, что дерево является BST, либо где-то там для каждого поддерева, когда findLargestBST вызывается с каждым поддеревом. Функция size также рекурсивно вызывается самим size.
Но для каждого узла size вызывается не более одного раза. Так накопилось O(n). Чтобы увидеть это, вы должны посмотреть на два случая в findLargestBST.
Если дерево BST, то size вызывается для всего дерева и внутренне рекурсивно обращается к каждому элементу дерева.
Если дерево не BST, то дерево разбивается, и для каждого поддерева можно вызвать size. Но самое большее, что смотрит на каждый элемент в левом дереве и каждый элемент в правом дереве. Два (или более) вызова size никогда не могут перекрываться и просматривать элемент более одного раза.
Накоплено то есть O(n).
если есть несколько bst, то size func будет вызываться несколько раз, верно?
Извините, вы правы, это вызывается для каждого поддерева.
так сбивает с толку, почему они поставили его на O (n ^ 2)
This is a code to find largest bst in a binary tree.Нет, это не так. Любой BST, который содержитINT_MINилиINT_MAX, не будет найден.