算法复杂度：高效编程的黄金法则

一、为什么要学复杂度

同样实现一个功能，写法不同效率天差地别：

• 普通写法：数据量大直接超时
• 优写法：时间空间最优，笔试稳稳通过

复杂度就是用来衡量算法运行效率的两把尺子：

1. 时间复杂度：运行耗时多少
2. 空间复杂度：占用内存多少

二、大 O 表示法 核心规则

只看最高次项，忽略常数、忽略低次项。常见复杂度从快到慢排序：\(O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)\)

三、常见时间复杂度逐一讲解

1. O (1) 常数级

执行次数固定，和数据量 n 无关

int a = 10; int b = 20; cout << a + b;

2. O (n) 线性级

一层循环，循环 n 次

for(int i = 0; i < n; i++) { cout << i; }

3. O (n²) 平方级

两层嵌套循环，笔试最容易超时

for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { } }

4. O (logn) 对数级

每次数据缩小一半，二分查找就是典型 O (logn)效率极高，十万级数据也秒跑。

5. O(nlogn)

排序常用复杂度：快排、归并排序

四、空间复杂度

看额外开辟的辅助空间大小：

• O (1)：只用到几个变量，不开数组 / 容器
• O (n)：开了大小为 n 的数组、vector
• 递归也要算空间（递归栈）

五、复杂度优化思想

1. 能用 O (n) 绝不写 O (n²)
2. 能二分就不用遍历，把 O (n) 降为 O (logn)
3. 尽量少开多余数组，节约空间
4. 递归深度太大容易栈溢出，改用迭代

六、今日总结

1. 算法好坏看时间 + 空间复杂度
2. 大 O 只保留最高次项
3. 常见复杂度速率：(O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)
4. 刷题第一件事：先分析复杂度，再写代码