我正在使用来自 scikit-learn 的 AdaBoost，使用典型的 DecisionTree 弱学习器。我想了解数据大小 N 和弱学习器数量 T 方面的运行时复杂性。我搜索了这些信息，包括 Yoav Freund 和 Robert Schapire 的一些原始 Adaboost 论文，但没有看到非常明确的答案.
最佳答案
没有不尊重 orgrisel 的意思，但他的回答缺乏，因为它完全忽略了功能的数量。
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) 行为。如果您输入的唯一值很少，则运行时会显示出比预期的一般情况更快的结果。
关于machine-learning - AdaBoost 的 O() 运行时复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22397485/