algorithm - 关于max-heapify时间复杂度的一个问题

Question

每个人。我刚来这地方。

我正在使用 Thomas H. Cormen 等人撰写的“算法简介”自学算法。我遇到了一个让我很困惑的问题，所以我来这里寻求帮助。如果有人可以帮助我，我将非常感激。

问题是关于 max-heapify 的复杂性。这是那本书第6章的练习，它说

证明 MAX-HEAPIFY 在大小为 n 的堆上的最坏情况运行时间为 (lgn)。lg 是以 2 为底的对数。

谁能向我解释为什么复杂性是（lgn）？为什么没有像 O(lgn) 这样的上限？

书上说MAX-HEAPIFY的运行时间是O(lgn)，我理解是因为树的高度是O(lgn)，但是为什么会因为最坏的情况而变成(lgn)呢？

标签： algorithmtime-complexityheap