2.4 空间复杂度¶
空间复杂度(space complexity)用于衡量算法占用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度非常类似,只需将“运行时间”替换为“占用内存空间”。
2.4.1 算法相关空间¶
算法在运行过程中使用的内存空间主要包括以下几种。
- 输入空间:用于存储算法的输入数据。
- 暂存空间:用于存储算法在运行过程中的变量、对象、函数上下文等数据。
- 输出空间:用于存储算法的输出数据。
一般情况下,空间复杂度的统计范围是“暂存空间”加上“输出空间”。
暂存空间可以进一步划分为三个部分。
- 暂存数据:用于保存算法运行过程中的各种常量、变量、对象等。
- 栈帧空间:用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧,函数返回后,栈帧空间会被释放。
- 指令空间:用于保存编译后的程序指令,在实际统计中通常忽略不计。
在分析一段程序的空间复杂度时,我们通常统计暂存数据、栈帧空间和输出数据三部分,如图 2-15 所示。
图 2-15 算法使用的相关空间
图解 2-15:空间复杂度通常统计哪些空间
图将算法运行涉及的空间分为三类,并用大括号标出通常的统计范围。
从左到右,三个方框由向右箭头相连,表示接收输入、暂存计算、产生输出的处理流程。左侧“输入空间”下写“输入数据”;中间“暂存空间”下依次列“暂存数据、栈帧空间、指令空间”;右侧“输出空间”下写“输出数据”。
上方大括号只覆盖暂存空间与输出空间,标注“通常情况下空间复杂度的统计范围”,不包括输入空间。结合正文的统计约定,还通常忽略暂存空间中的指令空间,因此重点计入暂存数据、栈帧空间和输出数据。
相关代码如下:
class Node:
"""类"""
def __init__(self, x: int):
self.val: int = x # 节点值
self.next: Node | None = None # 指向下一节点的引用
def function() -> int:
"""函数"""
# 执行某些操作...
return 0
def algorithm(n) -> int: # 输入数据
A = 0 # 暂存数据(常量,一般用大写字母表示)
b = 0 # 暂存数据(变量)
node = Node(0) # 暂存数据(对象)
c = function() # 栈帧空间(调用函数)
return A + b + c # 输出数据
/* 结构体 */
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(nullptr) {}
};
/* 函数 */
int func() {
// 执行某些操作...
return 0;
}
int algorithm(int n) { // 输入数据
const int a = 0; // 暂存数据(常量)
int b = 0; // 暂存数据(变量)
Node* node = new Node(0); // 暂存数据(对象)
int c = func(); // 栈帧空间(调用函数)
return a + b + c; // 输出数据
}
/* 类 */
class Node {
int val;
Node next;
Node(int x) { val = x; }
}
/* 函数 */
int function() {
// 执行某些操作...
return 0;
}
int algorithm(int n) { // 输入数据
final int a = 0; // 暂存数据(常量)
int b = 0; // 暂存数据(变量)
Node node = new Node(0); // 暂存数据(对象)
int c = function(); // 栈帧空间(调用函数)
return a + b + c; // 输出数据
}
/* 结构体 */
type node struct {
val int
next *node
}
/* 创建 node 结构体 */
func newNode(val int) *node {
return &node{val: val}
}
/* 函数 */
func function() int {
// 执行某些操作...
return 0
}
func algorithm(n int) int { // 输入数据
const a = 0 // 暂存数据(常量)
b := 0 // 暂存数据(变量)
newNode(0) // 暂存数据(对象)
c := function() // 栈帧空间(调用函数)
return a + b + c // 输出数据
}
/* 类 */
class Node {
var val: Int
var next: Node?
init(x: Int) {
val = x
}
}
/* 函数 */
func function() -> Int {
// 执行某些操作...
return 0
}
func algorithm(n: Int) -> Int { // 输入数据
let a = 0 // 暂存数据(常量)
var b = 0 // 暂存数据(变量)
let node = Node(x: 0) // 暂存数据(对象)
let c = function() // 栈帧空间(调用函数)
return a + b + c // 输出数据
}
/* 类 */
class Node {
val;
next;
constructor(val) {
this.val = val === undefined ? 0 : val; // 节点值
this.next = null; // 指向下一节点的引用
}
}
/* 函数 */
function constFunc() {
// 执行某些操作
return 0;
}
function algorithm(n) { // 输入数据
const a = 0; // 暂存数据(常量)
let b = 0; // 暂存数据(变量)
const node = new Node(0); // 暂存数据(对象)
const c = constFunc(); // 栈帧空间(调用函数)
return a + b + c; // 输出数据
}
/* 类 */
class Node {
val: number;
next: Node | null;
constructor(val?: number) {
this.val = val === undefined ? 0 : val; // 节点值
this.next = null; // 指向下一节点的引用
}
}
/* 函数 */
function constFunc(): number {
// 执行某些操作
return 0;
}
function algorithm(n: number): number { // 输入数据
const a = 0; // 暂存数据(常量)
let b = 0; // 暂存数据(变量)
const node = new Node(0); // 暂存数据(对象)
const c = constFunc(); // 栈帧空间(调用函数)
return a + b + c; // 输出数据
}
/* 类 */
class Node {
int val;
Node? next;
Node(this.val, [this.next]);
}
/* 函数 */
int function() {
// 执行某些操作...
return 0;
}
int algorithm(int n) { // 输入数据
const int a = 0; // 暂存数据(常量)
int b = 0; // 暂存数据(变量)
Node node = Node(0); // 暂存数据(对象)
int c = function(); // 栈帧空间(调用函数)
return a + b + c; // 输出数据
}
use std::rc::Rc;
use std::cell::RefCell;
/* 结构体 */
struct Node {
val: i32,
next: Option<Rc<RefCell<Node>>>,
}
/* 创建 Node 结构体 */
impl Node {
fn new(val: i32) -> Self {
Self { val: val, next: None }
}
}
/* 函数 */
fn function() -> i32 {
// 执行某些操作...
return 0;
}
fn algorithm(n: i32) -> i32 { // 输入数据
const a: i32 = 0; // 暂存数据(常量)
let mut b = 0; // 暂存数据(变量)
let node = Node::new(0); // 暂存数据(对象)
let c = function(); // 栈帧空间(调用函数)
return a + b + c; // 输出数据
}
### 类 ###
class Node
attr_accessor :val # 节点值
attr_accessor :next # 指向下一节点的引用
def initialize(x)
@val = x
end
end
### 函数 ###
def function
# 执行某些操作...
0
end
### 算法 ###
def algorithm(n) # 输入数据
a = 0 # 暂存数据(常量)
b = 0 # 暂存数据(变量)
node = Node.new(0) # 暂存数据(对象)
c = function # 栈帧空间(调用函数)
a + b + c # 输出数据
end
2.4.2 推算方法¶
空间复杂度的推算方法与时间复杂度大致相同,只需将统计对象从“操作数量”转为“使用空间大小”。
而与时间复杂度不同的是,我们通常只关注最差空间复杂度。这是因为内存空间是一项硬性要求,我们必须确保在所有输入数据下都有足够的内存空间预留。
观察以下代码,最差空间复杂度中的“最差”有两层含义。
- 以最差输入数据为准:当 \(n < 10\) 时,空间复杂度为 \(O(1)\) ;但当 \(n > 10\) 时,初始化的数组
nums占用 \(O(n)\) 空间,因此最差空间复杂度为 \(O(n)\) 。 - 以算法运行中的峰值内存为准:例如,程序在执行最后一行之前,占用 \(O(1)\) 空间;当初始化数组
nums时,程序占用 \(O(n)\) 空间,因此最差空间复杂度为 \(O(n)\) 。
在递归函数中,需要注意统计栈帧空间。观察以下代码:
函数 loop() 和 recur() 的时间复杂度都为 \(O(n)\) ,但空间复杂度不同。
- 函数
loop()在循环中调用了 \(n\) 次function(),每轮中的function()都返回并释放了栈帧空间,因此空间复杂度仍为 \(O(1)\) 。 - 递归函数
recur()在运行过程中会同时存在 \(n\) 个未返回的recur(),从而占用 \(O(n)\) 的栈帧空间。
2.4.3 常见类型¶
设输入数据大小为 \(n\) ,图 2-16 展示了常见的空间复杂度类型(从低到高排列)。
图 2-16 常见的空间复杂度类型
图解 2-16:常见空间复杂度的增长趋势
比较五种空间复杂度随输入规模增大的增长趋势。
横轴是输入数据大小 n,刻度为 1 至 14;纵轴是内存空间大小,没有可见的容量数值刻度。这是增长趋势示意图,不是实际字节数或未缩放函数值的比较。
下表按图右端曲线从低到高排列,对应右侧向上箭头“从低至高、从优至差”。
| 复杂度(右端从低到高) | 图中形态 |
|---|---|
| 常数阶 O(1) | 绿色水平线,紧贴横轴上方,不随 n 增长 |
| 对数阶 O(log n) | 青色曲线缓慢上升,斜率逐渐变缓 |
| 线性阶 O(n) | 蓝色直线,以固定斜率上升 |
| 平方阶 O(n²) | 橙色曲线向上弯曲,斜率越来越陡 |
| 指数阶 O(2ⁿ) | 红色曲线在刻度 1 至 8 附近贴近底部,后段急剧上升 |
小规模区间里部分示意曲线相交,例如刻度 2 至 6 之间对数曲线略高于线性直线。图要表达的是 n 足够大时的增长趋势:常数不变,对数增长缓慢,指数最终增长最快;不能用前段交点推算具体输入下的内存用量。
1. 常数阶 \(O(1)\)¶
常数阶常见于数量与输入数据大小 \(n\) 无关的常量、变量、对象。
需要注意的是,在循环中初始化变量或调用函数而占用的内存,在进入下一循环后就会被释放,因此不会累积占用空间,空间复杂度仍为 \(O(1)\) :
/* 函数 */
int func() {
// 执行某些操作
return 0;
}
/* 常数阶 */
void constant(int n) {
// 常量、变量、对象占用 O(1) 空间
const int a = 0;
int b = 0;
vector<int> nums(10000);
ListNode node(0);
// 循环中的变量占用 O(1) 空间
for (int i = 0; i < n; i++) {
int c = 0;
}
// 循环中的函数占用 O(1) 空间
for (int i = 0; i < n; i++) {
func();
}
}
/* 函数 */
int function() {
// 执行某些操作
return 0;
}
/* 常数阶 */
void constant(int n) {
// 常量、变量、对象占用 O(1) 空间
final int a = 0;
int b = 0;
int[] nums = new int[10000];
ListNode node = new ListNode(0);
// 循环中的变量占用 O(1) 空间
for (int i = 0; i < n; i++) {
int c = 0;
}
// 循环中的函数占用 O(1) 空间
for (int i = 0; i < n; i++) {
function();
}
}
/* 函数 */
int Function() {
// 执行某些操作
return 0;
}
/* 常数阶 */
void Constant(int n) {
// 常量、变量、对象占用 O(1) 空间
int a = 0;
int b = 0;
int[] nums = new int[10000];
ListNode node = new(0);
// 循环中的变量占用 O(1) 空间
for (int i = 0; i < n; i++) {
int c = 0;
}
// 循环中的函数占用 O(1) 空间
for (int i = 0; i < n; i++) {
Function();
}
}
/* 函数 */
func function() int {
// 执行某些操作...
return 0
}
/* 常数阶 */
func spaceConstant(n int) {
// 常量、变量、对象占用 O(1) 空间
const a = 0
b := 0
nums := make([]int, 10000)
node := newNode(0)
// 循环中的变量占用 O(1) 空间
var c int
for i := 0; i < n; i++ {
c = 0
}
// 循环中的函数占用 O(1) 空间
for i := 0; i < n; i++ {
function()
}
b += 0
c += 0
nums[0] = 0
node.val = 0
}
/* 函数 */
@discardableResult
func function() -> Int {
// 执行某些操作
return 0
}
/* 常数阶 */
func constant(n: Int) {
// 常量、变量、对象占用 O(1) 空间
let a = 0
var b = 0
let nums = Array(repeating: 0, count: 10000)
let node = ListNode(x: 0)
// 循环中的变量占用 O(1) 空间
for _ in 0 ..< n {
let c = 0
}
// 循环中的函数占用 O(1) 空间
for _ in 0 ..< n {
function()
}
}
/* 函数 */
function constFunc() {
// 执行某些操作
return 0;
}
/* 常数阶 */
function constant(n) {
// 常量、变量、对象占用 O(1) 空间
const a = 0;
const b = 0;
const nums = new Array(10000);
const node = new ListNode(0);
// 循环中的变量占用 O(1) 空间
for (let i = 0; i < n; i++) {
const c = 0;
}
// 循环中的函数占用 O(1) 空间
for (let i = 0; i < n; i++) {
constFunc();
}
}
/* 函数 */
function constFunc(): number {
// 执行某些操作
return 0;
}
/* 常数阶 */
function constant(n: number): void {
// 常量、变量、对象占用 O(1) 空间
const a = 0;
const b = 0;
const nums = new Array(10000);
const node = new ListNode(0);
// 循环中的变量占用 O(1) 空间
for (let i = 0; i < n; i++) {
const c = 0;
}
// 循环中的函数占用 O(1) 空间
for (let i = 0; i < n; i++) {
constFunc();
}
}
/* 函数 */
int function() {
// 执行某些操作
return 0;
}
/* 常数阶 */
void constant(int n) {
// 常量、变量、对象占用 O(1) 空间
final int a = 0;
int b = 0;
List<int> nums = List.filled(10000, 0);
ListNode node = ListNode(0);
// 循环中的变量占用 O(1) 空间
for (var i = 0; i < n; i++) {
int c = 0;
}
// 循环中的函数占用 O(1) 空间
for (var i = 0; i < n; i++) {
function();
}
}
/* 函数 */
fn function() -> i32 {
// 执行某些操作
return 0;
}
/* 常数阶 */
#[allow(unused)]
fn constant(n: i32) {
// 常量、变量、对象占用 O(1) 空间
const A: i32 = 0;
let b = 0;
let nums = vec![0; 10000];
let node = ListNode::new(0);
// 循环中的变量占用 O(1) 空间
for i in 0..n {
let c = 0;
}
// 循环中的函数占用 O(1) 空间
for i in 0..n {
function();
}
}
/* 函数 */
int func() {
// 执行某些操作
return 0;
}
/* 常数阶 */
void constant(int n) {
// 常量、变量、对象占用 O(1) 空间
const int a = 0;
int b = 0;
int nums[1000];
ListNode *node = newListNode(0);
free(node);
// 循环中的变量占用 O(1) 空间
for (int i = 0; i < n; i++) {
int c = 0;
}
// 循环中的函数占用 O(1) 空间
for (int i = 0; i < n; i++) {
func();
}
}
/* 函数 */
fun function(): Int {
// 执行某些操作
return 0
}
/* 常数阶 */
fun constant(n: Int) {
// 常量、变量、对象占用 O(1) 空间
val a = 0
var b = 0
val nums = Array(10000) { 0 }
val node = ListNode(0)
// 循环中的变量占用 O(1) 空间
for (i in 0..<n) {
val c = 0
}
// 循环中的函数占用 O(1) 空间
for (i in 0..<n) {
function()
}
}
可视化运行
2. 线性阶 \(O(n)\)¶
线性阶常见于元素数量与 \(n\) 成正比的数组、链表、栈、队列等:
/* 线性阶 */
void linear(int n) {
// 长度为 n 的数组占用 O(n) 空间
vector<int> nums(n);
// 长度为 n 的列表占用 O(n) 空间
vector<ListNode> nodes;
for (int i = 0; i < n; i++) {
nodes.push_back(ListNode(i));
}
// 长度为 n 的哈希表占用 O(n) 空间
unordered_map<int, string> map;
for (int i = 0; i < n; i++) {
map[i] = to_string(i);
}
}
/* 线性阶 */
void linear(int n) {
// 长度为 n 的数组占用 O(n) 空间
int[] nums = new int[n];
// 长度为 n 的列表占用 O(n) 空间
List<ListNode> nodes = new ArrayList<>();
for (int i = 0; i < n; i++) {
nodes.add(new ListNode(i));
}
// 长度为 n 的哈希表占用 O(n) 空间
Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(i, String.valueOf(i));
}
}
/* 线性阶 */
void Linear(int n) {
// 长度为 n 的数组占用 O(n) 空间
int[] nums = new int[n];
// 长度为 n 的列表占用 O(n) 空间
List<ListNode> nodes = [];
for (int i = 0; i < n; i++) {
nodes.Add(new ListNode(i));
}
// 长度为 n 的哈希表占用 O(n) 空间
Dictionary<int, string> map = [];
for (int i = 0; i < n; i++) {
map.Add(i, i.ToString());
}
}
/* 线性阶 */
func spaceLinear(n int) {
// 长度为 n 的数组占用 O(n) 空间
_ = make([]int, n)
// 长度为 n 的列表占用 O(n) 空间
var nodes []*node
for i := 0; i < n; i++ {
nodes = append(nodes, newNode(i))
}
// 长度为 n 的哈希表占用 O(n) 空间
m := make(map[int]string, n)
for i := 0; i < n; i++ {
m[i] = strconv.Itoa(i)
}
}
/* 线性阶 */
function linear(n) {
// 长度为 n 的数组占用 O(n) 空间
const nums = new Array(n);
// 长度为 n 的列表占用 O(n) 空间
const nodes = [];
for (let i = 0; i < n; i++) {
nodes.push(new ListNode(i));
}
// 长度为 n 的哈希表占用 O(n) 空间
const map = new Map();
for (let i = 0; i < n; i++) {
map.set(i, i.toString());
}
}
/* 线性阶 */
function linear(n: number): void {
// 长度为 n 的数组占用 O(n) 空间
const nums = new Array(n);
// 长度为 n 的列表占用 O(n) 空间
const nodes: ListNode[] = [];
for (let i = 0; i < n; i++) {
nodes.push(new ListNode(i));
}
// 长度为 n 的哈希表占用 O(n) 空间
const map = new Map();
for (let i = 0; i < n; i++) {
map.set(i, i.toString());
}
}
/* 线性阶 */
void linear(int n) {
// 长度为 n 的数组占用 O(n) 空间
List<int> nums = List.filled(n, 0);
// 长度为 n 的列表占用 O(n) 空间
List<ListNode> nodes = [];
for (var i = 0; i < n; i++) {
nodes.add(ListNode(i));
}
// 长度为 n 的哈希表占用 O(n) 空间
Map<int, String> map = HashMap();
for (var i = 0; i < n; i++) {
map.putIfAbsent(i, () => i.toString());
}
}
/* 线性阶 */
#[allow(unused)]
fn linear(n: i32) {
// 长度为 n 的数组占用 O(n) 空间
let mut nums = vec![0; n as usize];
// 长度为 n 的列表占用 O(n) 空间
let mut nodes = Vec::new();
for i in 0..n {
nodes.push(ListNode::new(i))
}
// 长度为 n 的哈希表占用 O(n) 空间
let mut map = HashMap::new();
for i in 0..n {
map.insert(i, i.to_string());
}
}
/* 哈希表 */
typedef struct {
int key;
int val;
UT_hash_handle hh; // 基于 uthash.h 实现
} HashTable;
/* 线性阶 */
void linear(int n) {
// 长度为 n 的数组占用 O(n) 空间
int *nums = malloc(sizeof(int) * n);
free(nums);
// 长度为 n 的列表占用 O(n) 空间
ListNode **nodes = malloc(sizeof(ListNode *) * n);
for (int i = 0; i < n; i++) {
nodes[i] = newListNode(i);
}
// 内存释放
for (int i = 0; i < n; i++) {
free(nodes[i]);
}
free(nodes);
// 长度为 n 的哈希表占用 O(n) 空间
HashTable *h = NULL;
for (int i = 0; i < n; i++) {
HashTable *tmp = malloc(sizeof(HashTable));
tmp->key = i;
tmp->val = i;
HASH_ADD_INT(h, key, tmp);
}
// 内存释放
HashTable *curr, *tmp;
HASH_ITER(hh, h, curr, tmp) {
HASH_DEL(h, curr);
free(curr);
}
}
/* 线性阶 */
fun linear(n: Int) {
// 长度为 n 的数组占用 O(n) 空间
val nums = Array(n) { 0 }
// 长度为 n 的列表占用 O(n) 空间
val nodes = mutableListOf<ListNode>()
for (i in 0..<n) {
nodes.add(ListNode(i))
}
// 长度为 n 的哈希表占用 O(n) 空间
val map = mutableMapOf<Int, String>()
for (i in 0..<n) {
map[i] = i.toString()
}
}
可视化运行
如图 2-17 所示,此函数的递归深度为 \(n\) ,即同时存在 \(n\) 个未返回的 linear_recur() 函数,使用 \(O(n)\) 大小的栈帧空间:
可视化运行
图 2-17 递归函数产生的线性阶空间复杂度
图解 2-17:递归调用的栈空间
空间取决于同时未返回的调用数,逐层递归会积累栈帧。
n 为正整数,以下按未做尾调用优化的执行过程计数。
左列“向下‘递’”从 linear_recur(n) 逐层减 1,直到基本情况 linear_recur(1),大括号标注“递归深度 n”。外层等待内层返回,因此最深处有 n 个栈帧同时存在;随后沿右列“向上‘归’”逐层返回,每返回一层才释放该层栈帧。图右列写作 return 0;现版 Python 用裸 return,实际返回 None,这一差异不影响栈空间计数。
每层占常数局部空间,最深时同时存在 n 层,峰值栈空间为 O(n);之后逐层释放不改变已经达到的峰值。
3. 平方阶 \(O(n^2)\)¶
平方阶常见于矩阵和图,元素数量与 \(n\) 成平方关系:
/* 平方阶 */
void quadratic(int n) {
// 矩阵占用 O(n^2) 空间
int[][] numMatrix = new int[n][n];
// 二维列表占用 O(n^2) 空间
List<List<Integer>> numList = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> tmp = new ArrayList<>();
for (int j = 0; j < n; j++) {
tmp.add(0);
}
numList.add(tmp);
}
}
/* 平方阶 */
function quadratic(n: number): void {
// 矩阵占用 O(n^2) 空间
const numMatrix = Array(n)
.fill(null)
.map(() => Array(n).fill(null));
// 二维列表占用 O(n^2) 空间
const numList = [];
for (let i = 0; i < n; i++) {
const tmp = [];
for (let j = 0; j < n; j++) {
tmp.push(0);
}
numList.push(tmp);
}
}
/* 平方阶 */
void quadratic(int n) {
// 矩阵占用 O(n^2) 空间
List<List<int>> numMatrix = List.generate(n, (_) => List.filled(n, 0));
// 二维列表占用 O(n^2) 空间
List<List<int>> numList = [];
for (var i = 0; i < n; i++) {
List<int> tmp = [];
for (int j = 0; j < n; j++) {
tmp.add(0);
}
numList.add(tmp);
}
}
/* 平方阶 */
void quadratic(int n) {
// 二维列表占用 O(n^2) 空间
int **numMatrix = malloc(sizeof(int *) * n);
for (int i = 0; i < n; i++) {
int *tmp = malloc(sizeof(int) * n);
for (int j = 0; j < n; j++) {
tmp[j] = 0;
}
numMatrix[i] = tmp;
}
// 内存释放
for (int i = 0; i < n; i++) {
free(numMatrix[i]);
}
free(numMatrix);
}
可视化运行
如图 2-18 所示,该函数的递归深度为 \(n\) ,在每个递归函数中都初始化了一个数组,长度分别为 \(n\)、\(n-1\)、\(\dots\)、\(2\)、\(1\) ,平均长度为 \(n / 2\) ,因此总体占用 \(O(n^2)\) 空间:
可视化运行
图 2-18 递归函数产生的平方阶空间复杂度
图解 2-18:递归各层保留数组形成平方空间
每层递归还保留一个局部数组,峰值空间需要把所有未返回层的数组长度相加。
n 为正整数。每次 quadratic_recur(k) 在 k > 0 时创建长度为 k 的 nums,再调用参数 k−1。图省略了不分配数组的最终调用 quadratic_recur(0),将终止与返回简化画在参数 1 这一行;代码实际在参数 0 时直接返回。
图从左到右是“数组 nums 长度”“向下‘递’”“向上‘归’”三列,同行长度与调用用线相连。大括号标“递归深度 n”,覆盖分配数组的 n 层;中间调用以省略号代替。参数 1 那一行用“触发递归终止条件”箭头转入右列,各层 return 0 由向上箭头相连。
| 调用 | nums 长度 |
|---|---|
| quadratic_recur(n) | n |
| quadratic_recur(n−1) | n−1 |
| 中间调用 | 省略 |
| quadratic_recur(2) | 2 |
| quadratic_recur(1) | 1 |
上层等待下层返回时,局部数组仍被保留。图底部将长度相加:1 + 2 + … + (n−1) + n = n(n+1)/2,指向平方阶 O(n²)。代码最深处还多一个参数 0 的栈帧,但不多分配数组;调用栈的 O(n) 开销不会改变由这些数组决定的 O(n²) 峰值空间。
4. 指数阶 \(O(2^n)\)¶
指数阶常见于二叉树。观察图 2-19 ,层数为 \(n\) 的“满二叉树”的节点数量为 \(2^n - 1\) ,占用 \(O(2^n)\) 空间:
可视化运行
图 2-19 满二叉树产生的指数阶空间复杂度
图解 2-19:存储 n 层满二叉树所需的空间
存储整棵 n 层满二叉树,需要统计所有保留下来的节点,而不只是递归调用栈。
n 为正整数,图对应 build_tree 构建并保存的树。每个圆圈代表一个占常数空间的节点,父节点通过箭头连接左右两个子节点;右侧大括号标“共 n 层”。
图画出前三层,再从第 3 层的 4 个节点伸出 8 条箭头接省略号,表示继续展开。右列“各层的节点总数”用幂次写出 2⁰、2¹、2²、…、2ⁿ⁻¹。下表补充层号、前几项的十进制值及幂次读法。
| 层(根为第 1 层) | 节点总数 |
|---|---|
| 1 | 2⁰ = 1 |
| 2 | 2¹ = 2 |
| 3 | 2² = 4 |
| n | 2ⁿ⁻¹,即 2 的 n−1 次方 |
底部把各层相加:2⁰ + 2¹ + 2² + … + 2ⁿ⁻¹ = 2ⁿ − 1,即 2 的 n 次方再减 1。新节点通过左右指针挂在树上,不随构建它的调用返回而销毁,因此这些节点同时占用内存。虽然递归调用栈只有 O(n) 深,整棵树仍需 O(2ⁿ) 空间,这也是底部箭头指向的结论。
5. 对数阶 \(O(\log n)\)¶
对数阶常见于分治算法。例如归并排序,输入长度为 \(n\) 的数组,每轮递归将数组从中点处划分为两半,形成高度为 \(\log n\) 的递归树,使用 \(O(\log n)\) 栈帧空间。
再例如将数字转化为字符串,输入一个正整数 \(n\) ,它的位数为 \(\lfloor \log_{10} n \rfloor + 1\) ,即对应字符串长度为 \(\lfloor \log_{10} n \rfloor + 1\) ,因此空间复杂度为 \(O(\log_{10} n + 1) = O(\log n)\) 。
2.4.4 权衡时间与空间¶
理想情况下,我们希望算法的时间复杂度和空间复杂度都能达到最优。然而在实际情况中,同时优化时间复杂度和空间复杂度通常非常困难。
降低时间复杂度通常需要以提升空间复杂度为代价,反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为“以空间换时间”;反之,则称为“以时间换空间”。
选择哪种思路取决于我们更看重哪个方面。在大多数情况下,时间比空间更宝贵,因此“以空间换时间”通常是更常用的策略。当然,在数据量很大的情况下,控制空间复杂度也非常重要。