二项堆：证明合并操作的时间复杂度为O(log n)

Question

二项堆：证明合并操作的时间复杂度为O(log n)

algorithmdata-structuresfunctional-programmingbig-oml

5

我正在阅读 Okasaki的纯函数数据结构，并尝试做一些练习。其中之一是证明二项堆merge需要O(log n)时间，其中n是堆中节点的数量。

functor BinomialHeap (Element:ORDERED):HEAP=
struct
  structure Elem=Element
  datatype Tree = Node of int*Elem.T*Tree list
  type Heap = Tree list
  fun link (t1 as Node (r,x1,c1), t2 as Node (_,x2,c2))=
    if Elem.leq(x1,x2)
    then Node (r+1,x1,t2::c1)
    else Node (r+1,x2,t1::c2)
  fun insTree (t,[])=[t]
     |insTree (t,ts as t'::ts')=
        if rank t < rank t' then t::ts else insTree(link(t,t'),ts')
  fun insert (x,ts)=insTree(Node(0,x,[]),ts) (*just for reference*)
  fun merge (ts1,[])=ts1
     |merge ([],ts2)=ts2
     |merge (ts1 as t1::ts1', ts2 as t2:ts2')=
        if rank t1 < rank t2 then t1::merge(ts1',ts2)
        else if rank t2 < rank t1 then t2::merge(ts1,ts2')
        else insTree (link(t1,t2), merge (ts1',ts2'))
end

很明显，merge函数会调用自身max(numNodes ts1, numNodes ts2)次，但由于insTree的最坏情况为O(log n)，你能解释一下为什么merge的时间复杂度是O(log n)吗？

- Justin Raymond

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m7thon · Accepted Answer

首先需要注意的是，merge 最多会被调用 (numNodes ts1 + numNodes ts2) 次，并且这是 O(log n) 次。 (为了明确，ts1 和 ts2 是二项树列表，其中一个排名为 r 的树恰好包含 2^r 个节点，每个等级最多出现一次。因此，在 ts1 中有 O(log n1) 个这样的树，在 ts2 中有 O(log n2) 个这样的树，其中 n1 和 n2 是堆中节点的数量，n=n1+n2。)

关键点是需要注意的是，对于每个秩（通过merge或递归），insTree 最多调用一次，而最大可能的秩是 log_2(n)。原因如下:

如果从merge中调用insTree，则假设r = rank t1 = rank t2，并且link(t1,t2)将具有等级r+1。因此，假设以秩r+1调用insTree。现在考虑merge(ts1'，ts2')会发生什么。将出现在ts1'和ts2'中的树中的最小秩为r' >= r+1。因此，由于两个等级为r'的树将被链接形成秩为r'+1的树，所以将再次从merge中调用insTree以获得秩r'+1。但是，合并堆merge(ts1'，ts2')因此可能不包含秩为r'的树，因此之前对insTree的调用不能递归超过r'。

将它们放在一起：

insTree 最多调用 O(log n) 次，每次调用都是恒定时间（因为我们将递归视为单独的调用）
merge 最多调用 O(log n) 次，每次调用都是恒定时间（因为我们将对 insTree 的调用和 link 视为单独的调用）

因此，整个合并操作是 O(log n) 的。

编辑：顺便说一下，合并二项堆非常类似于加法运算中的二进制数相加。如果一个大小为n的堆具有秩为r的树，则当二进制数n在2^r位置上有一个'1'时，它将具有该秩的树。在合并这样的堆时，您需要从最低秩到最高秩进行处理--或者从最低有效位到最高有效位的位置。相同秩的树需要链接（添加“1”），并插入/“进位”到更高的秩位置。