深高北-L19-时空复杂度&枚举算法

张kk

2026-04-23 23:22:11

发布于：广东

0阅读

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²)

二、空间复杂度

常见空间复杂度

复杂度	通俗理解	例子
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²)（开了二维数组）

《枚举算法笔记》

一句话理解

枚举：把所有可能的情况一个一个试，找出正确答案。

就像开密码锁，从 000 试到 999，总有一个能打开。

一、什么是枚举

枚举 = 列出所有可能性 + 逐个检查

优点：简单粗暴，一定能找到答案（只要时间够）

缺点：可能很慢，情况太多时会超时

二、枚举的基本结构

// 枚举的通用模板
for (所有可能的情况) {
    if (这种情况满足条件) {
        记录答案 / 输出
    }
}

三、经典例子

例子1：找最大值

int arr[5] = {3, 8, 2, 10, 5};
int maxVal = arr[0];

for (int i = 0; i < 5; i++) {
    if (arr[i] > maxVal) {
        maxVal = arr[i];
    }
}
cout << maxVal;  // 输出 10
// 枚举了数组中的每一个数

例子2：判断质数

int n = 17;
bool isPrime = true;

for (int i = 2; i < n; i++) {
    if (n % i == 0) {
        isPrime = false;  // 能被整除，不是质数
        break;
    }
}

if (isPrime) cout << n << "是质数";
// 枚举了 2 到 n-1 的所有数

例子3：百钱百鸡问题

公鸡5文，母鸡3文，小鸡3只1文，100文买100只鸡，各几只？

for (int g = 0; g <= 20; g++) {        // 公鸡最多20只
    for (int m = 0; m <= 33; m++) {    // 母鸡最多33只
        int x = 100 - g - m;           // 小鸡数量
        if (x >= 0 && 5*g + 3*m + x/3 == 100 && x % 3 == 0) {
            cout << g << " " << m << " " << x << endl;
        }
    }
}
// 枚举了所有公鸡和母鸡的可能数量

四、枚举的优化

枚举太慢怎么办？两个常用技巧：

技巧1：减少枚举范围

// 找 a + b = 100 的正整数解
// 笨办法：枚举 a 和 b（100×100=10000种）
for (int a = 1; a <= 100; a++) {
    for (int b = 1; b <= 100; b++) {
        if (a + b == 100) cout << a << " " << b << endl;
    }
}

// 优化：枚举 a，b = 100 - a（只有100种）
for (int a = 1; a <= 99; a++) {
    int b = 100 - a;
    cout << a << " " << b << endl;
}

技巧2：利用对称性

// 找 a ≤ b 且 a + b = 10
// 优化前：枚举 a 和 b
// 优化后：a 只枚举到 5（因为 a ≤ b，a 最大是 5）
for (int a = 1; a <= 5; a++) {
    int b = 10 - a;
    cout << a << " " << b << endl;
}

五、时间复杂度

枚举类型	时间复杂度	例子
一重循环	O(n)	找最大值
两重循环	O(n²)	百钱百鸡
三重循环	O(n³)	找三个数和为定值

注意：n 很大时（如 n=10000），O(n²) 就有一亿种情况，会超时！

六、什么时候用枚举？

适合用枚举	不适合用枚举
数据范围小（n ≤ 20）	n 很大（n > 1000）
情况数量有限	情况数量爆炸（2ⁿ 或 n!）
没有更好的算法	有数学公式或贪心解法
用来验证其他算法	对时间要求严格