计算的复杂度是一个特定算法在运行时所耗费的计算资源 (工夫和空间) 的度量。
计算复杂度又分为两类:
1、工夫复杂度
工夫复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所破费的工夫。工夫复杂度个别指工夫复杂性，工夫复杂度是一个 函数 ，它定性描述该算法的运行工夫，容许咱们在不运行它们的状况下比拟不同的算法。例如，带有 O(n) 的算法总是比 O(n²)体现得更好，因为它的增长率小于 O(n²)。
2、空间复杂度
就像工夫复杂度是一个函数一样，空间复杂度也是如此。从概念上讲，它与工夫复杂度雷同，只需将工夫替换为空间即可。维基百科将空间复杂度定义为：
算法或计算机程序的空间复杂度是解决计算问题实例所需的存储空间量，以特色数量作为输出的函数。
上面咱们整顿了一些常见的机器学习算法的计算复杂度。
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(sf): 线性核是 O(f)，RBF 和多项式是 O(sf)
运行时空间复杂度：O(s)
4、奢侈贝叶斯：
n= 训练样本数，f = 特色数，c = 分类的类别数
训练工夫复杂度：O(nfc)
预测工夫复杂度：O(c*f)
运行时空间复杂度：O(c*f)
5、决策树：
n= 训练样本数，f = 特色数，d = 树的深度，p = 节点数
训练工夫复杂度：O(nlog(n)f)
预测工夫复杂度：O(d)
运行时空间复杂度：O(p)
6、随机森林：
n= 训练样本数，f = 特色数，k = 树的数量，p= 树中的节点数，d = 树的深度
训练工夫复杂度：O(nlog(n)f*k)
预测工夫复杂度：O(d*k)
运行时空间复杂度：O(p*k)
7、K 近邻：
n= 训练样本数，f = 特色数，k= 近邻数
Brute：
训练工夫复杂度：O(1)
预测工夫复杂度：O(nf+kf)
运行时空间复杂度：O(n*f)
kd-tree：
训练工夫复杂度：O(fnlog(n))
预测工夫复杂度：O(k*log(n))
运行时空间复杂度：O(n*f)
8、K-means 聚类：
n= 训练样本数，f = 特色数，k= 簇数，i = 迭代次数
训练工夫复杂度：O(nfk*i)
运行时空间复杂度：O(nf+kf)
https://avoid.overfit.cn/post/2a0f0c99c9bc47cfa440816981716a88
作者：Rafay Qayyum