小工具知识网

当前位置: 首页 > 行业知识 > 空间复杂度(数据结构)

行业知识

空间复杂度(数据结构)

2026-11-20 03:52:26 来源:互联网转载

概念:

�� 空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

  注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

实例1:

// 计算BubbleSort的空间复杂度?void BubbleSort(int* a, int n){ assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i  a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; }}

实例2:

// 计算Fibonacci的空间复杂度?// 返回斐波那契数列的前n项long long* Fibonacci(size_t n){ if(n==0) return NULL;  long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i 

上一篇:HTML二级菜单纵向打印设置详解

下一篇:独立CDN下载链接全解析,轻松获取下载链接的方法