Skiena，算法设计手册，关于堆排序（第 111 页）

Question

我正在自学 "The Algorithm Design Manual" 这本书。我目前正在学习第 4 章（HeapSort），在第 111 页上有一个方程式，我无法理解

就像

Space efficiency thus demands that we not allow holes in our tree—i.e., that each level be packed as much as it can be. If so, only the last level may be incomplete. By packing the elements of the last level as far to the left as possible, we can represent an n-key tree using exactly n elements of the array. If we did not enforce these structural constraints, we might need an array of size 2n to store the same elements. Since all but the last level is always filled, the height h of an n element heap is logarithmic because: so h = lg n

我不明白的是如何从上面的等式中确定h =logn？我的数学很生疏，但据我所知它应该像 h =log((n+1)/2)

我希望这里有读过这本书的人能够帮助我理解这一点

在此先致谢

Answer 1

Skienna 的书指出（虽然不够清楚）h 是渐近 对数。即，

2^{h+1} >= n+1 等同于

h+1 >= log(n+1),

因此您忽略常量并得到 h=O(log n)。你的计算是正确的，它给出了相同的结果，但你应该观察渐近行为。

Answer 2

你是怎么得到h = log((n+1) / 2)的？假设以 2 为基数，我们有：

2^(h+1) - 1 >= n
2^(h+1) >= n+1 | apply log
log(2^(h+1)) >= log(n+1)
h+1 >= log(n+1)
(log n)+1 >= log(n+1)

=> h = O(log n) 

书上应该说h = O(log n)准确一点，不过这样也行。

阅读有关 big-oh notation 的内容，了解常量为何无关紧要。其实对数的底也无所谓。