我对 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) 以便树可以 "stop"？

在第 ( n-1 ) 级你会遇到 fib(1) 并且递归停止。节点数将是 2^n 的数量级，因为有 (n-1) 个级别。

二叉树比较

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

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

本例中的O(n)相当于O(2^h)

Answer 2

差异源于n的不同定义。虽然斐波那契数的朴素递归算法也在图中执行一种遍历，但 n 的值不是由该图中的节点数定义的，而是由输入数定义的。

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

所以n在这两个算法中的意义完全不同，也就解释了为什么n的时间复杂度出来了如此不同。

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

I am bit confused on Complexity comparison between 2 binary tree, if identical, below is the code for the same

algorithm

binary-tree

binary-search

algorithmic-trading

data-structures