algorithm - CLRS 的书是如何得出 BUILD_MAX_HEAP 不是渐近紧的 O(n log n) 的？

Question

CLRS 第 157 页第 3 版。我的问题不是关于为什么 BUILD_MAX_HEAP 的复杂性是 O(n) 也不是证明。然而，对于他们用来得出结论的系统方法，它在 O(n log n) 下不是渐近紧的。从逻辑上讲，O(n log n) 是正确的。

我被卡住的要点是他们是如何得到直觉的，即有更好的更严格的上限。如果不是 CLRS 的解释。我们会知道吗？

我关于直觉的问题的核心是我们必须让自己意识到有一个更好更严格的界限。

我们是否应该为我们找到的每个算法寻找更紧密的界限？我的意思是外行人的逻辑结论是 O(n log n)。他怎么能离这里更远。我错过了两者之间的一些基础知识吗？

Answer 1

how did they get the intuition that, there is much better tighter upper bound.

我不知道他们具体是如何获得直觉的，但这是一种看待它的方式(可能是事后诸葛亮)。

Build-Heap 的复杂性，至少在直觉上，似乎类似于

T(n) = T(n/2) + Θ(n)

其解是T(n) = Θ(n)。

(注意以下不是证明，只是直觉!)

假设您有一个包含 n/2 个元素的二叉堆，并且其最后一行已满，并且您将元素的数量加倍。这基本上会添加另一行。

元素数量加倍(至少在本例中是这样)如何改变 Build-Heap 的时间？

• 由于倒数第二行，对 Heapify 的调用 Θ(n) 次，但显然每个调用 O(1) 工作。

• 对于倒数第二行以上的行，Θ(n) 调用 Heapify 基本上和以前一样运行，但是每个行都有另一个 O (1) 在最后工作(路径长 1)。

Are we suppose to hunt for tighter tighter bound for every algorithm we find ?

在某种程度上，是的。为算法寻找更严格的界限总是会引起人们的兴趣。请注意，对于 Heapsort，甚至有人对 proving 感兴趣一个变体使用了 2 n log(n) (1 - o(1)) 操作，而另一个变体使用了 n log(n) (1 + o(1)) 操作，即使两者都是 Θ(n log(n))。

I mean a logical conclusion for a laymen is O(n log n).

外行可能主要使用专家广泛研究过的算法。

How can he go further from here.

可能没有找到算法边界的算法。一种可能的方法是绘制增加 n 值的运行时间，并查看运行时间的外观。如果它看起来是线性的，则它不是证明，而是指示要查找的内容。