企业官网建设流程全解析

🌟数学魔法函数学院

第九课《魔法天梯有多高——对数增长》

—— 为什么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、写成指数：

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）数据从：

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、指数增长

公式：

结果：

增长越来越快。

2、对数增长

公式：

结果：

增长越来越慢。

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()函数解决实际问题，并学会如何用对数计算位数、层数和算法复杂度。🚀