資料結構中的靜態手指定理

靜態手指定理 − 讓 f 被視為一個稱為手指的特定元素。

那麼下面的表示式是展平一個序列的代價的一個界。

O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j

注意 − |f-i| 表示手指和項 i 之間對稱排序的距離。

其中 m 表示最多有 n 個節點的樹上的更新或訪問操作的數量。

注意，至少在攤還意義上，對於一個永遠不超過 n 個節點的樹上的前 m 個操作所花費的時間與平衡二叉搜尋樹（如 AVL 樹、2-3 樹等）所花費的時間相同。

阿納布·查克拉博蒂

更新於: 13-7-2020

145 次瀏覽

開啟你的 職業生涯

完成本課程以獲得認證

開始