计算:一切数据处理的起点
看完你能说清什么是算法,并用复杂度判断一个算法的好坏
按 空格/→ 演示下一步
全部页面点击任意一页,跳回舞台从这页播放
计算:一切数据处理的起点
看完你能说清什么是算法,并用复杂度判断一个算法的好坏
绳索计算机
上一页说,计算就是一切数据处理的起点。但计算未必要芯片——很久以前的人用一根绳、几个结就能做乘法。我们用结绳算 2 的幂:绳的长度是数,打结这个动作就是运算。
折一次纸厚度翻倍,对应打一个结绳长翻倍
尺规计算机
上一页绳索能算乘法,那只有不带刻度的直尺和圆规呢?古希腊人靠它们解方程、开平方、作正多边形——每一步画线画圆的顺序,就是一份可执行的算法。
菜谱的按序步骤对应作图的有序操作,成品对应方程的根
计算 = 信息变换
绳结记数、尺规作图,看似两回事,但有共同点:都是拿到一份信息,按固定的规则操作,最后得到另一份信息。把这两个实例摆在一起,就能归纳出计算到底是什么。
食材对应输入信息,菜谱对应规则,切炒的工序对应工具执行
算法是什么
绳索计算机和尺规计算机都能完成计算,但步骤全靠人临场发挥。想要结果可靠、可复用,就得把每一步事先写死——这便是算法的起点。
厨房对应计算模型,每步「加盐少许」若改成「加盐3克」才够明确
有穷性:算法的生命线
从「开始」出发,顺着箭头走:只有两条路能到「终止」,任何一条走不完的路都不算算法。
自测:这算算法吗
计算机科学家说的"算法",下列哪一项最符合定义?
好算法的四大特质
前面我们确认了「有穷性」只是入场券。那什么样的算法才算好?想象两个都能算对的程序:一个偶尔崩溃、一个谁都看不懂、一个要跑三天——你选哪个?好算法有四个公认标准。
能干对活对应正确性、不闯祸对应健壮性、交接顺畅对应可读性、干活快对应效率
效率:时间与空间
两个算法都能解题,为什么一个秒出、一个卡死?差异藏在时间与空间两个维度里。
- 用查找表换速度,一步出结果
- 内存占用大,表越长空间越多
- 适合实时场景:搜索、行情计算
- 现算现用,不存中间结果
- 内存占用小,但每步都要重算
- 适合海量数据、内存受限设备
收束:从计算到好算法
- ✓计算无处不在:绳索、尺规都在做信息变换
- ✓算法 = 有限步骤 + 每步可执行 + 必然终止
- ✓有穷性不是细节,是算法与空谈的分界线
- ✓好算法先求正确有穷,再比时间和空间
- ✓具体例子先行,抽象定义只是给规律命名
课后思考
三个开放问题没有唯一答案——先自己想一会儿,再看参考思路。
参考答案顺着「计算 = 信息变换」想:装置只是变换的执行者,不同介质可以有相同的变换规则。判断两个装置是否在做同一种计算,看输入输出的对应关系是否一致。
参考答案用时间与空间两条线去衡量:哪里最频繁、哪里的等待最长。好的优化标准往往是「用户感知的等待」而非总耗时——这正好呼应算法评估要看场景。
参考答案想想操作系统、传感器监控:它们「不停」,但每一步响应都是有限变换。可以把边界拆开看——单个任务必须有穷,整体服务可以是无限循环包裹的有穷步骤。