多项式复杂度的算法是复杂度比较高的算法。这句话是错误的。
1、时间复杂度
时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。时间复杂度一般指时间复杂性,时间复杂度是一个函数,它定性描述该算法的运行时间,允许我们在不运行它们的情况下比较不同的算法。例如,带有O(n)的算法总是比O(n)表现得更好,因为它的增长率小于O(n)。
2、空间复杂度
就像时间复杂度是一个函数一样,空间复杂度也是如此。 从概念上讲,它与时间复杂度相同,只需将时间替换为空间即可。 维基百科将空间复杂度定义为:
算法或计算机程序的空间复杂度是解决计算问题实例所需的存储空间量,以特征数量作为输入的函数。
下面我们整理了一些常见的机器学习算法的计算复杂度。
1、线性回归
n= 训练样本数,f = 特征数;训练时间复杂度:O(fn+f);
预测时间复杂度:O(f);运行时空间复杂度:O(f)
2、逻辑回归
n= 训练样本数,f = 特征数;训练时间复杂度:O(f*n)
预测时间复杂度:O(f);运行时空间复杂度:O(f)