Merkle树空间复杂度

Question

当使用梅克尔树进行搜索时，时间复杂度是\mathcal O(\log n)，但我不明白空间复杂度如何是\mathcal O(n)。在我看来，也应该是\mathcal O(\log n)。有人能给我解释一下吗？

Answer 1

为了简单起见，假设Merkle树是一个完全二叉树。让数据块的数量是n，它被链接到叶节点。因此，树节点的总数是|nodes| = n + n/2+ \cdots +1。如果我们假定n =2^k比|nodes| = 1 + 2 + 2^2 + \cdots + 2^k = \frac{2^k-1}{2-1} = 2^k-1 = n-1.简单，那么我们就有n+ n -1 节点，也就是与数据块一起的节点。因此，节点数是\mathcal{O}(n)。

在另一种方法中，可以将树的高度考虑为搜索复杂性，h = c \log n，那么使用h的二叉树的最大数目是2^h-1 = 2^{c \log n}-1 = n 2^c-1 \in \mathcal{O}(n)。添加数据块不会改变复杂性。

注意:在一个完整的二叉树中，如果我们说根是1级，那么i-th级别包含2^{i-1}节点。每个级别将包含前一级的两倍。