求教一道算法题

晓东的算法设计与分析第2版的Ｐ９５页，说用最小堆实现优先队列。初始化优先队列需要用Ｏ（n).
我想问一下，初始化优先队列为什么不是Ｏ（nlogn)。谢谢。

8 个解决方案

#1

我是这样想的，初始化优先队列相当于把n个数push进最小堆中，
每个push是logn的复杂度，则n个是nlogn的复试度。

#2

up

#3

他的算法不一样：
大于n/2的结点没有子节点自成最小堆，从n/2个结点开始往前向下调整，直到根结点
你算一算，大概这个这样的序列
sigma(k*n/2^k) (k=1,2...logn), 这个级数是O(n)的

#4

我回去帮你核实下。现在有事呵呵。

#5

n/2 + n/4 + n/8 + ...... + 1 = O(n)

#6

不懂，等详细一点的解释。

#7

建立最小堆,需要元素之间的两两比较,这样的话需要先把元素分为2组,共需要比较n/2次,选出n/2个较小的
然后再对这n/2个较小的元素进行分组,分为2组,每组n/4个,进行n/4次比较,得到n/4个较小的元素,以此类推,
因此总共需要n/2 + n/4 + n/8 + ...... + 1次比较 = n - 1,因此复杂度是O(n)

引用 6 楼 liefeng999 的回复:

不懂，等详细一点的解释。

#8

理解了，
递归式是：
T(n)=T(n/2)+O(n)
于是为O(n)

谢谢
楼上的两位都提供了极佳的帮助！！
要是我分数多点真想多给点分。