深高北-L19-时空复杂度

张kk

2026-04-24 18:31:52

发布于：广东

54阅读

0回复

0点赞

《时间复杂度 & 空间复杂度》

一句话理解

时间复杂度：你的代码跑得快不快？
空间复杂度：你的代码占内存多不多？

就像玩游戏：

时间复杂度 = 通关需要多长时间
空间复杂度 = 游戏占了多少存储空间

一、时间复杂度

常见复杂度（从快到慢）

复杂度	名称	通俗理解	例子
O(1)	常数时间	无论数据多少，都是一瞬间	数组按下标取值
O(log n)	对数时间	数据翻倍，只多一步	二分查找
O(n)	线性时间	数据多少，就做多少次	遍历数组
O(n log n)	线性对数	比线性慢一点	快速排序、归并排序
O(n²)	平方时间	数据翻倍，时间变4倍	冒泡排序、双重循环
O(2ⁿ)	指数时间	数据多一点，直接爆炸	递归算斐波那契

速度对比（数据量 n=1000 时）

O(1)      → 1 步
O(log n)  → 约 10 步
O(n)      → 1000 步
O(n log n)→ 约 10000 步
O(n²)     → 1000000 步（一百万）
O(2ⁿ)     → 宇宙毁灭也算不完

怎么算时间复杂度？

口诀：看循环，数嵌套

// O(1) - 常数时间
int x = arr[5];
int y = a + b;

// O(n) - 线性时间
for (int i = 0; i < n; i++) {
    cout << arr[i];
}

// O(n²) - 平方时间
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << j;
    }
}

// O(log n) - 对数时间
int i = 1;
while (i < n) {
    i = i * 2;
}

复杂度的"省略规则"

忽略常数：O(2n) → O(n)，O(100) → O(1)
只保留最高次项：O(n² + n) → O(n²)

在信奥（信息学竞赛）中，时间限制为 1 秒时，通常对应 约 ( 3 \times 10^7 ) 到 ( 10^8 ) 次简单操作（如整数加减、比较、位运算等）。

更精确的经验参考（针对 C++，O2 优化）：

稳定安全：( 2 \times 10^7 ) 次运算（大部分 OJ 都能过）
常见极限：( 5 \times 10^7 ) 次运算（较优实现，简单操作）
风险边界：( 1 \times 10^8 ) 次运算（可能压线过，也可能 TLE）
通常超时：( \ge 2 \times 10^8 ) 次运算

不同操作耗时不同：

整数加减、位运算：最快
乘法稍慢（但仍很快）
除法、取模：慢（约为加减法的 3~10 倍）
内存访问（尤其随机访问大数组）：可能导致远低于上述数值

二、空间复杂度

常见空间复杂度

复杂度	通俗理解	例子
O(1)	只用了几个变量，和数据多少无关	交换两个数
O(n)	开了一个一维数组	int arr[100];
O(n²)	开了一个二维数组	int arr[10][10];

怎么算空间复杂度？

口诀：看数组，几个维数几次方

// O(1) - 常数空间
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

// O(n) - 线性空间（一维数组）
int temp[100];
for (int i = 0; i < n; i++) {
    temp[i] = arr[i];
}

// O(n²) - 平方空间（二维数组）
int matrix[10][10];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        matrix[i][j] = i + j;
    }
}

重要：输入数据不算！

空间复杂度只算你额外开的数组，输入数组本身不占额度。

void process(int arr[], int n) {  // arr 是输入，不算
    int temp[100];                 // 这个才算！新开了数组
}
// 空间复杂度：O(n)

三、完整例子对比

// 例子1：找最大值
int findMax(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

// 例子2：数组倒序
void reverse(int arr[], int n) {
    int temp[100];
    for (int i = 0; i < n; i++) {
        temp[i] = arr[n - 1 - i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] = temp[i];
    }
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)

// 例子3：冒泡排序
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
// 时间复杂度：O(n²)
// 空间复杂度：O(1)

四、总结表

你要做的事	时间复杂度	空间复杂度
数组按下标取值	O(1)	O(1)
遍历一遍数组	O(n)	O(1)
双重循环遍历	O(n²)	O(1)
二分查找	O(log n)	O(1)
复制一个数组	O(n)	O(n)
冒泡排序	O(n²)	O(1)
归并排序	O(n log n)	O(n)

五、记忆口诀

时间看循环，一层 n 两层 n²
空间看数组，一维 n 二维 n²
常数都是 O(1)，输入数据不算它

六、小测验

int result[10][10];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        result[i][j] = i * j;
    }
}

答案：

时间复杂度：O(n²)（双重循环嵌套）
空间复杂度：O(n²)（开了二维数组）

在信奥中，空间限制 128 MiB 时，通常能开的数组大小取决于数据类型和内存开销。

基本结论（C++）

128 MiB ≈ 134,217,728 字节

类型	大小	最多元素个数
`int` (32位)	4 B	约 3.35 × 10⁷（33,554,432）
`long long` (64位)	8 B	约 1.68 × 10⁷（16,777,216）
`bool` (实际通常1 B)	1 B	约 1.34 × 10⁸（134,217,728）
`char`	1 B	同上
`double`	8 B	同 `long long`

常见二维数组规模（`int` 类型）

int a[2000][2000]：约 16 MiB ✅ 安全
int a[5000][5000]：约 100 MiB ✅ 略紧张但可过
int a[6000][6000]：约 144 MiB ❌ 超限

二维数组极限（int）：约 5700 × 5700

注意事项

递归栈空间：递归深度过大（如 10⁵ 层）会额外占用内存，可能导致 MLE 或爆栈。
STL 容器开销：
- vector、string 等有少量额外内存（如 vector 约 24 字节的元数据）。
- queue、stack 默认底层是 deque，内存开销比数组大。
- 能用静态数组尽量用静态数组。
多维度数组：总元素数乘以类型大小即可估算。
代码段 + 数据段 + 堆栈：128 MiB 通常指总内存使用，静态数组、全局变量、堆分配（new/malloc）都算在内。