算法复杂度

时间复杂度可以看作是机器学习算法针对输入大小执行速度的快慢的度量。时间复杂度总是相对于某些输入大小（例如n）给出的。

空间复杂度可以看作是执行机器学习算法所需的额外内存量。像时间复杂度一样，它也针对某些输入大小（n）给出。

机器学习算法/机器学习模型的复杂性通常使用大O表示法表示，大O表示法定义了算法的上限，它仅从上方限制函数。

大O表示法：算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

下图显示了算法复杂性的不同情况：

 

 

 

 

为了写出计算复杂度，我们假设

n =训练示例数，d =数据维数，k =邻居数

k最近邻算法的复杂度

训练时间复杂度 = O（knd）

遍历每个训练观测值，并计算机器学习训练集观测值和新观测值之间的距离 d。

时间相对于实例数（n）和维数（d）是线性的。

空间复杂度 = O（nd）

K最近邻居存储数据。测试需要较长的时间，因为您必须将每个测试实例与整个训练数据进行比较。

逻辑回归的复杂度

训练时间复杂度在逻辑回归中意味着解决最优化问题。

训练时间复杂度= O（nd）

空间复杂度 = O（d）

注意： 逻辑回归对于低延迟应用程序非常有用。

支持向量机（SVM）的复杂度

训练时间复杂度 = O（n）

注意：如果n大，请尽量避免使用支持向量机（SVM）。

运行时复杂度 = O（k * d）

K =支持向量数，d =数据的维数

决策树的复杂度

训练时间复杂度= O(n*log(n)*d)

n=训练集中的样本数

d=数据的维数

运行时复杂度= O(树的最大深度)

注意:当我们有大量低维数据时，我们使用决策树。

随机森林的复杂度

训练时间复杂度= O(n*log(n)*d*k)

k=决策树的数量

注:当我们有大量具有合理特征的数据时。然后我们可以使用多核并行化我们的机器学习模型来训练不同的决策树。

运行时复杂度= O(树的深度* k)

空间复杂度= O(树的深度*k)

注意:随机森林相对于其他机器学习算法速度更快。

朴素贝叶斯的复杂度

训练时间复杂度 = O（n * d）

运行时复杂度 = O（c * d）

我们必须为每个类'c'检索特征

结论：

如果您有大量数据，则根据要解决的业务问题选择算法。如果需要降低计算复杂性，可以尝试减少数据的维数。