我最近正在研究siftDown
用于构建二进制堆的算法。在“算法和数据结构:基本工具箱”一书中练习 6.5 中指出,该算法的给定实现需要2*log(n)
元素比较。现在,我试图弄清楚为什么会这样,但我做不到。为什么这是正确的?
问问题
237 次
1 回答
2
调用时siftDown(i)
,您首先执行两个元素比较:
- 第一个是
h[2i]
和之间h[2i+1]
。 - 第二个是
h[i]
和之间h[m]
。
进行两次比较后,您递归调用siftDown(m)
wherem=2i
或m=2i+1
。也就是说,每次siftDown()
使用n
-element 堆调用都会导致进行两次元素比较和对siftDown()
-elementn/2
堆的调用。
因此,使用-element 堆T(n)
调用时进行的比较次数满足:siftDown()
n
T(n) = 2 + T(n/2)
这种递推关系的解是
T(n) = 2logn
您可以2logn
通过观察每次都恰好进行 2 个元素比较,并且次数为logn
(因为如果您开始n
并不断除以 2,那么您就完成了)logn
部门)。
因此,由 进行的元素比较总数siftDown()
约为2logn
.
于 2016-06-03T14:08:41.920 回答