我对2个二叉树之间的复杂度比较有些困惑，如果相同，下面是相同的代码

Question

与下面的另一个二叉树代码相同或不同的二叉树给出了线性复杂度，即大O（n），其中n是二叉树的节点数最少的节点数。

 boolean identical(Node a, Node b)  
{ 
    if (a == null && b == null) 
        return true; 

    if (a != null && b != null)  
        return (a.data == b.data 
                && identical(a.left, b.left) 
                && identical(a.right, b.right)); 

    /* 3. one empty, one not -> false */
    return false; 
} 

（使用递归的斐波那契数列给出指数复杂度）以下代码的复杂度为2 ^ n。

class Fibonacci  { 
    static int fib(int n) 
    { 
       if (n <= 1) 
         return n; 
       return fib(n-1) + fib(n-2); 
    } 
    public static void main (String args[]) 
    { 
       int n = 9; 
     }  
}

我的问题看起来都相似，但是一个具有线性复杂度，另一个具有指数级。谁能澄清两种算法。

Answer 1

斐波那契系列

如果为递归代码构建树以生成斐波那契数列，它将类似于：

              fib(n)

      fib(n-1)      fib(n-2)

  fib(n-2) fib(n-3)   fib(n-3)  fib(n-4)

您将在哪个级别遇到fib（1）以便树可以“停止”？

第( n-1 )级，您将遇到fib(1)，然后递归停止。因为有2^n个级别，所以节点数约为(n-1)。

二叉树比较

让我们考虑一下您的二叉树比较。

假设两者都是完整的二叉树。根据您的算法，如果“ h”是高度，它将访问所有节点一次树的节点数将是2^h的顺序。在这种情况下，您可以说复杂度为O(2^h)。

在这种情况下，O(n)等效于O(2^h)

Answer 2

差异源自n的不同定义。尽管针对Fibonacci数的朴素递归算法也执行图中的一种遍历，但n的值不是由该图中的节点数来定义，而是由输入数来定义。

然而，二叉树比较将n定义为许多节点。

所以n在这两种算法中具有完全不同的含义，并且它解释了为什么以n表示的时间复杂度如此不同。

Answer 3

I think above solution is more acceptable, If we take n = 4 then total number of calls(instructions) will be 16. 

fib(4)  = [[fib(1)+fib(0)]+[fib(1)]   +   [fib(1)]]   +   [fib(1)+fib(0)]+[fib(1)]
fib(3) =  [[fib(1)+fib(0)]+[fib(1)]]   +  [fib(1)]
fib(2) =  [fib(1)+fib(0)]+[fib(1)]
fib(1) =  [1]
fib(0) =  [0]
These many individual and sub calls would be there. Please correct me if i am wrong?