GBDT的时间复杂度是多少？

Question

它是树的深度还是点的维度

1. 伪残差（r_im）的计算为每点O（d）。因此，对于大小为n的数据集，每次迭代计算伪残差为O（nd）。总时间复杂度为O（nd*m）。这里d是维度

2. gamma_m的计算速度非常快，因为它是一个简单的一维优化问题，我们试图找到最好的gamma_m，它是一个标量。在实践中，这通常是一个恒定的时间步长

因此，总体而言，M决策树的压缩顺序所需的时间O（nlgndM）比上述两个步骤所需的时间O（ndM+const）要多。由于lg（n）是M决策树压缩中的附加项，O（nlgndM）+O（ndM+const）=O（nlgnd*M）。这里d是决策树的深度