算法导论笔记0x15 —— 均摊分析 & 斐波那契堆

势能法 Potential Method

均摊分析 Amortized Analysis

假设我们把每个操作的最大耗时记为f(n)n个操作以后则得到时间上界f(n)⋅n然而这个界限是不 tight 的,因为一些操作会比其他操作耗时更多。

均摊分析关注于每个操作消耗的平均时间。

Basic Knowledge

  • 势能函数, Potential Function Φ : D → ℝ
  • D is the set of states of the data structure.
  • Di is state after i’th operation.
  • ci is the cost of i’th operation.
  • The amortized cost for i’th operation is $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})$
  • $\sum_i \hat{c_i}\geq \sum_i c_i$
  • When we overcharge, i.e. $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1}) > c_i$, Φ increases
    • We “store” $\hat{c_i}-c_i$, which is called “credit” or “potential”
  • When we undercharge, i.e. $\hat{c_i} < c_i$, Φ decreases
    • We use stored credit to pay for $c_i – \hat{c_i}$
  • Lemma Suppose Φ(Dn)≥Φ(D0). Then $\sum_{i=1}^n \hat{c_i}\geq \sum_{i=1}^n c_i$.
    • To design Φ so that Φ(D0)=0 and Φ(Di)≥0 for all i.

Binary Counter

  • Consider a k-digit binary counter. When we increment the counter, we flip some bits.
    • 每次比特翻转消耗1个单位。
  • Φ(Di)=bi, where bi is the number of 1’s in Di.
  • Suppose i’th operation sets ti bits from 1 to 0.
    • Actual cost is ci = ti + 1
    • Set ti bits from 1 to 0, and one bit from 0 to 1 for the carry(进位?)
  • If bi = 0, the i’th operation reset all the bits.
    • All bits were set in Di − 1
    • ti = bi − 1 = k
  • If bi > 0, then bi = bi − 1 − ti + 1.
  • In both cases, bi ≤ bi − 1 − ti + 1
    • Then Φ(Di)−Φ(Di − 1)=bi − bi − 1 ≤ 1 − ti
  • $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})\leq (t_i + 1) + (1-t_i) = 2$
  • Φ(D0)=0, Φ(Dn)≥0
  • $\sum_{i=1}^n c_i \leq \sum_{i=1}^n \hat{c_i} \leq 2n$

斐波那契堆

  • Both Dijkstra’s and Prim’s algorithms take O((V + E)logV) time with a binary heap, and O(E + VlogV) time with a Fibonacci heap.
    • Both algorithms decrease the key value heap items O(E) times.
    • This takes O(ElogV) time on a binary heap, and O(E) time on a Fibonacci heap.
  • 斐波那契堆比二叉堆复杂得多,在实际情况下通常不会表现得更好。
  • 由多棵树的根节点连接而成
  • 每棵树满足最小堆的性质 —— 即每个节点的值小于子孙节点
  • 每个根节点被双向链表连接
    • 每棵树的每个节点的子孙节点用双向链表连接
  • 根节点中最小值的节点被 H.min 指向。
  • 节点数存储在 H.n 中。
  • 黑色的节点是被标记的marked.
    • Marks are only used during decrease key and deletion operations.
  • Suppose H has t(H) root nodes and m(H) marked nodes.
    • The potential of H is Φ(H)=t(H)+2m(H)

Basic Operations

  • Let H and H’ denote the heap before and after an operation.
  • Make-Heap
    • Make an empty heap. Set H’.n=0, H’.min=NIL.
    • Cost = O(1).
    • Amortized cost = O(1), since Φ(H)=Φ(H′) = 0
  • Insert a node
    • Add the new node to the root list, left of the min node.
    • Change H.min if new node’s key is smaller.
    • Cost = O(1).
    • Amortized cost = O(1).
      • Number of roots increases by 1
      • Φ(H′) − Φ(H)=(t(H)+4 + 2m(H)) − (t(H)+2m(H)) = O(1)

  • Find the minimum
    • Return H.min.
    • Cost = amortized cost = O(1).
  • Union of two heaps
    • Concatenate the root lists of the two heaps H1 and H2.
    • Set H.min to min(H1.min, H2.min)
    • Cost = O(1)
    • Φ(H′) − (Φ(H1)+Φ(H2)) = t(H′) + 2m(H′) − (t(H1)+2m(H1)+t(H1)+2m(H1)) = 0
    • Amortized cost = O(1)

Extract Min Node

  • 移去 H.min 指向的节点
  • 将每个 H.min 的子节点连带他们的子树移到根节点中
  • The degree of a node is its number of children.
  • We merge some of the trees in the root list, so that none of the roots have the same degree.
    • The merging function is called CONSOLIDATE.
    • Let D(H.n) be upper bound on the degree of any node in a Fibonacci heap with n nodes. D(H.n)=O(logn)
    • Use an array A of size D(H.n)+1. A[i] points to a tree in the root list with degree i.
    • 遍历根节点列表
      • 如找到两个 degree 为 d 的根节点,我们连接(link)两个节点。
      • A[d] = NIL, and A[d+1] = newly linked tree
      • If 4 is marked, clear the mark.
    • Finally, iterate through A array, and set H.min to the min root value.

Pseudocode for extract min

Complexity for extract min

  • Real cost is O(D(n)+t(H))
  • Potential befor extract min is at most t(H)+2m(H)
  • Potential after extract is (D(n)+1)+2m(H)
  • Amortized cost is
    • O(D(n)+t(H)) + ((D(n)+1)+2m(H)) − (t(H)+2m(H)) = O(D(n)) + O(t(H)) − t(H)=O(D(n))
    • we can scale up the units of the potential to cancel out the hidden constant in O(t(H)).

Decreasing Key and Marking

  • 减小一个节点的值,若与堆的性质不冲突则结束
  • 若冲突,将被减小的节点移到根节点列表
    • 如果父节点unmarked,将父节点mark
    • 如果父节点marked,unmark父节点,将父节点移到根节点列表
  • (unmark)若被unmark的节点的父节点被mark,对其父节点重复unmark & move to root list的操作
  • A node is marked if one of its children has been cut, since the last time it’s been cut.
  • One decrease key can create a sequence of cascading cuts.

  • To delete a key, simply decrease its value to −∞ and then do a extract-min.
  • Cutting a node: O(1)
  • Decrease key operation creates c cascading cuts, then cost is O(c)
  • For the amortized cost:
    • After decrease key, the root list contains t(H)+c trees.
    • It contains m(H)−c + 2 marked nodes.
      • c-1 nodes were unmarked by cascading cuts, and the last call to CASCADING-CUT may have marked a node.
    • Change in potential is (t(H)+c + 2(m(H)−c + 2)) − (t(H)+2m(H)) = 4 − c
    • Amortized cost is O(c)+4 − c = O(1) by scaling the hidden constant in the potential appropriately.

Leave a Reply

Your email address will not be published.