故事前言：
🌟《算法王国的速度比赛》
1、在 算法王国里，每年都会举行一次 程序速度大赛。
参赛的不是人，而是各种 算法机器人 🤖。
2、比赛规则很简单：
给机器人很多很多数据，看谁完成任务最快。
3、但是评委发现一个问题：
-
如果数据只有 10个，几乎所有算法都很快
-
如果数据有 100万，有些算法就慢得像乌龟 🐢
4、于是评委们发明了一种评估标准：
🧠 算法复杂度
5、用来估算：
-
时间复杂度 ⏰
程序大约要做多少次计算 -
空间复杂度 📦
程序需要多少内存
6、今天我们主要学 时间复杂度估算。
一、算法复杂度的核心思想
1、记住一句最重要的话：
只看数据规模 n 变大时，程序增长的速度
2、比如：
数据量：
n = 10
n = 100
n = 1000
n = 100000
3、我们关心的是：
程序运行次数怎么变。
二、最常见的复杂度
1、算法王国有几个著名选手：
| O(1) | 常数算法 | 🚀最快 |
| O(log n) | 对数算法 | 很快 |
| O(n) | 线性算法 | 正常 |
| O(n log n) | 稍慢 | |
| O(n²) | 平方算法 | 慢 |
| O(n³) | 立方算法 | 非常慢 |
2、记住顺序：
O(1) < O(log n) < O(n) < O(n log n) < O(n²)< O(n³)
三、第一种：O(1) 常数复杂度
1、故事：
机器人只做 一次操作。
2、比如：
int n ;
cin >> n;
cout << n++;
3、无论：
n = 10
n = 1000
n = 100000
4、操作次数都是：
cin 操作 1次
cout 操作 1次
n++ 操作 1次
一共3次
5、所以：
时间复杂度 = O(1)
6、意思是：
操作次数是固定的常数。
四、第二种：O(n) 线性复杂度
1、故事：
机器人要检查 每一个箱子。
2、如果有 n 个箱子。
程序：
for(int i=1;i<=n;i++)
{
cout<<i<<endl;
}
3、算一算：
（1）如果：n = 5
循环：
5次
（2）如果：n = 100
循环
100次
（3）操作次数：
≈ n
4、所以：
时间复杂度 O(n)
五、第三种：O(n²) 平方复杂度
1、故事：
学校要让 每个学生和所有学生握手 🤝
2、程序：
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<i<<" "<<j<<endl;
}
}
3、算一算：
（1）如果
n = 5
次数
5 × 5 = 25
（2）如果
n = 100
次数
100 × 100 = 10000
4、所以：
时间复杂度 O(n²)
5、口诀：
两层循环 → n²
三层循环 → n³
六、含多项式的复杂度
1、有时候程序不是简单循环。
2、例如：
for(int i=1;i<=n;i++)
{
cout<<i<<endl;
}
for(int i=1;i<=n*n;i++)
{
cout<<i<<endl;
}
第一部分：
n 次
第二部分：
n² 次
总次数：
n + n²
3、复杂度写作：
O(n + n²)
4、但在复杂度估算里：
只保留 最大项
5、所以：
时间复杂度：O(n²)
6、口诀：
多项式只看最大项
7、例子：
| n² + n | O(n²) |
| n³ + n² + n | O(n³) |
| 5n² + 3n | O(n²) |
8、原因：
当 n 很大时：
n² 远大于 n
七、对数复杂度 O(log n)
这是很多学生不容易理解的。
我们用故事讲。
1、故事：猜数字游戏
（1）老师想一个数：
1 ~ 100
（2）你每次猜。
老师说：
大了
小了
（3）聪明的方法是：
每次猜中间。
（4）例如：
第一次
猜 50
范围变成
50 ~ 100
第二次
猜 75
范围变
75 ~ 100
第三次、第四次…….
范围越来越小。
（5）每次：
数据量减半
这就是：
log₂ n
（6）例如：
log₂8 = 3
2、所以对数复杂度是：
O(log n)
八、经典例子：二分查找
while(l <= r)
{
mid = (l+r)/2;
if(a[mid]==x)
return mid;
if(a[mid] < x)
l = mid+1;
else
r = mid-1;
}
每次：
范围减半
所以：
时间复杂度 O(log n)
九、组合复杂度
1、有时复杂度会组合。
2、例如：
for(int i=1;i<=n;i++)
{
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
}
}
（1）外层：
n 次
（2）内层：
log n
（3）总复杂度：
n × log n
（4）所以：
O(n log n)
十、空间复杂度
1、空间复杂度 = 使用的内存。
2、例如：
（1）一维数组：
int a[100000];
（2）需要
100000 个空间
（3）所以：
空间复杂度 O(n)
（4）如果是二维数组：
int a[n][n];
（5）需要N*N个空间：
空间复杂度 O(n²)
（6）如果只是：
int a,b,c;
（7）只有固定变量：
O(1)
十一、复杂度估算三步法
学生推荐用下列方法：
1、第一步：找到循环
看有几层循环。
1层 → n
2层 → n²
3层 → n³
2、第二步：看循环范围
（1）例如：
for(i=1;i<=n;i++)
是：
n
（2）如果：
i *= 2
就是：
log n
3、第三步：合并复杂度
例如：
n + n² → n²
n × log n → n log n
十二、给学生的记忆口诀
一层循环 O(n)
两层循环 O(n²)
三层循环 O(n³)
每次减半 O(log n)
循环+二分 O(n log n)
多项式只看最大项
十三、练习题（判断复杂度）
题1
for(int i=1;i<=n;i++)
cout<<i;
答案
O(n)
题2
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cout<<i*j;
答案
O(n²)
题3
for(int i=1;i<=n;i*=2)
cout<<i;
答案
O(log n)
题4
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cout<<j;
次数：
1+2+3+…+n
≈
n²/2
复杂度
O(n²)
十四、算法竞赛经验
如果
一般：
| O(n) | ✔ |
| O(n log n) | ✔ |
| O(n²) | ❌ |
所以竞赛里：
n ≤ 10^5 → 需要 O(n log n)
🌟最后一句话
算法复杂度不是精确时间，而是增长速度。
我们关心的是：
n变大时
程序变慢多少
