利特代码:平衡二叉树 .我的程序是O(n^2)吗?它的运行速度比 O(n) 快

Question

这是问题：https：//oj.leetcode.com/problems/balanced-binary-tree/首先我写出我认为是 O（n^2） 的解决方案，如下所示：

class Solution {
public:
    int calc(TreeNode *p){
        if (p==NULL) return 0;
        int a=calc(p->left);
        int b=calc(p->right);
        if (a>b) return a+1; else return b+1;
    }
    bool isBalanced(TreeNode *root) {
        if (root==NULL) return true;
        return (isBalanced(root->left) && isBalanced(root->right) && abs(calc(root->left)-calc(root->right))<=1);
    }
};

然后我写一个 O（n） 解决方案：类解决方案 {

public:
    int check(TreeNode *p){
        if (p==NULL) return 0;
        int l=check(p->left);
        int r=check(p->right);
        if( l==-99 || r==-99 || abs(l-r)>1) return -99;
        return max(l,r)+1;
    }
    bool isBalanced(TreeNode *root) {
        if (root==NULL) return true;
        return check(root)!=-99;
    }
};

两人都被录取了。第一个运行时间：56ms，第二个是100ms有时是400+ms。为什么 O（n^2） 比 O（n） 快？

Answer 1

Big-O 表示法不会告诉您 N 特定值的运行时间，它只告诉您运行时间将如何随着 N 的增加而增长。

对于特定的 N，O（n） 优于 O（n^2） 并非不自然。

考虑一下，一段总是需要 10 分钟才能完成的代码是 O（1）。