比较两棵 Merkle 树的时间复杂度是多少？

Question

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

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 树比普通哈希表做得更好，因为它能够更快地修剪树。但是，我无法用大 O 术语来表示。

一个类似的哈希表实现是遍历 rowid 并在第二个哈希表上进行恒定时间查找。找到 rowid 的值后，如果叶级数据存储为哈希表，您可能会对每个叶进行线性比较。

Answer 1

这是 output-sensitive algorithm 的一个很好的例子，其最坏情况运行时间通过引入新数量来最准确地指定。对于这个问题，如果 h 是树的高度，d 是叶子差异的数量，那么最坏的情况是 O(d + d (h − log d))。在树的第 ℓ 层，我们最多可以有 min(2^ℓ, d) 个有差异的节点，我们可以向它们的父节点收取匹配节点的成本，所以我们只需要绑定这笔款项。交叉点是 ℓ = log d，所以 ∑_{ℓ=0...log d} 2^ℓ 是 2^{log d + 1} − 1 = Θ(d)。然后有 h − log d 水平剩余 d 差异。

比较两棵 Merkle 树的时间复杂度是多少？

What is the time complexity of comparing two Merkle trees?

algorithm

hashmap

data-structures

merkle-tree