空间复杂度 #

空间复杂度全称是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

示例分析 #

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
 
  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

分析：

• 第2行：变量 i 是常量阶，与数据规模 n 无关，可忽略
• 第3行：申请了大小为 n 的数组，空间复杂度为 O(n)
• 其他代码没有占用额外空间

结论： 整段代码的空间复杂度为 O(n)

常见空间复杂度 #

• O(1)：常量空间
• O(n)：线性空间
• O(n²)：平方空间

空间复杂度分析比时间复杂度分析简单，掌握这些基础内容即可。