复杂度类型 规范符号 核心特征 典型场景 常数空间复杂度 O(1)O(1)O(1) 空间固定，与 nnn 无关 仅定义少量变量 sum/cnt 、简单条件判断 对数空间复杂度 O(logn)O(\log n)O(logn) 空间随 nnn 的对数增长(增长极慢) 二分查找的递归调用栈、平衡二叉树的递归遍历 平方根空间复杂度 O(nO(\sqrt{n}O(n ) 空间随 nnn 的平方根增长(亚线性) 数组分块(存储 n 个块的汇总信息)、根号分治算法 线性空间复杂度 O(n)O(n)O(n) 空间与 nnn 成正比(最常用) 存储 nnn 个元素的数组 / 结构体、简单哈希表
线性对数空间复杂度 O(nlogn)O(n \log n)O(nlogn) 空间随 nlognn \log nnlogn 增长 归并排序的临时数组、分治算法的中间结果缓存 平方空间复杂度 O(n2)O(n^2)O(n2) 空间与 n2n^2n2 成正比(增长较快) 存储 n × n 个元素的二维数组(如邻接矩阵)、暴力 DP 的二维状态表 立方空间复杂度 O(n3)O(n^3)O(n3) 空间与 n3n^3n3 成正比(极少用) 三维 DP 的状态表、三阶矩阵乘法的临时数组 指数空间复杂度 O(2n)O(2^n)O(2n) 空间随 2n2^n2n 爆炸增长(几乎不用)
暴力枚举子集的递归栈(仅理论场景)
