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

点击上方“小白学视觉”，选择加"星标"或“置顶”

重磅干货，第一时间送达

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

计算复杂度又分为两类：

一、时间复杂度

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

二、空间复杂度

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

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

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

1. 线性回归

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

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

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

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

2. 逻辑回归

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

训练时间复杂度：O(f*n)

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

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

3. 支持向量机

n= 训练样本数，f = 特征数，s= 支持向量的数量

训练时间复杂度：O(n²) 到 O(n³)，训练时间复杂度因内核不同而不同。

预测时间复杂度：O(f) 到 O(s*f):线性核是 O(f)，RBF 和多项式是 O(s*f)

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

4. 朴素贝叶斯

n= 训练样本数，f = 特征数，c = 分类的类别数

训练时间复杂度：O(n*f*c)

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

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

5. 决策树

n= 训练样本数，f = 特征数，d = 树的深度，p = 节点数

训练时间复杂度：O(n*log(n)*f)

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

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

6. 随机森林

n= 训练样本数，f = 特征数，k = 树的数量，p=树中的节点数，d = 树的深度

训练时间复杂度：O(n*log(n)*f*k)

预测时间复杂度：O(d*k)

运行时空间复杂度：O(p*k)

7. K近邻

n= 训练样本数，f = 特征数，k= 近邻数

Brute：

训练时间复杂度：O(1)

预测时间复杂度：O(n*f+k*f)

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

kd-tree：

训练时间复杂度：O(f*n*log(n))

预测时间复杂度：O(k*log(n))

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

8. K-means 聚类

n= 训练样本数，f = 特征数，k= 簇数，i = 迭代次数

训练时间复杂度：O(n*f*k*i)

运行时空间复杂度：O(n*f+k*f)

好消息！
小白学视觉知识星球
开始面向外开放啦👇👇👇



下载1：OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

下载2：Python视觉实战项目52讲


    
在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。

下载3：OpenCV实战项目20讲
在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。

交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~