原书出处
Introduction to Algorithms, Fourth Edition
19 第19章 不相交集合的数据结构
the O(m′ α(n)) running time of the original sequence of m′ operations. Potential function
The potential function we use assigns a potential ϕq(x) to each node x in the disjoint-set forest after q operations. For the potential Φq of the entire forest after q operations, sum the individual node potentials: . Because the forest is empty before the first operation, the sum is taken over an empty set, and so Φ0 = 0. No potential Φq is ever negative.
The value of ϕq(x) depends on whether x is a tree root after the qth operation. If it is,
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter019.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea