CLRS 书是如何得出结论 BUILD_MAX_HEAP 不是渐近紧的 O(n log n)？
How did CLRS book conclude BUILD_MAX_HEAP is not asymptotically tight with O(n log n)?
CLRS 书第 157 页第 3 版。我的问题不是关于为什么 BUILD_MAX_HEAP 的复杂性是 O(n) 也不是证明。然而，对于他们用来得出结论的系统方法，它在 O(n log n) 下不是渐近紧的。逻辑上说 O(n log n) 是正确的。
我被卡住的一点是他们是如何得到直觉的，即有更好的更严格的上限。如果不是 CLRS 的解释。我们会知道吗？
我关于直觉的问题的核心是我们必须让自己意识到有一个更好更严格的界限。
我们是否应该为我们找到的每个算法寻找更紧密的界限？我的意思是外行人的逻辑结论是 O(n log n)。他怎么能离这里更远。我错过了两者之间的一些基础知识吗？
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 的时间？
因为倒数第二行，有Θ(n)次调用Heapify，但显然每一次都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 的值，然后查看 运行 时间的外观。如果它看起来是线性的，则它不是证明，而是指示要查找的内容。
CLRS 书第 157 页第 3 版。我的问题不是关于为什么 BUILD_MAX_HEAP 的复杂性是 O(n) 也不是证明。然而，对于他们用来得出结论的系统方法，它在 O(n log n) 下不是渐近紧的。逻辑上说 O(n log n) 是正确的。
我被卡住的一点是他们是如何得到直觉的，即有更好的更严格的上限。如果不是 CLRS 的解释。我们会知道吗？
我关于直觉的问题的核心是我们必须让自己意识到有一个更好更严格的界限。
我们是否应该为我们找到的每个算法寻找更紧密的界限？我的意思是外行人的逻辑结论是 O(n log n)。他怎么能离这里更远。我错过了两者之间的一些基础知识吗？
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 的时间？
因为倒数第二行，有Θ(n)次调用
Heapify，但显然每一次都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 的值，然后查看 运行 时间的外观。如果它看起来是线性的，则它不是证明，而是指示要查找的内容。