CART的时间复杂度的详解

大家在看算法的时候肯定会考虑时间的复杂度，那么就来讲一下CART的时间复杂度。

对于一个样本数量是N的数据集，他的feature（特征）数是M，那么对应生成的树的深度是D 。

在cart生长时，需要把所有的feature内的值都作为一个分裂的候选，然后根据这个计算一个指标，例如信息增益，信息增益比，gini指数等等，于是每层的时间复杂度是O(N*M),再加上树的深度D，那么总的时间复杂度就是O(N*M*D)。