我正在使用scikit-learn中的AdaBoost，并使用典型的决策树作为弱学习器。我想了解运行时间复杂度是如何随数据大小N和弱学习器数量T变化的。我已经搜索了包括Yoav Freund和Robert Schapire的原始AdaBoost论文在内的信息，但没有找到一个非常明确的答案。
回答：
对不起@人名，但他的回答不够全面，因为完全忽略了特征的数量。
AdaBoost的时间复杂度显然是O(T f)，其中f是所使用弱学习器的运行时间。
对于像C4.5这样的普通风格决策树，时间复杂度是O(N D^2)，其中D是特征的数量。单层决策树的时间复杂度将是O(N D)。
你永远不应该通过实验来确定算法的运行时间复杂度，正如有人建议的那样。首先，你将无法轻易区分相似的复杂度，如O(N log(N))和O(N log(N)^2)。此外，还可能被底层实现细节所误导。例如，许多排序算法在数据大部分已排序或包含少数唯一属性时可以表现出O(N)的行为。如果你输入的数据具有很少的唯一值，运行时间将显示出比预期的一般情况更快的结果。
