比较两个Merkle树的时间复杂度是多少?

Question

我有一个简单的递归函数，它比较两个默克尔树并累积叶节点中的差异。但是，我无法测量它的时间复杂度。具体来说，我想看看它与比较两个哈希表或两个bst相比是如何比较的。在这种情况下，一组叶子是一行，它们共享一行。一组行构成了整个默克尔树。在下面的代码中，我只是在叶子级别累积差异。

def diff_helper(node1: MNode, node2: MNode, diff: List[Difference]):
if not node1 and not node2:
return
elif node1.rowid==node2.rowid and node1.signature==node2.signature and node1.nodetype==NodeType.Row and node2.nodetype==NodeType.Row:
return
elif node1.rowid==node2.rowid and node1.signature!=node2.signature and node1.nodetype==NodeType.Row and node2.nodetype==NodeType.Row:
diff_helper(node1.left, node2.left, diff)
diff_helper(node1.right, node2.right, diff)
elif node1.rowid==node2.rowid and node1.signature!=node2.signature and node1.nodetype==NodeType.Leaf and node2.nodetype==NodeType.Leaf:
diff.append(Difference(node1.rowid, node1.column, node1.value, node2.value))
else:
diff_helper(node1.left, node2.left, diff)
diff_helper(node1.right, node2.right, diff)

时间复杂度:

在最好的情况下，我看到这是一个常量操作，因为两个树的根哈希值是相同的。在最坏的情况下，比较次数是所有叶节点的总数。

问题:

我可以感觉到merkle树比普通哈希表做得更好，因为能够更快地修剪树。但是，我无法用大0来表示。

一个可比较的哈希表实现是遍历数组并对第二个哈希表进行常量时间查找。找到row的值后，如果叶子级数据存储为散列表，则可能会对每个叶子进行线性比较。

Answer 1

这是输出敏感算法的一个很好的例子，它的最坏情况运行时间通过引入一个新量来最准确地指定。对于这个问题，如果h是树的高度，d是叶子的个数，那么最坏的情况是O(d + d (h - log d))。在树的第r层，我们可以有最小(2^{， r}， d)个有差异的节点，我们可以将节点与它们的父节点相匹配的代价，所以我们只需要约束这个和。日志交叉点ℓ= d,所以∑<子>ℓ= 0…日志d2<一口>ℓ2<一口>日志d + 1>