Complexity
默克爾樹空間複雜度
使用 Merkle 樹進行搜尋時，時間複雜度為 $ \mathcal O(\log n) $ 但我不明白空間複雜度如何 $ \mathcal O(n) $ . 在我看來，它也應該是 $ \mathcal O(\log n) $ . 有人可以向我解釋嗎？
為簡單起見，假設 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} $ 節點。每個級別將包含前一個級別的兩倍。