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

关注“FightingCV”公众号

回复“AI”即可获得超100G人工智能的教程

转载自：DeepHub IMBA

本文约1000字，建议阅读6分钟
本文为你整理了一些常见的机器学习算法的计算复杂度。

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

计算复杂度又分为两类：

一、时间复杂度

时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。时间复杂度一般指时间复杂性，时间复杂度是一个函数，它定性描述该算法的运行时间，允许我们在不运行它们的情况下比较不同的算法。例如，带有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)

往期回顾

基础知识

【CV知识点汇总与解析】|损失函数篇

【CV知识点汇总与解析】|激活函数篇

【CV知识点汇总与解析】| optimizer和学习率篇

【CV知识点汇总与解析】| 正则化篇

【CV知识点汇总与解析】| 参数初始化篇

【CV知识点汇总与解析】| 卷积和池化篇（超多图警告）

最新论文解析

SlowFast Network：用于计算机视觉视频理解的双模CNN

WACV2022 | 一张图片只值五句话吗？UAB提出图像-文本匹配语义的新视角！

CVPR2022 | Attention机制是为了找最相关的item？中科大团队反其道而行之！

ECCV2022 Oral | SeqTR：一个简单而通用的 Visual Grounding网络

如何训练用于图像检索的Vision Transformer？Facebook研究员解决了这个问题！

ICLR22 Workshop | 用两个模型解决一个任务，意大利学者提出维基百科上的高效检索模型

See Finer, See More！腾讯&上交提出IVT，越看越精细，进行精细全面的跨模态对比！

MM2022｜兼具低级和高级表征，百度提出利用显式高级语义增强视频文本检索

MM2022 | 用StyleGAN进行数据增强，真的太好用了

MM2022 | 在特征空间中的多模态数据增强方法

ECCV2022|港中文MM Lab证明Frozen的CLIP 模型是高效视频学习者

ECCV2022｜只能11%的参数就能优于Swin，微软提出快速预训练蒸馏方法TinyViT

CVPR2022|比VinVL快一万倍！人大提出交互协同的双流视觉语言预训练模型COTS，又快又好！

CVPR2022 Oral｜通过多尺度token聚合分流自注意力，代码已开源

CVPR Oral | 谷歌&斯坦福（李飞飞组）提出TIRG，用组合的文本和图像来进行图像检索