- 综合排序
- 最热优先
- 最新优先
- 来自专栏后端架构师
2.时间复杂度与空间复杂度
这里就要用到我们今天要讲的内容：时间、空间复杂度分析。只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。 类比一下，空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。 我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。 所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。 空间复杂度 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。 int i = 1; int j = 2; ++i; j++; int m = i + j; 代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
91420发布于 2020-03-24 - 来自专栏热爱编程的证据
数据结构入门（2）时间复杂度与空间复杂度
long long Fib(int N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); } 2 算法的复杂度 算法在编写成可执行程序后，运行时需要耗费时间资源和空间 因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 1 // 计算Func2的时间复杂度？ O（N） 实例2 // 计算Func3的时间复杂度？ 实例2 // 计算Fibonacci的空间复杂度？
28310编辑于 2024-02-11 - 来自专栏Android小知识
空间复杂度
什么是空间复杂度 空间复杂度是指执行算法时所使用的临时变量所占用内存空间的大小，同时间复杂度一样用大写的字母O(数量)来表示。 为什么使用空间复杂度 用于判断算法的优劣（算法在时间复杂度相同的情况下，空间复杂度越小的越好） 常见的空间复杂度种类 常数空间：算法所占用的空间是固定的，与输入输出无关，记为S(n) = O(1)。 线性空间：算法所占用的空间与输入输出成正比，记为S(n) = O(n)。 二维空间：算法所分配的是一个集合长度和宽度都与输入规模成正比的二维数组，记为S(n) = O(n²)。 递归空间：算法使用递归时，内存会分配一个方法调用栈，和递归深度成正比，与线性空间的空间复杂度相同，记为S(n) = O(n)。
57910发布于 2020-02-18 - 来自专栏学习
空间复杂度
一、空间复杂度 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 ，一共创建了三个变量，end，exchange，i，使用了常数个额外空间，所以空间复杂度为 O(1) 注：空间复杂度算的是变量的个数 实例2： // 计算Fibonacci的空间复杂度？ i <= n ; ++i) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; } 动态开辟了N个空间 空间复杂度为O(N) 三、常见复杂度对比 常见的空间复杂度有：O(1) ，O(N)，O(N^2) 总结 尽管现代计算机的存储容量已经很高，使得在大多数情况下，算法的空间复杂度不再是绝对的限制因素
23500编辑于 2024-11-22 - 来自专栏Linux网络：从不懂到不会
空间复杂度
1.1空间复杂度概念 空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。 空间复杂度不是程序占用了多少的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数 空间复杂度计算规则基本跟时间复杂度类似，也是用大O渐进表示法 注意：函数运行时所需要的栈空间 ，但是变量的个数是常数，根据大O渐进表示法，就可以得出空间复杂度了。 示例二 int func2(int N) { if (N == 0) { return; } return func2(N - 1) * N; } 空间复杂度：O(N) 这个例子是一个递归 ，而递归的空间复杂度为=单次递归的空间复杂度✖递归次数，在这个例子中递归次数我们知道为N，而在这个函数中并没有创建新的变量，都是对形参N做出改变再传回去，故单次递归的空间复杂度就为1，根据公式就可以计算出空间复杂度
8910编辑于 2026-01-12 - 来自专栏来自csdn的博客
空间复杂度
; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {1, 2, 这些基本数据类型的空间复杂度是常量级别的，即O(1)。无论程序如何运行，它们占用的内存空间都不会改变。 2. 数组与空间复杂度 数组是C语言中一种重要的数据结构，它由多个相同类型的数据组成。 因此，指针的空间复杂度是O(1)，而它指向的内容的空间复杂度是O(n)。 5. 函数与空间复杂度 函数的空间复杂度主要取决于函数中定义的局部变量和函数调用栈的大小。 *p = (int *)malloc(10 * sizeof(int)); if (p == NULL) { // 处理内存分配失败的情况 } // 使用p free(p); // 释放内存 2. 例如： union { int a; float b; } u; 在这个联合体中，a和b共享同一块内存空间。 2.
21310编辑于 2025-04-15 - 来自专栏前端学习文档
空间复杂度
什么是空间复杂度？ 算法在运行过程中临时占用存储空间大小的度量，和时间复杂度表示一样，一个函数，用大 O 表示，例如 O (1)、O (n)、O (^2 )... javascript let i = 0 i += 1 O(n) 这段代码主要声明了变量 list 和变量 i，但是变量 list 的元素个数会受 n 的影响，所以时间复杂度是 O (n) 而变量 i 的时间复杂度 O (1) 两个相加时可忽略不计。 javascript const list = [] for (let i = 0; i < n; i++) { list.push(i) } O(n ^ 2) 我们平时用的栅格布局（一行里面包括多少列 这段代码主要声明了 matrix 变量，是一个数组，因为是嵌套循环，所以数组的元素个数为 n * n 为 n ^ 2。
24500编辑于 2023-06-08 - 来自专栏C++/Linux
【时间复杂度空间复杂度】
因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度，所以我们如今已经不需要再特别关注一个算法的空间复杂度。 1.3 算法复杂度在校招中的考察 2. 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 实例2： // 计算Fibonacci的空间复杂度？ ; } 实例2在堆空间开辟了n+1个空间，由于空间是复用的，使用次数不会改变空间复杂度的大小，因此空间复杂度为O(N)。
2K00编辑于 2023-03-28 - 来自专栏程序猿杂货铺
时间复杂度和空间复杂度
2 空间复杂度 01 定义 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。 比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。 (2) 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。 一个算法所需的存储空间用f(n)表示。 若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。 通常， 我们都使用"时间复杂度"来指运行时间的需求，使用"空间复杂度"指空间需求。 03 空间复杂度常见计算规则 01 加法规则 T(n,m) = T1(n) + T2(m) = O(max{f(n), g(m)}) 02 乘法规则 T(n,m) = T1(n) * T2(m) =
1.4K60发布于 2019-09-04 - 来自专栏萌新的日常
时间复杂度与空间复杂度
一、时间复杂度 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; } } 这里的空间复杂度为 所以空间复杂度为o(n)
54221编辑于 2022-11-10 - 来自专栏牛人NR
时间复杂度与空间复杂度
2次 如果用大O记法表示上述每个算法的时间复杂度，应该如何表示呢？ 空间复杂度分析 计算机的软硬件都经历了一个比较漫长的演变史，作为为运算提供环境的内存，更是如此，从早些时候的512k,经历了1M，2M，4M…等，发展到现在的8G，甚至16G和32G，所以早期，算法在运行过程中对内存的占用情况也是一个经常需要考虑的问题 我么可以用算法的空间复杂度来描述算法对内存的占用。 算法的空间复杂度计算公式记作：S(n)=O(f(n)),其中n为输入规模，f(n)为语句关于n所占存储空间的函数。 案例： 对指定的数组元素进行反转，并返回反转的内容。 O(1),算法二的空间复杂度为O(n),所以从空间占用的角度讲，算法一要优于算法二。
88320发布于 2020-09-01 - 来自专栏LittlePanger的代码之路
时间复杂度与空间复杂度
主要还是从算法所占用的「时间」和「空间」两个维度去考量。 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。 因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同，但时间复杂度相同，都为 O(n²)。 立方阶 O(n^3) 3次n循环 7. k 次方阶 O(n^k) k次n循环 3 空间复杂度 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
1.1K30发布于 2020-04-14 - 来自专栏SRE运维实践
漫谈时间复杂度空间复杂度
Example: Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1] O（N**N）；第二种是空间复杂度为O（1）。 空间复杂度，就是运行一次的过程中，占用的存储空间的大小度量，例如在进行一个list操作的时候，那么空间复杂度为O（1），当在进行修改删除操作的时候，可能需要新建一个新的存储空间来存储新的队列，从而空间复杂度为 空间复杂度和时间复杂度，可以作为选择数据类型的评判标准之一。 对于一种数据结构来说，有各种各样的时间复杂度，对于python的list实现，当你查询一个元素的时候，时间复杂度是O（1），常量时间；但是当你进行加入元素，删除元素的时候，时间复杂度是O（N），对于特例在尾部增加和删除的操作来说
90830发布于 2019-07-08 - 来自专栏Java
【数据结构与算法】2.时间复杂度和空间复杂度
时间和空间复杂度 1. 算法效率 算法效率分为两种：第一种是时间效率；第二种是空间效率。时间效率又称为时间复杂度，而空间效率又称为空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度衡量一个算法所需要的额外空间。 在计算机的发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。 所以我们如今不需要特别关注空间复杂度。 2. 时间复杂度 2.1 时间复杂度的概念 时间复杂度的定义：算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。 空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度为 O(1) */ 【例子2】： // 计算fibonacci的空间复杂度？
26710编辑于 2024-05-07 时间复杂度和空间复杂度
要比较n2次才行，复杂度O(n2) 总结：稳定的排序方法，时间复杂度O(n^2)，空间复杂度O(1)，当待排序列有序时，效果比较好。 算法的时间复杂度是O(nlogn)，最坏的时间复杂度O(n^2)，空间复杂度O(nlogn) 四.选择排序 ①.直接选择排序 和序列的初始状态无关 总结：时间复杂度O(n^2)，无论最好还是最坏 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另 外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。 （5） 如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当 一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与
26910编辑于 2025-08-29- 来自专栏c语言
了解时间复杂度和空间复杂度
在学习数据结构前，我们需要了解时间复杂度和空间复杂度的概念，这能够帮助我们了解数据结构。 算法效率分为时间效率和空间效率 时间复杂度 一个算法的复杂度与其执行的次数成正比。 举例： 冒泡排序的时间复杂度 从这个例子我们知道了，不是一层循环时间复杂度就是N，两层就是N^2要看具体算法实现。 二分法时间复杂度分析： 阶乘递归的时间复杂度 空间复杂度 对临时储存空间占用大小的量度。计算的是变量的个数。 首先来看冒泡排序的时间复杂度 循环走了N次，重复利用的是一个空间。 斐波那契数列的空间复杂度： 阶乘的时间复杂度： 算法题 消失的数字 面试题 17.04. 这种方法的时间复杂度是N*lgN 思路2： 把0到N加起来，再减去各个数字，得到的数字就是消失的数字。这里的时间复杂度是O（N）。如果先累加，时间复杂度是0(N),依次遍历一遍为O(N)。
23810编辑于 2024-05-04 - 来自专栏全栈程序员必看
时间复杂度和空间复杂度详解
如：T(n)=n 2+3n+4与T(n)=4n 2+2n+1它们的频度不同，但时间复杂度相同，都为O(n 2)。 指数阶0(2 n)，显然，时间复杂度为指数阶0(2 n)的算法效率极低，当n值稍大时就无法应用。 （5）时间复杂度评价性能 有两个算法A 1和A 2求解同一问题，时间复杂度分别是T 1(n)=100n 2，T 2(n)=5n 3。 2.空间复杂度 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。 这部分属于静态空间。 （2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。 一个算法所需的存储空间用f(n)表示。
1.7K10编辑于 2022-07-15 - 来自专栏基础知识文章
时间复杂度与空间复杂度总结
常见的时间复杂度有： 常数阶O(1), 对数阶O(log2 n), 线性阶O(n), 线性对数阶O(n log2 n), 平方阶O(n^2)， 立方阶O(n^3) k次方阶O(n^K), 空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。 计算方法： ①忽略常数，用O(1)表示 ②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间 ③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程 空间复杂度的计算： 1 int a; 2 int b; 3 int c; 4 printf("%d %d %d \n",a,b,c); 它的空间复杂度O（n）=O（1）； 1 int fun(int n 调用n次，空间复杂度O（n*1）=O（n)。 时间复杂度与空间复杂度总结： ?
89620发布于 2020-08-27 - 来自专栏Yui编程知识
解析时间复杂度和空间复杂度
1.2 算法的复杂度 算法再编写成可执行程序后，运行时需要耗费的时间和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。而对空间复杂度很是在乎。 所以我们如今已经不早特别需要关注一个程序的空间复杂度。 2.时间复杂度 2.1 时间复杂度的概念 时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量的描述了该算法的运行时间。 3.空间复杂度 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少Bytes的字节，因为计算这个没什么意义，所以空间复杂度算的变量个数。 } 空间复杂度度：O(N) 递归调用了N个堆栈，每个堆栈使用了常数个的空间 4.常见复杂度对比 完
35110编辑于 2024-10-16 - 来自专栏C/C＋＋、数据结构、算法
DS：时间复杂度和空间复杂度
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 时间复杂度是O(N^2) // 计算斐波那契递归Fib的时间复杂度和空间复杂度 long long Fib(size_t N) { if(N < 3) return 1; return Fib 但是不影响大O阶表示时间复杂度O（N^2） 时间一去不复返，但是空间是可以重复利用的，新销毁的函数栈帧释放后可以马上被新的函数栈帧替代，重复利用的空间，所以空间复杂度是O（N） // 计算BubbleSort O（N^2）,虽然每次循环都有存在创建i和end变量，但其实使用的都是一块空间，空间一直在被重复利用，所以空间复杂度O（1） 分析以下函数的空间复杂度（ ） int** fun(int n) { ,...n列，所以是n(n + 1)/2个元素空间，空间复杂度为O(n^2) 六、二分查找法 二分查找法的使用前提： 1、数据存储在数组中 2、数组中的元素必须有序 一次折半的过程： 1、确定被查找的范围
52610编辑于 2024-02-17
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号