a**********3
发帖数: 64 | 1 为啥in fact, the cost is O(n), 不是O(nlogn)? |
f*****e
发帖数: 2992 | 2 因为只是partially sorted。siblings无法判断谁大谁小。
【在 a**********3 的大作中提到】
: 为啥in fact, the cost is O(n), 不是O(nlogn)?
|
a**********3
发帖数: 64 | 3 还是不太懂，bubbleDown cost O(logn), n 次 bubbleDown不是O(nlogn)么？
【在 f*****e 的大作中提到】
: 因为只是partially sorted。siblings无法判断谁大谁小。
|
M********n
发帖数: 34 | 4 每次递归heapify的时候， 比较的是半个partition的一半，
累加起来， 就不是nlgn， 而正好是O（n）。
youtube的mit课程里有10分钟专门讲这个。 |
a**********3
发帖数: 64 | 5 soga...
多谢猴子豆！
【在 M********n 的大作中提到】
: 每次递归heapify的时候， 比较的是半个partition的一半，
: 累加起来， 就不是nlgn， 而正好是O（n）。
: youtube的mit课程里有10分钟专门讲这个。
|
j******2
发帖数: 362 | 6 最底层有n/2个节点，它们的比较次数是0
倒数第二层有n/4个节点，它们的比较次数是1
倒数第三层有n/8个节点，它们的比较次数是2
...
最后一层有1个节点，比较次数是log(n)-1
所以总的复杂度是:
(n/4)*1+(n/8)*2+(n/16)*3+...+1*(log(n)-1)
=n*(1/4+2/8+3/16+...)
括号里这个序列(i-1)/(2^i)是个收敛数列，其和在i->无穷时都是常数。所以一小段的
和更是常数。所以上面的式子
＝n*c |
a**********3
发帖数: 64 | 7 大牛，你讲的好清楚，非常感谢！
【在 j******2 的大作中提到】
: 最底层有n/2个节点，它们的比较次数是0
: 倒数第二层有n/4个节点，它们的比较次数是1
: 倒数第三层有n/8个节点，它们的比较次数是2
: ...
: 最后一层有1个节点，比较次数是log(n)-1
: 所以总的复杂度是:
: (n/4)*1+(n/8)*2+(n/16)*3+...+1*(log(n)-1)
: =n*(1/4+2/8+3/16+...)
: 括号里这个序列(i-1)/(2^i)是个收敛数列，其和在i->无穷时都是常数。所以一小段的
: 和更是常数。所以上面的式子
|
