我会给出一个不同的答案，因为评论太多了，而且它处理的是更一般的方法。

因此，在 ESL 中，它们确实描述了分支定界的计算时间（更准确地说，它在我看来就像是分而治之）。

当我们种植一棵树时，我们用表示观察的数量，用表示子节点的数量。是固定的，我假设我们一般不会松懈。此外，我们可以用表示在给定节点计算分割点的处理时间。$N$$K$$K$$f(N)$

因此，我们可以递归地编写执行时间的公式，例如： 我们在这里考虑的子节点将大小为的个子集大小相等的。我们知道这是最好的情况。

但是，我们可以看到这是主定理的一个众所周知的应用。这在CLRS book中有很好的记录。我有第 3 版，详细信息在第 4.5 节，证明在下一节。我不太记得细节，但我记得如果扩展递归并将一些术语组合在一起，它不会太复杂。

但是，对于这种情况，重要的是当 - 线性时间时，算法的结果时间是。该时间是针对单个输入变量计算的，因此，我们个变量的总时间将为$f(N)=O(N)$$T(N) = O(N logN)$$P$$O(P N logN)$

如果所有输入最初都按排序，那么这个时间对于树的生长是可以实现的，并且在这个排序的输入上找到分割值需要线性时间。在这里，我们可以应用在线方差算法，正如我在之前对的回答中提到的那样。对于更容易找到中位数。我承认我从未尝试过其他树的损失函数。$O(P N logN)$$L_2 = \frac{1}{N}(y-\hat{y})^2$$L_1 = \frac{1}{N}|y-\hat{y}|$

但是请注意，如果拆分大小相等，则主定理适用于最佳情况。最坏的情况是分裂非常不平衡。在那里，可以应用不同的 Master Theorem 情况，时间将变为。$O(P N^2)$

作为结论，我假设 ESL 作者通常以用于描述快速排序算法的方式使用该术语。对于某些特定的数据设置，通常快速排序会给出运行时间，最坏的情况是$O(N logN)$$O(N^2)$

我希望它有所帮助。

在这里查看我从另一个问题的回答。虽然我没有论文参考，但您可以轻松地发现，对于长度为个数字输入，您必须：$p$$N$

• 遍历所有个输入 -$p$$O(p)$
• 对每个输入进行升序排序 -$O(N log(N))$
• 在线性时间内计算 2 个运行方差，一个从左侧开始，一个从右侧开始 -$O(N)$

每个属性的主导时间是排序时间，因此我们有$O(p N log(N))$.