8个常见的机器学习算法的计算复杂度总结

计算的复杂度是一个特定算法在运行时所消耗的计算资源(时间和空间)的度量。

计算复杂度又分为两类:

1、时间复杂度

时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。时间复杂度一般指时间复杂性，时间复杂度是一个函数，它定性描述该算法的运行时间，允许我们在不运行它们的情况下比较不同的算法。例如，带有O(n)的算法总是比O(n²)表现得更好，因为它的增长率小于O(n²)。

2、空间复杂度

就像时间复杂度是一个函数一样，空间复杂度也是如此。从概念上讲，它与时间复杂度相同，只需将时间替换为空间即可。维基百科将空间复杂度定义为：

算法或计算机程序的空间复杂度是解决计算问题实例所需的存储空间量，以特征数量作为输入的函数。

下面我们整理了一些常见的机器学习算法的计算复杂度。

1、线性回归

n= 训练样本数，f = 特征数

训练时间复杂度：O(f²n+f³)

预测时间复杂度：O(f)

运行时空间复杂度：O(f)

完整文章：

https://avoid.overfit.cn/post/2a0f0c99c9bc47cfa440816981716a88