我对2棵二叉树之间的复杂度比较有点困惑，如果相同，下面是相同的代码。
我对2棵二叉树之间的复杂度比较有点困惑，如果相同，下面是相同的代码。
提问于 2020-05-07 17:49:05
二叉树与下面的二叉树代码相同或不相同，给出了线性复杂度，即大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;
} (使用递归的Fibonacci级数给出了指数复杂度)以下代码的复杂度为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;
}
}我的问题是，两者看起来都是相似的，但一个是线性复杂性，另一个是指数。有谁能澄清这两种算法。
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-05-07 18:31:52
Fibonacci系列
如果为生成fibonacci系列的递归代码构建树，则如下所示：
fib(n)
fib(n-1) fib(n-2)
fib(n-2) fib(n-3) fib(n-3) fib(n-4)在哪一级你会遇到谎言(1)，这样树才能“停止”？
在( n-1 )第四层，您将遇到fib(1)，并在那里停止递归。节点的数量将按2^n的顺序排列，因为存在(n-1)级别。
二叉树比较
让我们考虑您的二叉树比较。
让我们假设两者都是完整的二叉树。根据您的算法，它将访问所有节点一次，如果'h‘是树的高度，那么节点的数量将是2^h的顺序。您可以将这种情况下的复杂性称为O(2^h)。
本例中的O(n)等价于O(2^h)
Stack Overflow用户
发布于 2020-05-07 21:34:22
这种差异起源于n的不同定义，而Fibonacci数的朴素递归算法也在图中执行一种遍历，而n的值不是由图中的节点数来定义，而是由输入数来定义。
但是二叉树比较，n定义为多个节点。
因此，在这两种算法中，n有着完全不同的含义，这就解释了为什么n的时间复杂度出现了如此不同的结果。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61664405
复制相关文章
相似问题
腾讯云开发者
