网站后台无法上传图片,在局网站 作风建设,网站建设保密协议书,杨浦建设机械网站文章目录 空间复杂度概念实例 空间复杂度
概念
空间复杂度也是一个数学表达式#xff0c;是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间#xff0c;因为这个也没太大意义#xff0c;所以空间复杂度算的是变量的个数。… 文章目录 空间复杂度概念实例 空间复杂度
概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
注意空间是可以重复利用的
实例
空间复杂度为O1 创建常数个变量 空间复杂度O1
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 end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
}空间复杂度为ON 因为创建出N1个额外的空间 取影响最大的项为N
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;
}空间复杂度为ON 递归算空间复杂度算的是总调用函数个数变量的个数 这里每次开辟1个空间 一共开辟N次
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}常见复杂度对比图
