AdaBoost 的 O() 运行时复杂度是多少？

Question

我正在使用来自 scikit-learn 的 AdaBoost，使用典型的 DecisionTree 弱学习器。我想了解数据大小 N 和弱学习器 T 数量方面的运行时复杂性。 .

Answer 1

没有不尊重 orgrisel 的意思，但他的回答缺乏，因为它完全忽略了功能的数量。

AdaBoost 的时间复杂度为 O(T f)，其中 f 是使用中的弱学习器的运行时间。

对于普通风格的决策树，例如 C4.5，时间复杂度是O(ND^2)，其中 D 是特征的数量。单级决策树将是 O(ND)

您永远不应该像建议的那样使用实验来确定算法的运行时复杂性。首先，您将无法轻松区分类似的复杂性，例如 O(N log(N)) 和 O(N log(N)^2)。它还存在被底层实现细节所愚弄的风险。例如，当数据大部分排序或包含一些唯一属性时，许多排序可能表现出 O(N) 行为。如果您输入的唯一值很少，则运行时会显示出比预期的一般情况更快的结果。