数据结构中的静态手指定理

静态手指定理 − 让 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 次浏览

开启你的 职业生涯

完成本课程以获得认证

开始