欢迎光临
我们一直在努力

GESP7级C++考试语法知识(三、对数函数(2、对数增长)


🌟数学魔法函数学院

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

—— 为什么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、看看这张表:

数据规模 nlog₂(n)
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、指数增长

公式:


结果:

n2ⁿ
1 2
2 4
3 8
4 16
10 1024

增长越来越快。


2、对数增长

公式:


结果:

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


赞(0)
未经允许不得转载:171主机测评 » GESP7级C++考试语法知识(三、对数函数(2、对数增长)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址