- 综合排序
- 最热优先
- 最新优先
- 来自专栏DeepHub IMBA
8个常见的机器学习算法的计算复杂度总结
计算的复杂度是一个特定算法在运行时所消耗的计算资源(时间和空间)的度量。 计算复杂度又分为两类: 1、时间复杂度 时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。 2、空间复杂度 就像时间复杂度是一个函数一样，空间复杂度也是如此。从概念上讲，它与时间复杂度相同，只需将时间替换为空间即可。 1、线性回归 n= 训练样本数，f = 特征数 训练时间复杂度：O(f²n+f³) 预测时间复杂度：O(f) 运行时空间复杂度：O(f) 2、逻辑回归： n= 训练样本数，f = 特征数 训练时间复杂度 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 聚类：
90420编辑于 2022-11-11 - 来自专栏数据派THU
8个常见的机器学习算法的计算复杂度总结
计算复杂度又分为两类： 一、时间复杂度 时间复杂度不是测量一个算法或一段代码在某个机器或者条件下运行所花费的时间。 二、空间复杂度 就像时间复杂度是一个函数一样，空间复杂度也是如此。从概念上讲，它与时间复杂度相同，只需将时间替换为空间即可。 线性回归 n= 训练样本数，f = 特征数 训练时间复杂度：O(f²n+f³) 预测时间复杂度：O(f) 运行时空间复杂度：O(f) 2. 逻辑回归 n= 训练样本数，f = 特征数 训练时间复杂度：O(f*n) 预测时间复杂度：O(f) 运行时空间复杂度：O(f) 3. (f*n*log(n)) 预测时间复杂度：O(k*log(n)) 运行时空间复杂度：O(n*f) 8.
57130编辑于 2022-08-29 - 来自专栏C++/Linux
【时间复杂度空间复杂度】
时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3 常见时间复杂度计算举例 3. 空间复杂度 4. 常见复杂度对比 5. 即我们的查找过程 : N/2, N/4, N/8 , …… , 2 , 1。 实例8： // 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); } 实例8可以大约看成二叉树的遍历 ，即每一层的次数为：从高到低1->2->4->8->2*n，这样等比数列求和,求得大约递归了 2^n 次，即时间复杂度为O(2^N)。
2K00编辑于 2023-03-28 - 来自专栏萌新的日常
时间复杂度与空间复杂度
一、时间复杂度 1.概念 即时间复杂度计算的是执行次数 2.大O的渐进表示法 1.用常数1取代时间中的所有加法常数 2.在修改后的运行次数函数中，只保留最高项 3.如果最高项存在而且不是1，则去除与这个项目相乘的常数 N:factorial(N-1)*N; } 假设为3时得递归展开图 可以看出当N为3时 ，一共递归了3次，每次递归函数调用一次 即时间复杂度为O(N) 二、空间复杂度 1.概念 即创建变量的个数 2.用法 void bubblesort(int *a,int n)//冒泡排序 的bubblesort的空间复杂度 { assert(a); for(size_t end=n;end>0;end { swap(&a[i-1],&a[i]); exchange=1; } } if(exchange==0) break; } } 这里的空间复杂度为 ++) { fibary[i]=fibary[i-1]+fibary[i-2]; } return fibary; } 这道题因为malloc动态开辟了n+1个空间 所以空间复杂度为
54221编辑于 2022-11-10 - 来自专栏牛人NR
时间复杂度与空间复杂度
空间复杂度分析 计算机的软硬件都经历了一个比较漫长的演变史，作为为运算提供环境的内存，更是如此，从早些时候的512k,经历了1M，2M，4M…等，发展到现在的8G，甚至16G和32G，所以早期，算法在运行过程中对内存的占用情况也是一个经常需要考虑的问题 java中常见内存占用 基本数据类型内存占用情况： 计算机访问内存的方式都是一次一个字节 一个引用（机器地址）需要8个字节表示： 例如： Date date = new Date(),则date这个变量需要占用 8个字节来表示 创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。 一般内存的使用，如果不够8个字节，都会被自动填充为8字节： java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销， - 1 - i] = arr[i]; } return temp; } 忽略判断条件占用的内存，我们得出的内存占用情况如下： 算法一： 不管传入的数组大小为多少，始终额外申请4+4=8个字节
88120发布于 2020-09-01 - 来自专栏LittlePanger的代码之路
时间复杂度与空间复杂度
时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。 因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。 记作 T(n)= Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。 T(n) 不同，但时间复杂度可能相同。 阶乘阶 旅行商问题 说明：常见的时间复杂度有小到大依次排序，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低 1. 立方阶 O(n^3) 3次n循环 7. k 次方阶 O(n^k) k次n循环 3 空间复杂度 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间
1.1K30发布于 2020-04-14 - 来自专栏SRE运维实践
漫谈时间复杂度空间复杂度
O（N**N）；第二种是空间复杂度为O（1）。 空间复杂度，就是运行一次的过程中，占用的存储空间的大小度量，例如在进行一个list操作的时候，那么空间复杂度为O（1），当在进行修改删除操作的时候，可能需要新建一个新的存储空间来存储新的队列，从而空间复杂度为 空间复杂度和时间复杂度，可以作为选择数据类型的评判标准之一。 对于一种数据结构来说，有各种各样的时间复杂度，对于python的list实现，当你查询一个元素的时候，时间复杂度是O（1），常量时间；但是当你进行加入元素，删除元素的时候，时间复杂度是O（N），对于特例在尾部增加和删除的操作来说 ，时间复杂度又是O（1）。
90830发布于 2019-07-08 - 来自专栏程序猿杂货铺
时间复杂度和空间复杂度
1 时间复杂度 01 时间复杂度定义 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。 算法的时间复杂度，也就是算法的时间量度，基座T（n）=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进算法时间复杂度，简称为时间复杂度。 所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。 那么下面这个循环嵌套，它的时间复杂度是多少呢? 比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。 当不用限定词地使用"复杂度'时，通常都是指时间复杂度。
1.4K60发布于 2019-09-04 时间复杂度和空间复杂度
要比较n2次才行，复杂度O(n2) 总结：稳定的排序方法，时间复杂度O(n^2)，空间复杂度O(1)，当待排序列有序时，效果比较好。 算法的时间复杂度是O(nlogn)，最坏的时间复杂度O(n^2)，空间复杂度O(nlogn) 四.选择排序 ①.直接选择排序 和序列的初始状态无关 总结：时间复杂度O(n^2)，无论最好还是最坏 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。 讨论方法与时间复杂度类似，不再赘述。 （3）渐进时间复杂度评价算法时间性能 主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。 (6) 下面如图是常见的算法的时间复杂度和空间复杂度:
26910编辑于 2025-08-29- 来自专栏韩曙亮的移动开发专栏
【算法】复杂度理论 ( 时间复杂度 )
文章目录 一、复杂度理论 二、时间复杂度 1、P 与 NP 问题 2、O 表示的复杂度情况 3、时间复杂度取值规则 4、时间复杂度对比 一、复杂度理论 ---- 时间复杂度 : 描述一个算法执行的大概效率 使用 蛮力算法 , 编程复杂度很低 , 很容易看懂 , 但是其时间复杂度是 O(m \times n) ; 如果使用 Rabin-Karp 算法 , 时间复杂度是 O(m + n) , 但是编程复杂度很高 , 也是很难理解的 ; 一般 蛮力算法 时间复杂度 很高 , 但是 编程复杂度 和 思维复杂度 很低 , 代码容易理解 ; 如果对 时间复杂度 要求很高 , 如必须达到 O(n) 或 O(n^ 等 ; 2、O 表示的复杂度情况 O 表示算法在 最坏的情况下的时间复杂度 ; 一般情况下 , 算法的时间复杂度都以最坏情况的时间复杂度为准 ; 但是也有特例 , 快速排序的最坏情况下 , 时间复杂度是 O(n^2) , 这个时间复杂度几乎不会遇到 , 一般情况下描述快速排序的时间复杂度时 , 使用 平均时间复杂度 O(n \log n) ; 3、时间复杂度取值规则 只考虑最高次项 : 时间复杂度描述中
1.8K20编辑于 2023-03-29 - 来自专栏程序架道
软件只有两种复杂度：本质复杂度&偶然复杂度
图自网络 我们知道软件设计的本质是持续对抗软件本身产生的复杂度。 题目中的两种复杂度名称，最早来源自哪里呢？ 在《人月神话》这本书中，作者将软件复杂度分为本质复杂度（Essential Complexity）和偶然复杂度（Accidental Complexity）。 这两种复杂度应该怎么理解呢？ 技术而引入的复杂度，为偶然复杂度。 我们继续分别对本质复杂度和偶然复杂度列举两个更详细的案例。 本质复杂度案例：大型电商平台的实时交易系统 图自网络仅示例 考虑一个大型的电商平台，如淘宝或京东，在高峰时段每秒处理数千甚至数万笔交易。 与本质复杂度相比，偶然复杂度更多地是由于技术选择、系统设计和实现过程中的决策所引起的。通过合理的架构设计、模块化和抽象化等方法，可以降低这种偶然复杂度，提高系统的可维护性和可扩展性。
1.6K10编辑于 2023-12-10 - 来自专栏c语言
了解时间复杂度和空间复杂度
在学习数据结构前，我们需要了解时间复杂度和空间复杂度的概念，这能够帮助我们了解数据结构。 算法效率分为时间效率和空间效率 时间复杂度 一个算法的复杂度与其执行的次数成正比。 举例： 冒泡排序的时间复杂度 从这个例子我们知道了，不是一层循环时间复杂度就是N，两层就是N^2要看具体算法实现。 二分法时间复杂度分析： 阶乘递归的时间复杂度 空间复杂度 对临时储存空间占用大小的量度。计算的是变量的个数。 首先来看冒泡排序的时间复杂度 循环走了N次，重复利用的是一个空间。 斐波那契数列的空间复杂度： 阶乘的时间复杂度： 算法题 消失的数字 面试题 17.04. 这种方法的时间复杂度是N*lgN 思路2： 把0到N加起来，再减去各个数字，得到的数字就是消失的数字。这里的时间复杂度是O（N）。如果先累加，时间复杂度是0(N),依次遍历一遍为O(N)。
23810编辑于 2024-05-04 - 来自专栏全栈程序员必看
时间复杂度和空间复杂度详解
大家好，又见面了，我是全栈君 算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 （1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。 记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。 时间频度不同，但时间复杂度可能相同。 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 （3）最坏时间复杂度和平均时间复杂度 最坏情况下的时间复杂度称最坏时间复杂度。 在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 2.空间复杂度 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。
1.7K10编辑于 2022-07-15 - 来自专栏基础知识文章
时间复杂度与空间复杂度总结
时间复杂度： 时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。 当我们面前有多个算法时，我们可以通过计算时间复杂度，判断出哪一个算法在具体执行时花费时间最多和最少。 此类算法的时间复杂度是O(1)。 空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。 ,) 2 { 3 int k=10; 4 if（n==k) 5 return n; 6 else 7 return fun(++n); 8 } 递归实现，调用fun函数，每次都创建1个变量k。 调用n次，空间复杂度O（n*1）=O（n)。 时间复杂度与空间复杂度总结： ?
89520发布于 2020-08-27 - 来自专栏C / C++
【数据结构】详解算法复杂度：时间复杂度和空间复杂度
这就要引出一个概念了，即复杂度。 算法的好与坏要从复杂度上去分析。 我们学习复杂度的重点就放在计算时间复杂度上。 三、复杂度：时间复杂度和空间复杂度 （一）时间复杂度 1、时间复杂度的定义 在计算机科学中，算法的时间复杂度是用一个函数式T(N)来表示的，T(N)可以定量描述算法运行时间。 我们希望时间复杂度变化的慢一点，我们通过优化复杂度来优化代码。 结尾 结语： 本篇文章内容到这里就结束了，本文主要介绍了复杂度的概念，复杂度又分为时间复杂度和空间复杂度，博主相信通过本文列举的一些经典的示例和复杂度算法题的讲解，大家对复杂度已经有了更深刻的认识，
39410编辑于 2025-11-12 - 来自专栏Yui编程知识
解析时间复杂度和空间复杂度
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。而对空间复杂度很是在乎。 所以我们如今已经不早特别需要关注一个程序的空间复杂度。 2.时间复杂度 2.1 时间复杂度的概念 时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量的描述了该算法的运行时间。 练习8 long long Fib(int n) { if(n<3) return 1; return Fib(n-1)+Fib(n-2); } 时间复杂度为O(2^N) 每次的调用都是上一次的两倍 3.空间复杂度 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少Bytes的字节，因为计算这个没什么意义，所以空间复杂度算的变量个数。 空间复杂度的计算规则和时间复杂度类型，也使用大O的渐近表示法。
35110编辑于 2024-10-16 - 来自专栏C/C＋＋、数据结构、算法
DS：时间复杂度和空间复杂度
二、时间复杂度 2.1 时间复杂度的概念 在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 四、常见的复杂度对比 五、时间复杂度和空间复杂度例题 特点：时间一去不复返，但是空间可以重复利用！！ // 计算Func3的时间复杂度？ logN 6.2 效率以及实用性 7、内存、外存、CPU、缓存的一些相关知识 7.1 内存和外存的区别 内存：快、小、8G-16G左右、带电存储 外存：慢、大、500G左右、不带电存储 寄存器是最快的，但是一般只有4-8字节的大小，对于大一点的数据，一般都是加载到缓存中再由cpu进行读取。 缓存命中率：在说明这两个问题之前。我们需要要解一个术语 Cache Line。
52510编辑于 2024-02-17 - 来自专栏前端Up Up！
算法的时间复杂度与空间复杂度
一、说明 时间复杂度和空间复杂度是用来评价算法效率高低的2个标准，身为开发者肯定会经常会听到这2个概念，但它们分别是什么意思呢? 二、时间复杂度的计算 表示方法 我们一般用“大O符号表示法”来表示时间复杂度：T(n) = O(f(n)) n是影响复杂度变化的因子，f(n)是复杂度具体的算法。 三、空间复杂度计算 空间复杂度 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。 四、总结 评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。 可能有的开发者接触时间复杂度和空间复杂度的优化不太多（尤其是客户端），但在服务端的应用是比较广泛的，在巨大并发量的情况下，小部分时间复杂度或空间复杂度上的优化都能带来巨大的性能提升，是非常有必要了解的。
2.2K10发布于 2021-02-28 - 来自专栏python3
算法分类 ,时间复杂度 ,空间复杂度,优
前言: 算法的复杂度分为时间复杂度与空间复杂度,时间复杂度指执行算法需要需要的计算工作量,空间复杂度值执行算法需要的内存量,可能在运行一些小数据的时候,大家体会不到算法的时间与空间带来的体验. if __name__ == '__main__': # alist = [12,34,56,78,90,87,65,43,21] # # alist = [1,2,3,4,5,6,7,8,9 alist[i], alist[min_index] = alist[min_index],alist[i] if __name__ == '__main__': alist = [8,10,15,30,25,90,66,2,999 时间复杂度,空间复杂度 接下来就要来说说时间复杂度与空间复杂度: 时间复杂度就是假如你 泡茶,从开始泡,到你喝完茶,一共用了多长时间,你中间要执行很多步骤,取茶叶,烧水,上厕所,接电话,这些都是要花时间的 , 觉得特别厉害,我就比较low了,只能给大家简单的总结一下我遇到的空间复杂度了, 一般来说,算法的空间复杂度值得是辅助空间,比如:一组数字,时间复杂度O(n),二维数组a[n][m] :那么他的空间复杂度就是
89730发布于 2020-01-19 - 来自专栏学习笔记
——算法的时间复杂度和空间复杂度
所以我们如今已经不需要再特别关注一个算法的空间复杂度。 2.时间复杂度 1.时间复杂度的概念 时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。 实例8: // 计算斐波那契递归Fib的时间复杂度？ 空间复杂度为O(N) 3.常见复杂度对比 一般算法常见的复杂度如下： 4. 注意：本题相对书上原题稍作改动 示例 1： 输入：[3,0,1] 输出：2 示例 2： 输入：[9,6,4,2,3,5,7,0,1] 输出：8 思路 1： 1.冒泡排序 2.遍历，如果当前值+1，不等于下一个数字就是下一个数 对同一个值异或两次，那么结果等于它本身 例如：输入：[9,6,4,2,3,5,7,0,1] 输出：8 我们重新创建一个数组[0.1.2.3.4.5.6.7.8.9]与所求数组[9,6,4,2,3,5,7,0,1
88510编辑于 2024-06-15
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号