常见的机器学习算法的计算复杂度

偏执的太偏执、 2023-09-29 17:43 42阅读 0赞

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

## **一、时间复杂度** ##

时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。时间复杂度一般指时间复杂性，时间复杂度是一个函数，它定性描述该算法的运行时间，允许我们在不运行它们的情况下比较不同的算法。例如，带有O(n)的算法总是比O(n²)表现得更好，因为它的增长率小于O(n²)。

![f1aa9bad94714f2eb12e8f23f6f442fb.jpeg][]

## **二、空间复杂度** ##

就像时间复杂度是一个函数一样，空间复杂度也是如此。从概念上讲，它与时间复杂度相同，只需将时间替换为空间即可。维基百科将空间复杂度定义为：

> 算法或计算机程序的空间复杂度是解决计算问题实例所需的存储空间量，以特征数量作为输入的函数。

三、常见的机器学习算法复杂度。

下面我们整理了一些常见的机器学习算法的计算复杂度。

### **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)

[f1aa9bad94714f2eb12e8f23f6f442fb.jpeg]: https://img-blog.csdnimg.cn/f1aa9bad94714f2eb12e8f23f6f442fb.jpeg

发表评论取消回复

表情：

评论列表（有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

相关常见的排序算法的时间复杂度

接着，对每个桶中的元素进行排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次将各个桶中的元素取出，得到的就是有序序列。计数排序不是基于比较的排...

╰半夏微凉°/ 2024年05月03日 14:37/ 0 赞/ 190 阅读

相关时间复杂度的计算

> 时间复杂度的定义：算法的时间复杂度是一个数学函数，定量的描述该算法的运行时间，一个算法的所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复

野性酷女/ 2023年10月13日 19:42/ 0 赞/ 141 阅读

相关常见的机器学习算法的计算复杂度

计算的复杂度是一个特定算法在运行时所消耗的计算资源（时间和空间）的度量。计算复杂度又分为两类，时间复杂度和空间复杂度：一、时间复杂度时间复杂度不是测量一个算法或一段

偏执的太偏执、/ 2023年09月29日 17:43/ 0 赞/ 43 阅读

相关时间复杂度和空间复杂度的计算

一、算法的时间复杂度定义一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n

àì夳堔傛蜴生んèń/ 2023年07月13日 05:30/ 0 赞/ 93 阅读

相关 LeetCode0：学习算法必备知识：时间复杂度与空间复杂度的计算

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项，也是每个高级程序员的必备技能。针对同一问题，可以有很多种算法来解决，但不同的算

迈不过友情╰/ 2023年01月02日 06:29/ 0 赞/ 50 阅读

相关算法的复杂度

算法的复杂度算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却

叁歲伎倆/ 2022年09月14日 13:28/ 0 赞/ 236 阅读

相关算法时间复杂度计算

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvbmRh

青旅半醒/ 2022年08月31日 11:23/ 0 赞/ 324 阅读

相关各个常见算法的时间复杂度

哈希表的插入时间复杂度平均O(1),最好O(1),最差O(n)。排序链表的插入时间复杂度平均O(n),最好O(1),最差O(n)。数组的查询时间复杂度平均O(n),

分手后的思念是犯贱/ 2022年08月31日 11:08/ 0 赞/ 210 阅读

相关常见问题时间复杂度的计算过程

算法是用系统的方法解决实际问题的策略机制，算法的质量将影响到程序的效率，而时间复杂度则是评判时间复杂度的标准，时间复杂度越小，算法越好，程序执行效率越高，反之，

红太狼/ 2022年08月09日 06:18/ 0 赞/ 144 阅读

相关时间复杂度的计算

如果我们想验证一段代码的效率，一个最直接的办法就是编出来之后运行一下，这个方法称为事后统计方法，但是这个方法存在着非常大的弊端，比如我们需要时间编写代码，而代码写完后如果不符合

╰+攻爆jí腚メ/ 2022年06月15日 11:38/ 0 赞/ 345 阅读