计算复杂度

在建立好决策树模型后， 做出预测需要遍历决策树， 从根节点一直到叶节点。决策树通常近似左右平衡，因此遍历决策树需要经历大致 [2] 个节点。由于每个节点只需要检查一个特征的值，因此总体预测复杂度仅为 ，与特征的数量无关。 所以即使在处理大型训练集时，预测速度也非常快。

[2] 是二进制对数，它等于 。

然而，训练算法的时候（训练和预测不同）需要比较所有特征（如果设置了max_features会更少一些）

在每个节点的所有样本上。就有了 的训练复杂度。对于小型训练集（少于几千例），Scikit-Learn 可以通过预先设置数据（presort = True）来加速训练，但是这对于较大训练集来说会显着减慢训练速度。