机器算法验证 - XGBoost论文——时间复杂度分析 - 吾爱随笔录

我正在阅读XGBoost 论文，我对 4.1 中标题为“时间复杂度分析”的小节感到困惑。在这里，作者断言精确的贪心算法与 $K$ 树，最大深度 $d$ 每棵树，和 $\|\mathbf{x}\|_0$ “训练数据中的非缺失条目”，使用原始的稀疏感知算法，会产生前 3 个因素对我来说很有意义（部分） - 我将其解释为：

O (K d ‖ x ‖_{0} \log n) .

$O(Kd\|\mathbf{x}\|_0\log n).$

K d ‖ x ‖_{0}

$Kd\|\mathbf{x}\|_0$

有棵树，给你 $K$ $K$
在每棵树的层中，您需要扫描块条目以找到最佳分割。（我的理解是是非零特征值的总数，聚合在所有特征列和所有训练示例中。这意味着每个块由 CSC 格式的数字。）这给出了一个因子。 $d$ $\|\mathbf{x}\|_0$ $\|\mathbf{x}\|_0$ $3\|\mathbf{x}\|_0$ $d\|\mathbf{x}\|_0$

但是，我不确定应该表示什么（本文的本节未指定）或因子来自何处。根据本文前面的用法，我假设是训练示例的数量，但我不清楚这如何导致精确贪心算法的时间复杂度乘法增加。 $n$ $\log n$ $n$ $\log n$

有谁了解作者是如何达到这种时间复杂度的？任何帮助将非常感激。