数学魔法函数学院第九课《魔法天梯有多高——对数增长》—— 为什么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 10242、每次×23、写成指数次数楼层02⁰112¹222²432³842⁴164、到达1024时。5、问题变成2的几次方等于1024也就是答案106、所以只需要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 → 22第二次2 → 43第三次4 → 84第n次1 → 2ⁿ2、反过来问达到某个数字需要几次答案log₂(n)3、这就是对数增长 五、观察对数增长到底有多慢1、看看这张表数据规模 nlog₂(n)2142831643256461287256851291024102、发现了吗1数据从2 变成 10242扩大512倍3而对数1 变成 104只增加9这就是对数增长极慢 六、小游戏猜数字1、国王心里想了一个数字。范围1 ~ 1002、你每次猜一个数。如果猜错。国王告诉你大了或者小了3、怎么最快1没学过二分的同学只能1 2 3 4 5 ...一个个试。2最坏情况100次3学过二分的同学直接猜50范围减半。4再猜25 或者 75再减半。不断减半。通过二分查找很快找到了 七、二分查找为什么这么快1、假设1024个数字1第一次剩5122第二次剩2563第三次剩1284第四次剩64不断减半。5直到剩1个2、问需要多少次3、其实就是1024 ÷ 2 ÷ 2 ÷ 2 ...直到变成14、即2的几次方等于10245、所以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ⁿ122438416101024增长越来越快。2、对数增长公式结果nlog₂n214283164102410增长越来越慢。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第三题不断除22048 1024 512 ...直到1。需要多少次第四题为什么100万个数字。二分查找只需要20次左右而顺序查找最坏需要100万次 本课总结1、今天我们认识了对数增长2、核心思想每次翻倍 → 指数 每次减半 → 对数3、重要应用✅ 二分查找✅ 快速幂✅ AVL树✅ 线段树✅ 堆4、竞赛名言当你发现一个问题每次都能缩小一半时答案里往往藏着一个 log。下一课我们将进入对数王国最终挑战⚔️《智慧水晶测试——log函数实战应用》⚔️在那里我们将真正使用 C 的log()函数解决实际问题并学会如何用对数计算位数、层数和算法复杂度。