6.5 计算复杂度

进行预测需要从根到叶遍历决策树。决策树通常是近似平衡的，因此遍历决策树需要经过大约\(\text{O}(log_2(m))\)个节点。由于每个节点仅需要检查一个特征值，因此总体预测复杂度为\(\text{O}(log_2(m))\)。与特征数量无关。因此，即使处理大训练集，预测也非常快。训练算法比较每个节点上所有样本上的所有特征（如果设置了max_features，则更少）。比较每个节点上所有样本的所有特征会导致训练复杂度为\(\text{O}(n \times m log_2(m))\)。对于小训练集（少于几千个实例），Scikit-Learn可以通过对数据进行预排序（设置presort=True）来加快训练速度，但是这样做会大大降低大训练集的训练速度。