计算这个由多个分类器组成的集合的Big-O符号

Question

我有一个如下所示的模型，我正在尝试计算它的总体计算复杂度(Big-O记法)。

​

​

在这个模型中，类型为"A“的分类器的时间复杂度为O(mN)，其中N是数据集中的实例数，m是由分类器"A”确定的常量变量(我正在尝试生成一个最小的工作示例，以便问题可以清楚地表达出来。如果需要更多关于m)的信息，请让我知道。分类器"B“的时间复杂度为O(N^2)，其中N是数据集中的实例数。

这个模型基本上是一个集成分类器，由n个"A“分类器和m个"B”分类器组成。最后的决定是基于简单的加权多数票。为了确定权重，我使用数据集训练系统，同时将随机生成的权重组合分配给分类器"A“和"B”。为系统选择的最佳权重组合是在数据集的训练子集上提供最佳检测精度的组合。然后，还在系统的测试期间使用该选定的权重组合。

作为算法和时间复杂性分析的新手，我只能计算或研究我在上面提出/陈述的单个分类的时间复杂性，但是考虑到n+m分类器和多数投票阶段(最终决策阶段)，系统的总体计算复杂性是多少？

Answer 1

假设a_1, a_2, a_3, a_4, ...., a_n是由类型为A的n分类器生成的常量。

让a_max = max{a_1, a_2, a_3, ...., a_n}

A类型的n分类器的时间复杂度是：O(n*a_max*N)

B类型的m分类器，每个都在时间复杂度O(N^2)中运行

对于总的m分类器，应该是：O(m*N^2)

时间复杂度：O(m*N^2 + n*a_max*N)

你也可以这样写：

O(m*N^2 + (a_1 + a_2 + a_3 + ... + a_n)*N), a tighter bound.