有人可以确定我制作的 LeetCode 解决方案的时间复杂度吗？

Question

我为下面链接的问题编写了一个解决方案，但我不确定其时间复杂度。我以为它是二次的，但当我提交时它在 0 毫秒内通过，所以它可能是线性的 idk。如果有更多经验的人解释我，我会很高兴。

https://leetcode.com/problems/balanced-binary-tree/description/

这是我的解决方案（用 C 编写）：

#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
 };

int maxDepth(struct TreeNode* root) {
    if (!root)
    {
        return 0;
    }
    
    int leftHeight = 1 + maxDepth(root->left);
    int rightHeight = 1 + maxDepth(root->right);

    if (leftHeight > rightHeight)
        return leftHeight;
    else
        return rightHeight;
}

bool isBalanced(struct TreeNode* root) {
    
    if (!root)
    {
        return true;
    }

    int leftHeight = maxDepth(root->left);
    int rightHeight = maxDepth(root->right);

    int diff = leftHeight - rightHeight;

    if (diff == 0 || diff == 1 || diff == -1){
        return isBalanced(root->left) && isBalanced(root->right);
    }

    return false; 
}

单独分析这些函数，我知道计算树的最大深度需要线性时间，并且由于我为树的每个节点调用它，所以我认为它是线性的。然而，它在提交时获得了相当好的运行时间，所以我想知道这是怎么发生的。

Answer 1

我知道计算树的最大深度需要线性时间

正确

因为我为树的每个节点调用它，所以我认为它是线性的

该组合不是线性的。是 O(𝑛log𝑛):

在根处执行一次

isBalanced

（没有递归调用

isBalanced

）所访问的节点数为𝑛（对根的

isBalanced

访问算一，然后递归访问的完整子树）

maxDepth

拨打电话）。递归

isBalanced

调用（仅，没有进一步递归）访问的节点数为 𝑛−1（除根之外的所有节点）。在下一个递归级别，这是 𝑛−3（除了前两级之外的所有级别），等等。继续最坏的情况（其中树完全平衡，𝑛 小于 2 的整数次方），我们得到：

      𝑛 + 𝑛−1 + 𝑛−3 + 𝑛−7 + ... + (𝑛+1)/2，log₂(𝑛+1) 项的总和，或

      𝑛−(2⁰−1) + 𝑛−(2^−1) + 𝑛−(2²−1) + 𝑛−(2³−1) + ... + (𝑛+1)/2，log _的总和2(𝑛+1) 项

2 的幂相减形成几何级数 (2⁰ + 21 + 22 + 23 + ... + 2^{log(𝑛+1)−1})，加起来为 𝑛，所以我们得到：

      𝑛log(𝑛+1) − 𝑛 + log(𝑛+1) = (𝑛+1)log(𝑛+1) − 𝑛

...这是 O(𝑛log𝑛)。

对于实际输入，时间复杂度并不是影响实际运行时间的唯一因素。正如您所注意到的，即使时间复杂度可能不是最优的，实现仍然可以足够快地执行具体输入的任务。

您可以通过自下而上的方法达到线性时间复杂度，在该方法中，您可以将为子树计算的深度冒泡，这样就不需要为每个节点计算多次。