-简单算法 Lecture 3 - Simple Algorithms
-简单算法 Lecture 3 - Si
搞清线性与二分搜索、冒泡归并排序的实现差异与复杂度边界，从此按场景选算法
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
-简单算法 Lecture 3 - Si
搞清线性与二分搜索、冒泡归并排序的实现差异与复杂度边界，从此按场景选算法
Lecture 3 Introduction
上一节我们认识了程序的基本骨架——变量、循环、条件。今天开始让程序'找东西、算东西、排序东西'，这些动作背后都有一个共同的名字：简单算法。
食谱每步明确无歧义；同样的食材同样的做法，每次做出同样的菜
Iteration
在 Excel 里给 1000 个数都加 1，手动改几乎不可能，写一条「重复执行」的指令让电脑跑——这就是迭代的核心思路：把同一段动作反复做下去。
每跑一圈是一次迭代，规定圈数就是终止条件；忘了数圈就会一直跑（死循环）
Guess and Check Algorith
上页我们学了用 for/while 做机械重复。但循环只是在搬砖——Guess and Check 才是把循环变成「解题」的第一个套路。它朴素却强大，是后续所有高效算法的出发点。
逐把插锁孔试转，对应逐个候选 check；命中即停
Loop Mechanisms
上次我们讲了 Iteration 和 Guess and Check——一个猜数字的程序会反复尝试直到猜对。但「反复」背后到底怎么实现？为什么有些循环跑 5 次就停，有些要跑百万次？这一页拆开看。
while 像「跑到喘不过气就停」——条件驱动；for 像「我决定跑 10 圈」——计数驱动
Floating Point Accuracy
上一讲我们用 abs(guess**2 - x) < epsilon 判断猜测是否够准。有人会问：为什么不直接 == 0？因为计算机里的 0.1 其实不是 0.1——这就是浮点精度问题。
1/3 在十进制写不完，0.1 在二进制也写不完——某些数在当前进制下必然无限循环
Approximation Methods
上一节我们看到浮点数天生有误差——很多真实答案根本存不进去。但工程上我们往往不需要完美答案，够用就行。怎么在有限精度里找到「够好的值」？
每次得到反馈（远近），据此调整下一步方向，最终定位目标
Bisection Search
上一页的猜数字游戏，如果对方只回「大了」或「小了」——最聪明的策略不是从 1 试到 100，而是每次把范围砍掉一半。
不逐页翻，翻到中间看首字母决定往前还是往后，每次砍掉一半
Demo: Bisection Search
上页说 bisection 每步砍一半。这次玩个游戏：你心里想 1 到 100 的整数，我最多几次猜中？答案会让你意外——只要 7 次。
翻到中间 → 看首字母决定留前半还是后半 → 再翻中间 → 直到定位
Newton-Raphson Root Find
二分法像对半猜——稳但慢。如果知道函数在某点的斜率，就能'看清方向'，一步到位附近。这就是 Newton-Raphson 的思路。
切线斜率=山坡坡度；横截距=下一步落脚点
本节要点
- ✓迭代本质是用重复逼近真相，不是穷举所有可能
- ✓二分法慢但鲁棒，牛顿法快但依赖初值与连续性
- ✓浮点精度划定算法边界，停止条件必须含容差
- ✓猜-检是搜索类算法的骨架，for/while 选择看终止条件是否已知
- ✓好算法=收敛速度、稳定性、实现复杂度三者的折中
课后思考
先独立思考再对照参考答案。三个问题对应记忆、应用、迁移三个层次。
参考答案二分法依赖介值定理，异号才能保证区间内有零点。牛顿法靠导数做线性逼近逐步迭代，不依赖区间假设，所以适用范围更广但对初值敏感。
参考答案牛顿法可能发散或收敛到别的根。例如金融模型估算内部收益率时，若初值偏离真实利率太远，迭代可能跳出合理区间。工程上常先用二分粗定位，再用牛顿加速。
参考答案浮点无法精确表示许多小数，函数值可能永远不严格为零，会导致死循环。用区间宽度判断更可靠——区间足够小时根必在其中，精度可控可量化。