时间戳

首页 > 解决方案 > 我对2个二叉树之间的复杂性比较有点困惑，如果相同，下面是相同的代码

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

问题描述

二叉树与下面的另一个二叉树代码相同或不同给出线性复杂度，即大 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; 
     }  
}

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

标签： algorithmdata-structuresbinary-treebinary-searchalgorithmic-trading

解决方案

斐波那契数列

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

              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)

推荐阅读