计算复杂度是对特定算法在运行时消耗的计算资源(时间和空间)的度量。计算复杂度分为两类:1.时间复杂度时间复杂度不是衡量一个算法或一段代码在某种机器或条件下运行所花费的时间。时间复杂度一般指的是时间复杂度,时间复杂度是一个定性描述算法运行时间的函数,可以让我们在不运行的情况下比较不同的算法。例如,具有O(n)的算法将始终比O(n2)执行得更好,因为它的增长率小于O(n2)。2.空间复杂度正如时间复杂度是一个函数一样,空间复杂度也是。概念上和时间复杂度一样,只是用空间代替时间。维基百科将空间复杂度定义为:算法或计算机程序的空间复杂度是解决计算问题实例所需的存储空间量,是作为输入的特征数量的函数。下面我们对一些常见的机器学习算法的计算复杂度进行梳理。1.线性回归n=训练样本数,f=特征数训练时间复杂度:O(f2n+f3)预测时间复杂度:O(f)运行时空间复杂度:O(f)2.逻辑回归:n=数训练样本的数量,f=特征数量训练时间复杂度:O(f*n)预测时间复杂度:O(f)运行时空间复杂度:O(f)3,支持向量机:n=训练样本数量,f=特征数,s=支持向量数训练时间复杂度:O(n2)到O(n3),训练时间复杂度随不同的内核而变化。预测时间复杂度:O(f)到O(s*f):线性核为O(f),RBF和多项式为O(s*f)运行时空间复杂度:O(s)4,朴素贝叶斯S: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=树数DeepTrainingTime复杂度:O(n*log(n)*f*k)预测时间复杂度:O(d*k)运行时空间复杂度:O(p*k)7,KNeighbors:n=TrainingNumberofsamples,f=number特征,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-表示聚类:n=训练样本数,f=特征数,k=簇数,i=迭代次数训练时间复杂度:O(n*f*k*i)运行时空间复杂度:O(n*f+k*f)
