c++ - 如何找到该算法的运行时间以查找二叉树是否平衡？

Question

这是算法

int getHeight(node *root)
{
    if(!root) return 0;
    return max (getHeight(root->left), getHeight(root->right)) + 1;
}

bool isBalanced(node *root)
{
    if(!root) return true;
    int balanceFactor = abs( getHeight (root->left) - getHeight(root->right) );  //O(logn)
    if(balanceFactor > 1) return false;
    return isBalanced(x->left) && isBalanced(x->right); //T(n) = 2T(n/2)
}

我的理解:

//n is the number of nodes in the tree

T(n) = 2T(n/2) + O(logn) 正如我在评论中提到的。但是，我无法解决这种复发。主定理对此不起作用。

此算法的预期运行时间为 O(N-squared)。怎么会这样？我搞错了循环，这是肯定的。

Answer 1

我不确定你的递归关系，但我的简单理解如下:

您的 getHeight() 函数的复杂度为 O(N)，因为该函数会针对以根为根的子树中的每个节点调用一次。

通过类似的推理，在最坏的情况下，您的 isBalanced() 函数也会为每个节点调用(N 次)。此外，在每次调用时，您计算 getHeight() 函数两次。

Hence the complexity of isBalanced() function = O( N * (2 * N) ) = O(N^2)