让$N$= 训练样本的数量，$d$= 特征的维度和$c$=类数。

然后训练有复杂性：

1. 朴素贝叶斯是$O(Nd)$，它需要做的就是计算每个特征值的频率$d_i$对于每个班级。
2. $k$-NN 在$\mathcal{O}(1)$（甚至有人说不存在，但是训练的空间复杂度是$\mathcal{O}(Nd)$因为您需要存储数据，这也需要时间）。
3. 非线性非近似 SVM 是$O(N^2)$或者$O(N^3)$取决于内核。你可以得到一个$O(N^3)$向下$O(N^{2.3})$有一些技巧。
4. 近似 SVM 是$O(NR)$其中 R 是迭代次数。

测试复杂性：

1. 朴素贝叶斯在$\mathcal{O}(cd)$因为你必须检索$d$每个特征值$c$类。
2. $k$-NN 在$\mathcal{O}(Nd)$因为您必须将测试点与数据库中的每个数据点进行比较。

资料来源：“核心向量机：超大型数据集上的快速 SVM 训练”- http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

对不起，我不知道其他人。