社区
教程
Wiki
注册
登录
创作新主题
社区所有版块导航
Python
python开源
Django
Python
DjangoApp
pycharm
DATA
docker
Elasticsearch
分享
问与答
闲聊
招聘
翻译
创业
分享发现
分享创造
求职
区块链
支付之战
aigc
aigc
chatgpt
WEB开发
linux
MongoDB
Redis
DATABASE
NGINX
其他Web框架
web工具
zookeeper
tornado
NoSql
Bootstrap
js
peewee
Git
bottle
IE
MQ
Jquery
机器学习
机器学习算法
Python88.com
反馈
公告
社区推广
产品
短视频
印度
印度
一周十大热门主题
用Python优雅地写LaTeX
易点天下入选虎嗅智库大鲸榜AIGC数字营销技术商TOP15
从AIGC到AGI,为什么我们需要更多的“技术信仰派”?
香港科技大学(广州)机器学习基础实验室招收多名2024Fall/2025Spring博士生、研究助理...
免费课程:机器学习辅助材料模拟实践
开源机器学习编译器的“理想与现实” src:网页链接 -20240423084002
GitHub工业级开源软件:CAD 的官方源代码开放!
自动驾驶十年:AI 大爆发、Transformer「登基」和特斯拉的 ChatGPT 时刻︱酷商业
Open WebUI 私有部署本地chatgpt应用
博士申请 | 美国亚利桑那大学杨幻睿老师招收机器学习方向全奖博士/实习生
关注
Py学习
»
机器学习算法
8个常见机器学习算法的计算复杂度总结!
Datawhale
• 1 年前 • 216 次点击
Datawhale干货
来源:
DeepHub IMBA,编辑:数据派THU
计算的复杂度是一个特定算法在运行时所消耗的计算资源(时间和空间
)
的度量。
计算复杂度又分为两类:
一、时间复杂度
时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。时间复杂度一般指时间复杂性,时间复杂度是一个函数,它定性描述该算法的运行时间,允许我们在不运行它们的情况下比较不同的算法。例如,带有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)
“干货学习,
点
赞
三连
↓
Python社区是高质量的Python/Django开发社区
本文地址:
http://www.python88.com/topic/146899
216 次点击
登录后回复