当前位置:   article > 正文

空间复杂度_空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度

基本概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,我们用 S(n) 来定义。

计算方法

1. 空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
  • 1
  • 2
  • 3
  • 4
  • 5

变量 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

2. 空间复杂度 O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

转自:https://zhuanlan.zhihu.com/p/50479555

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/721830
推荐阅读
相关标签
  

闽ICP备14008679号