
🌟数学魔法函数学院
第九课《魔法天梯有多高——对数增长》
—— 为什么100万数据只需要查20次?
🎯 本课学习目标
学完本课后,你将掌握:
✅ 什么是对数增长
✅ 为什么对数增长非常慢
✅ 对数增长与指数增长的区别
✅ 二分查找为什么是 O(log n)
✅ 对数在信息学竞赛中的重要应用
✅ 如何利用 C++ 观察对数增长过程
🏰 一、故事开始:通天魔法塔
1、程序王国有一座神秘建筑:
🏯 通天魔法塔
传说:
塔顶藏着:
至尊算法宝典
但是没人知道塔有多高。
国王派出阿Q去测量。
2、阿Q发现:
这座塔十分特殊。
每上一层楼,
楼层编号都会:
翻倍
3、例如:
第1层
↓
第2层
↓
第4层
↓
第8层
↓
第16层
↓
第32层
4、国王问:
如果已经到了第1024层,
一共爬了多少次?
🔍 二、发现隐藏规律
1、观察:
1
2
4
8
16
32
64
128
256
512
1024
2、每次:
×2
3、写成指数:
| 0 | 2⁰=1 |
| 1 | 2¹=2 |
| 2 | 2²=4 |
| 3 | 2³=8 |
| 4 | 2⁴=16 |
4、到达:
1024
时。
5、问题变成:
2的几次方等于1024?
也就是:
答案:
10
6、所以:
只需要10步
🤔 三、为什么对数增长这么神奇?
现在有两个小精灵比赛。
1、红精灵(加法增长)
每次:
+1
路线:
1
2
3
4
5
6
7
…
到达:
1024
需要:
1023步
2、蓝精灵(翻倍增长)
每次:
×2
路线:
1
2
4
8
16
32
64
128
256
512
1024
只需:
10步
3、同样到达1024。
差距竟然:
1023步 VS 10步
🌟 四、什么叫对数增长?
1、假设:
每次翻倍。
(1)第一次:
1 → 2
(2)第二次:
2 → 4
(3)第三次:
4 → 8
(4)第n次:
1 → 2ⁿ
2、反过来问:
达到某个数字需要几次?
答案:
log₂(n)
3、这就是:
对数增长
📊 五、观察对数增长到底有多慢
1、看看这张表:
| 2 | 1 |
| 4 | 2 |
| 8 | 3 |
| 16 | 4 |
| 32 | 5 |
| 64 | 6 |
| 128 | 7 |
| 256 | 8 |
| 512 | 9 |
| 1024 | 10 |
2、发现了吗?
(1)数据从:
2
变成
1024
(2)扩大:
512倍
(3)而对数:
1
变成
10
(4)只增加:
9
这就是:
对数增长极慢
🎮 六、小游戏:猜数字
1、国王心里想了一个数字。
范围:
1 ~ 100
2、你每次猜一个数。
如果猜错。
国王告诉你:
大了
或者:
小了
3、怎么最快?
(1)没学过二分的同学只能:
1
2
3
4
5
…
一个个试。
(2)最坏情况:
100次
(3)学过二分的同学
直接猜:
50
范围减半。
(4)再猜:
25
或者
75
再减半。
不断减半。
通过二分查找很快找到了
🔥 七、二分查找为什么这么快?
1、假设:
1024个数字
(1)第一次:
剩512
(2)第二次:
剩256
(3)第三次:
剩128
(4)第四次:
剩64
不断减半。
(5)直到:
剩1个
2、问:
需要多少次?
3、其实就是:
1024 ÷ 2 ÷ 2 ÷ 2 …
直到变成:
1
4、即:
2的几次方等于1024?
5、所以:
1024个数
最多查10次
💻 八、C++模拟法,观察对数过程
我们来模拟不断除2。
#include <iostream>
using namespace std;
int main()
{
int n = 1024;
int cnt = 0;
while(n > 1)
{
n /= 2;
cnt++;
cout << "剩余:" << n << endl;
}
cout << "次数:" << cnt << endl;
return 0;
}
输出:
512
256
128
64
32
16
8
4
2
1
次数:10
发现:
次数
=
log₂(1024)
⚔️ 九、指数增长 VS 对数增长
1、指数增长
公式:
结果:
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 10 | 1024 |
增长越来越快。
2、对数增长
公式:
结果:
| 2 | 1 |
| 4 | 2 |
| 8 | 3 |
| 16 | 4 |
| 1024 | 10 |
增长越来越慢。
3、生活中的应用
(1)指数增长带来的财富奥秘

通过上面的表格,你会发现,复利会给未来的你带来多大的财富,这就是指数增长。
(2)对数增长越来越慢,边际效应越来越低

通过上面的表格,你会发现,
收入与幸福感的关系:
当你从没有钱到得到10元钱,你的快乐值增加了2
但是你现在有1000元,如果收入带来快乐值增加2,就需要将收入提高到10000元。
单位收入增长给你带来的快乐值,会越来越低,这就是边际效应递减。
🚀 十、信息学竞赛中的应用
1、很多算法都和对数有关。
✅️二分查找
✅️快速幂
✅️ 线段树
✅️AVL树
✅️堆(优先队列)
2、所以:
对数 = 高效算法的灵魂
🚧 十一、初学者最容易犯的错误
错误1
认为:
log₂(1000000)
很大。
实际上:
≈20
只有20左右。
错误2
把:
2ⁿ
和:
log₂(n)
搞反。
记忆口诀:
指数增长像火箭
越来越快
对数增长像蜗牛
越来越慢
错误3
看到:
每次减半
没有想到:
log
记忆:
翻倍
减半
二分
都和log有关
🎮 挑战任务
第一题
不断翻倍:
1 → 2 → 4 → 8 …
到达:
4096
需要多少次?
第二题
100万数据。
使用二分查找。
最多查多少次?
提示:
2²⁰≈1048576
第三题
不断除2:
2048
1024
512
…
直到1。
需要多少次?
第四题
为什么:
100万
个数字。
二分查找只需要:
20次左右
而顺序查找最坏需要:
100万次
📝 本课总结
1、今天我们认识了:
对数增长
2、核心思想:
每次翻倍
→ 指数
每次减半
→ 对数
3、重要应用:
✅ 二分查找
✅ 快速幂
✅ AVL树
✅ 线段树
✅ 堆
4、竞赛名言:
当你发现一个问题每次都能缩小一半时,答案里往往藏着一个 log。
下一课,我们将进入对数王国最终挑战:
⚔️《智慧水晶测试——log函数实战应用》⚔️
在那里,我们将真正使用 C++ 的 log() 函数解决实际问题,并学会如何用对数计算位数、层数和算法复杂度。🚀

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)

