势能分析

发表于 2020-02-29 分类于 Others 阅读次数： 37 本文字数： 761 阅读时长 ≈ 1 分钟

next hexonext butterfly volantis yearn yilia shoka indigo apollo landscape cactus matery icarus fluid material

势能分析简介

势能分析是一种常用的数据结构时间复杂度分析的手段，我们常常会定义一个势能函数，用于评价数据结构某个状态的势能，把每个操作的时间复杂度加上操作导致的势能变化作为摊还复杂度，如果经过了一系列操作以后，势能不减少，这一系列操作的时间复杂度之和不大于这一系列操作的摊还复杂度之和。

势能分析更加严谨的简介

我们对一个初始数据结构 $D_{0}$ 执行 $n$ 个操作，对于每个 $i = 1, 2, . . ., n$ 令 $C_{i}$ 为第 $i$ 个操作的实际代价,令 $D_{i}$ 为在数据结构 $D_{i - 1}$ 上执行第 $i$ 个操作后得到的结果数据结构，势能函数 $Φ$ 将每个数据结构 $D_{i}$ 映射到一个实数 $Φ (D_{i})$ ,此值即为关联到数据结构 $D_{i}$ 的势，第 $i$ 个操作的摊还代价 $\hat{C_{i}} = C_{i} + Φ (D_{i}) - Φ (D_{i - 1})$ ,则 $n$ 个操作的总摊还代价为 $\sum_{i = 1}^{n} \hat{C_{i}} = \sum_{i = 1}^{n} C_{i} + Φ (D_{n}) - Φ (D_{0})$ ，如果势能函数满足 $Φ (D_{n}) \geq Φ (D_{0})$ ，则总摊还代价 $\sum_{i = 1}^{n} \hat{C_{i}}$ 是总实际代价 $\sum_{i = 1}^{n} C_{i}$ 的一个上界

后记

笔者在此不会做势能分析，能进行势能分析的东西太多了，例如splay、pairing heap、fibonacci heap、link cut tree等等,我们将其留在后边的博文中详细介绍。