(a)计算

官官方信息技术老师·11 页·深入(追求细节与边界)·0 次浏览·38 天前
计算理论算法复杂度

计算:一切数据处理的起点

看完你能说清什么是算法,并用复杂度判断一个算法的好坏

按 空格/→ 演示下一步

问一句
1 / 11 页

全部页面点击任意一页,跳回舞台从这页播放

计算理论算法复杂度

计算:一切数据处理的起点

看完你能说清什么是算法,并用复杂度判断一个算法的好坏

1第 1 页 · 计算:一切数据处理的起点

绳索计算机

上一页说,计算就是一切数据处理的起点。但计算未必要芯片——很久以前的人用一根绳、几个结就能做乘法。我们用结绳算 2 的幂:绳的长度是数,打结这个动作就是运算。

绳长即数值
绳段长度对应一个数,长一米代表 1,翻倍绳长即数值翻倍
打结即运算
每打一个结,把当前绳长加倍,一次结就是一次乘 2
结数即指数
打了 n 个结,绳长就是 2ⁿ,结的位置记录了计算过程
折纸翻倍对应 →结绳乘 2

折一次纸厚度翻倍,对应打一个结绳长翻倍

Ln=2n(打 n 个结后的绳长)L_n = 2^n \quad (\text{打 } n \text{ 个结后的绳长})
2第 2 页 · 绳索计算机

尺规计算机

上一页绳索能算乘法,那只有不带刻度的直尺和圆规呢?古希腊人靠它们解方程、开平方、作正多边形——每一步画线画圆的顺序,就是一份可执行的算法。

两种基本操作
直尺画过两点的直线,圆规画定圆心的圆,仅此而已
交点即计算
线与线、线与圆、圆与圆的交点,产生新数值
序列即算法
有限步操作照序执行,输出就是方程的根
能力边界
加减乘除与开平方可作;倍立方、三等分角被证明不可能
菜谱做菜对应 →尺规作图

菜谱的按序步骤对应作图的有序操作,成品对应方程的根

x=−b±b2−4ac2a  ⇒  根只含加减乘除与平方根,故尺规皆可作x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\;\Rightarrow\;根只含加减乘除与平方根,故尺规皆可作
3第 3 页 · 尺规计算机

计算 = 信息变换

绳结记数、尺规作图,看似两回事,但有共同点:都是拿到一份信息,按固定的规则操作,最后得到另一份信息。把这两个实例摆在一起,就能归纳出计算到底是什么。

对象是信息
输入是绳结、线段这类承载信息的符号,不是信息本身
靠规则驱动
每一步怎么做是事先定好的,不需要临场发挥
借助工具执行
绳索、尺规就是执行规则的物理装置
产出新信息
结束时的状态代表答案,即变换的结果
厨房做菜对应 →计算

食材对应输入信息,菜谱对应规则,切炒的工序对应工具执行

4第 4 页 · 计算 = 信息变换

算法是什么

绳索计算机和尺规计算机都能完成计算,但步骤全靠人临场发挥。想要结果可靠、可复用,就得把每一步事先写死——这便是算法的起点。

依托计算模型
算法不是空中楼阁,要先说清在什么机器上执行:绳索、尺规还是图灵机
实现特定功能
输入到输出的明确对应关系,如排序、求最大公约数
指令序列
有限步骤、按顺序执行,每一步都可实际完成
必须明确
每条指令无歧义:同一个状态下,执行结果唯一确定
一份菜谱对应 →算法

厨房对应计算模型,每步「加盐少许」若改成「加盐3克」才够明确

5第 5 页 · 算法是什么

有穷性:算法的生命线

从「开始」出发,顺着箭头走:只有两条路能到「终止」,任何一条走不完的路都不算算法。

图解渲染中…
c1:判定分支:执行到有限步后是否必然停止g1:如while(true)永不停,不满足有穷性
6第 6 页 · 有穷性:算法的生命线

自测:这算算法吗

点击作答

计算机科学家说的"算法",下列哪一项最符合定义?

7第 7 页 · 自测:这算算法吗

好算法的四大特质

前面我们确认了「有穷性」只是入场券。那什么样的算法才算好?想象两个都能算对的程序:一个偶尔崩溃、一个谁都看不懂、一个要跑三天——你选哪个?好算法有四个公认标准。

正确性
对每个合法输入都给出正确输出,能被测试和证明
健壮性
遇到非法输入不崩溃,给出提示或安全处理
可读性
结构和命名清晰,他人(和未来的你)能维护
效率
时间和空间消耗可接受,用复杂度衡量
招一名员工对应 →算法四大特质

能干对活对应正确性、不闯祸对应健壮性、交接顺畅对应可读性、干活快对应效率

8第 8 页 · 好算法的四大特质

效率:时间与空间

两个算法都能解题,为什么一个秒出、一个卡死?差异藏在时间与空间两个维度里。

省时间的算法
  • 用查找表换速度,一步出结果
  • 内存占用大,表越长空间越多
  • 适合实时场景:搜索、行情计算
省空间的算法
  • 现算现用,不存中间结果
  • 内存占用小,但每步都要重算
  • 适合海量数据、内存受限设备
要实时响应选省时间(空间换时间);内存紧张或数据量巨大选省空间(时间换空间)。
9第 9 页 · 效率:时间与空间

收束:从计算到好算法

  • ✓计算无处不在:绳索、尺规都在做信息变换
  • ✓算法 = 有限步骤 + 每步可执行 + 必然终止
  • ✓有穷性不是细节,是算法与空谈的分界线
  • ✓好算法先求正确有穷,再比时间和空间
  • ✓具体例子先行,抽象定义只是给规律命名
延伸主题:确定性:算法能容错吗如何度量算法快慢:大 O从算法到程序:谁执行每一步
10第 10 页 · 收束:从计算到好算法

课后思考

三个开放问题没有唯一答案——先自己想一会儿,再看参考思路。

1绳索计算机和现代芯片都能做加法,为什么说计算的本质是信息变换,而不是某个具体装置?

参考答案顺着「计算 = 信息变换」想:装置只是变换的执行者,不同介质可以有相同的变换规则。判断两个装置是否在做同一种计算,看输入输出的对应关系是否一致。

2把「效率」放进你的日常:手机里哪些功能让你等得难受?如果只能优化一个,你会按什么标准选?

参考答案用时间与空间两条线去衡量:哪里最频繁、哪里的等待最长。好的优化标准往往是「用户感知的等待」而非总耗时——这正好呼应算法评估要看场景。

3有穷性是算法的生命线。如果允许一个过程永不停止、持续输出,它还算计算吗?边界在哪里?

参考答案想想操作系统、传感器监控:它们「不停」,但每一步响应都是有限变换。可以把边界拆开看——单个任务必须有穷,整体服务可以是无限循环包裹的有穷步骤。

11第 11 页 · 课后思考
(a)计算 · 知识图解