递归分析（时间复杂度）

Question

im编写一个布尔函数，用于计算两个二叉树是否相同。让我们看一下程序：

boolean func(Node head1 , Node head2){
if(head1 == null || head2 == null) return head1 == null && head2 == null;
return func(head1.left , head2.left) && (head1.right,head2.right);
}

我知道在最坏的情况下程序会检查n个元素，因此它的O（n）。我想在T（n）中描述此递归函数。我不知道要开始，因为我不知道停止点的价值是什么，我认为函数是T（n，m）= 2 * t（n-1，m-1）+ n + m。

Answer 1

让n为二叉树中的节点数。如果二叉树的节点数不同，则n小于两种大小（因为一旦到达一棵树的末端，您将停止比较）。

在每次调用时，您都在树的节点之间进行一些比较。这将是恒定时间，因此您可以将这段时间称为d，它表示某个任意常数。

最后，您正在为当前节点的2个子节点进行2次递归调用。请注意，在最坏的情况下，每个子节点都是子树的根，该子树占树中节点总数的一半。换句话说，如果您有一棵具有n个节点的树，并且正在查看根节点，那么根的每个子节点都在其下（包括它）有大约n / 2个节点。

所以您的复发情况如下：

T(n) = 2*T((n-1)/2) + d

您可以简化为：

T(n) = 2*T(n/2) + d