计科导上-07：算法思维之概念与复杂度

课程摘要 / Summary

本节课进入“算法思维”单元。老师没有一开始就给出抽象定义，而是先用图片隐写任务说明：算法可以很简练，但真正写成程序时必须面对文件格式、字节定位、数据结构和循环操作等细节。随后课程从文件系统、元数据、bytearray、BMP Pixel Array 和最低有效位隐写，过渡到高德纳的算法定义。最后用冒泡排序、递归斐波那契、渐进记号、构造性与有穷性说明：算法不仅要能描述步骤，还要能分析正确性边界和资源消耗。

课件纵览与课堂路径

本节课的核心问题

算法和程序有什么区别？
为什么老师用图片隐写作为算法思维的入口？
文件、元数据和 bytearray 如何支撑图片隐写算法？
高德纳算法定义的主干和五个特征是什么？
为什么算法定义不等于“正确算法”的定义？
如何用复杂度分析递归斐波那契的资源消耗？
o、O、Ω、Θ 分别表达什么量级关系？
“构造性”和“有穷性”为什么是计算过程的核心要求？

老师的讲课路径

从逻辑思维单元过渡到算法思维单元。
用图片隐写说明“程序有点难，算法很简单”。
补充文件系统、路径、数据与元数据、访问权限。
用 bytearray 读文件，并定位 BMP 文件中的 Pixel Array。
用最低有效位隐藏文本长度和文本内容。
引入高德纳算法定义：有限规则、操作序列、五个特征。
用冒泡排序检查算法定义。
讨论确定性、三种有穷性和“什么不是算法”。
区分算法定义、正确性分析和复杂度分析。
用递归斐波那契推导指数复杂度。
讲小 o、大 O、Ω、Θ 渐进记号。
用构造性和有穷性理解计算过程。

模块一：从程序转向算法思维

1.1 为什么进入算法思维

前面的课程已经讲过计算思维 ABC、冯诺依曼模型、Python 编程入门，也讲过直线程序、循环程序和递归函数。数据类型方面，我们已经接触过标量类型和容器类型，例如布尔、整数、浮点数、字符串、列表、元组和字典。本周开始引入新的数据类型：文件和字节数组。

上一周逻辑思维单元还讲到命题逻辑的可靠性、完备性和不可判定性，并进一步提到：一旦把皮亚诺算术放进形式系统，就会出现不完备问题。也就是说，数学基础和计算边界并不像直觉中那样“无所不能”。在这个背景下进入算法思维，核心问题就变成：当一个问题可以被计算时，我们怎样把它组织成可执行、可分析、可比较的步骤？

本节课的入口不是抽象定义，而是一个具体任务：图片隐写。这个任务可以同时暴露两个层面：

算法层面：输入是什么，输出是什么，要执行哪些步骤。
程序层面：文件怎样读入，字节怎样定位，哪些区域可以改，怎样循环处理每个字符。

老师还用小班作业里的图灵机加法器作对比：同样做任意位二进制加法，有人的状态转移表只有几十行，有人的状态转移表超过一百行。它们都能解决问题，但背后的算法设计并不一样。这说明写代码之前不能只盯语法细节，还要先想清楚问题如何分解、循环在哪里、数据结构怎样组织。

1.2 算法和程序的区别

课件中的关键表达是：

算法比程序更简练，程序比算法更详细。

算法 + 数据结构 = 程序。

可以把算法理解为理想化菜谱，把程序理解为给“机器人厨师”的详细指令。算法只需要说清楚解决问题的主要步骤；程序则必须具体到机器能执行的细节，包括数据如何存放、文件如何打开、异常如何处理、循环边界在哪里、变量怎样更新。

以图片隐写为例，算法可以只写成“读入文本，读入图片，把文本藏进图片，再写出新图片”。但程序必须继续回答：

文本和图片应该按文本模式读入，还是按二进制模式读入？
图片文件的元数据在哪里，像素数据从哪里开始？
一个字符有 8 位，每次隐藏 2 位，需要修改几个字节？
文本长度应该先藏在哪里，否则恢复时如何知道读到哪里结束？

所以，算法更关注“问题求解步骤”，程序更关注“这些步骤如何在计算机上精确落地”。写代码前先想算法，是为了避免一开始就陷入语言细节，而忽略了问题本身的结构。

模块二：图片隐写作为最小算法场景

2.1 任务描述

图片隐写任务的输入是：

hamlet.txt
autumn.bmp

输出是：

doctoredAutumn.bmp

目标是把 hamlet.txt 的全部内容隐藏进 autumn.bmp，并且让新图像和原图像在肉眼观察下没有明显区别。

老师选择这个例子，是因为它既足够具体，又能完整呈现算法和程序的差异。算法步骤看起来很短，但只要真的写程序，就必须处理文件系统、二进制读写、BMP 文件结构、字节数组、循环寻址和最低有效位修改。

2.2 自顶向下的算法步骤

课件给出的文本隐藏算法是：

将文本文件 hamlet.txt 读进变量 t。
将图像文件 autumn.bmp 读进变量 p。
将 hamlet.txt 的文件长度隐藏到变量 p 的 Pixel Array 前 32 个字节。
将 hamlet.txt 的文件内容隐藏到变量 p 的像素阵列剩余字节。
将 p 写到新文件 doctoredAutumn.bmp。

这 5 步已经在算法层面说明了输入、输出和主要操作顺序。但在程序层面还必须补充更多细节，例如：t 和 p 具体是什么数据结构，Pixel Array 从哪个地址开始，隐藏长度为什么需要 32 个字节，一个字符为什么需要 4 个图像字节。

其中“先隐藏文本长度”非常关键。如果只把文本内容连续藏进图片，恢复时并不知道应该取出多少字节。先把 len(t) 写入 Pixel Array 的开头，就相当于给解码程序留下一个边界信息。

2.3 算法简单，程序变复杂的原因

这个例子中，复杂性主要来自两个方面。

第一是数据结构。文件在磁盘上是持久存储的数据，读入内存之后要变成方便定位和修改的形式。本节课使用 bytearray，因为它和现代计算机的 byte-addressable memory 很匹配：文件被看成一串按字节编号的数组，就可以通过下标直接修改某个位置。

第二是文件格式。BMP 图片不是一整块都能随便修改。文件开头包含元数据，描述图片格式、大小等信息；真正的图像数据从 Pixel Array 开始。隐写应该修改像素阵列中的最低有效位，而不是破坏元数据或颜色高位。这样才能既藏入信息，又保持图片视觉上基本不变。

模块三：文件系统、路径与元数据

3.1 文件系统是一棵树

文件是数据和程序在计算机下电后仍然存在的形式。大量文件需要被系统组织起来，这个组织结构就是文件系统。

文件系统可以看作一棵倒着的树：

根目录：树的根，用 / 表示。
叶子节点：普通文件。
内部节点：目录，也可以理解为特殊文件。
父目录：某个节点的上一级目录。
子目录：某个目录的下一级目录。
当前目录：当前 shell 所在的位置，也叫工作目录。
主目录：登录后默认进入的目录。

路径用来定位文件，分为绝对路径和相对路径。

绝对路径从根目录 / 开始写完整路径，例如：

/cs101/Prj2/autumn.bmp

相对路径则从当前目录出发。如果当前目录已经是 /cs101/Prj2/，可以写：

./autumn.bmp

如果当前目录是 /cs101/Prj3/，可以写：

../Prj2/autumn.bmp

常见命令包括：

pwd
cd Prj2
cd ..
cd /

pwd 查看当前工作目录，cd Prj2 进入子目录，cd .. 回到父目录，cd / 回到根目录。如果当前目录已经是根目录，再执行 cd ..，当前目录仍然是根目录，因为根目录的父目录仍可理解为它自己。

3.2 数据与元数据

文件不只有数据本身，还有元数据。元数据就是“关于数据的数据”。

以 autumn.bmp 为例：

数据：真正的像素信息，也就是 Pixel Array。
元数据：文件格式、文件大小、访问权限、修改时间等描述性信息。
BMP 文件内部元数据：File Header 和 Info Header。

课件强调，BMP 文件地址 0 到 53 保存 File Header 和 Info Header，从地址 54 开始才是实际图像数据：

0 ~ 53      BMP File Header / BMP Info Header
54 开始     Pixel Array

图片隐写不能乱改元数据。元数据被破坏后，文件可能无法被图片软件识别；而 Pixel Array 中的低位变化通常只会造成极小的颜色变化，因此更适合隐藏信息。

3.3 系统管理的元数据与访问权限

可以通过：

ls -l autumn.bmp

查看文件名、文件大小、修改时间和访问权限等信息。课件特别提醒，ls -l 里的 l 是小写字母 L，不是大写 I。

课件中的终端输出示例：

$ ls -l autumn.bmp
-rw-r--r-- 1 coder coder 9144630 Oct 27 17:07 autumn.bmp

权限例子：

-rw-r--r--
0644

解释如下：

最左边的 -：表示这是普通文件，不是目录。
owner 权限：rw-，拥有者可读、可写、不可执行。
group 权限：r--，同组用户只可读。
others 权限：r--，其他用户只可读。
r：read，可读。
w：write，可写。
x：execute，可执行。

0644 中，最左边的 0 对应普通文件；后面的 644 可以理解为 owner、group、others 三组权限的八进制表示。

模块四：`bytearray`、BMP 与最低有效位

4.1 为什么用字节数组读文件

Python 读入 BMP 文件：

with open('./autumn.bmp', 'rb') as f:
    p = bytearray(f.read())

文本文件也可以按二进制读入：

with open('hamlet.txt', 'rb') as f:
    t = bytearray(f.read())

其中：

r：read，表示读取。
b：binary，表示二进制模式。
with：负责打开文件，并在代码块结束后自动关闭文件。
bytearray：可修改的字节数组。

如果不写 b，Python 默认按文本模式读入。图片隐写需要精确修改某些字节，所以应按二进制模式读取。把文件读成 bytearray 后，无论原文件是文本、图片、音频还是视频，都可以先看作一串字节，再通过下标定位和修改。

这和计算机内存的 byte-addressable memory 很一致：每个字节都有地址，程序可以根据地址或下标访问它。

4.2 BMP 像素阵列

Pixel 是 Picture Element，也就是图像上的像素点。

Pixel Array 从地址 54 开始。
每个像素有 3 个字节。
每个字节表示一个颜色通道。
BMP 文件中实际存储顺序是 BGR，不是 RGB。

颜色示例：

BGR = (0, 0, 0)       黑色
BGR = (255, 255, 255) 白色
BGR = (0, 0, 255)     红色
BGR = (0, 255, 0)     绿色
BGR = (255, 0, 0)     蓝色

每个颜色通道用一个字节表示，取值范围是 0 到 255。数值越大，对应颜色通道越强。

4.3 最低有效位隐写

最低有效位是 least significant bit，也就是二进制表示中对数值影响最小的位。对于一个颜色通道来说，修改高位会明显改变颜色；修改最低一两位只会让数值产生很小变化，肉眼通常难以察觉。

课件使用的三个常量是：

S = 54   # BMP 文件元数据大小为 54 字节，其后是 Pixel Array
T = 32   # 隐藏文本长度最大所需的像素阵列字节数
C = 4    # 隐藏一个字符所需的像素阵列字节数

解释：

S = 54：BMP 元数据占前 54 个字节，Pixel Array 从 p[54] 开始。
T = 32：文本长度按 64 位整数处理，每次藏 2 位，所以需要 64 / 2 = 32 个图像字节。
C = 4：一个字符按 8 位处理，每次藏 2 位，所以需要 8 / 2 = 4 个图像字节。

隐藏文本长度：

modify(len(t), p, S, T)

也就是把 len(t) 隐藏到：

p[54:86]

课件中的 hamlet.txt 长度例子是 182397 字节。这个长度先被写入 Pixel Array 的前 32 个字节，后续解码时才能知道需要恢复多少文本内容。

把课件里的前半段代码合起来，就是下面这个可复制片段：

S = 54  # BMP 文件元数据大小为 54 字节，其后是 Pixel Array
T = 32  # 隐藏文本长度最大所需的像素阵列字节数
C = 4   # 隐藏一个字符所需的像素阵列字节数

# 读入文本文件
with open('hamlet.txt', 'rb') as f:
    t = bytearray(f.read())

# 读入图像文件
with open('./autumn.bmp', 'rb') as f:
    p = bytearray(f.read())

# 隐藏文本长度到图像字节数组中
# modify() 是课件中的抽象函数，具体实现后续还需要补。
modify(len(t), p, S, T)

4.4 隐藏文本内容与地址计算

对第 i 个字符：

offset = S + T + i * C
modify(t[i], p, offset, C)

这对应计算机指令寻址中的模式：

基址 + 索引 * 比例因子 + 偏移量

以第一个字符 H 为例：

t[0] = 'H' = 72 = 01001000

课件中隐藏第一个字符的代码片段是：

offset = S + T + C * 0
modify(t[0], p, offset, C)

一个字符有 8 位，每次把 2 位藏进一个图像字节的最低两位，所以一个字符需要 4 个 Pixel Array 字节。

第 0 次迭代：

offset = 54 + 32 + 0 * 4 = 86

会修改：

p[86], p[87], p[88], p[89]

第 1 次迭代：

offset = 54 + 32 + 1 * 4 = 90

会修改：

p[90], p[91], p[92], p[93]

这个例子把循环和寻址联系起来了：循环变量 i 表示当前处理第几个字符，i * C 把字符编号转换成字节偏移量，S + T 则跳过 BMP 元数据和文本长度区域。

课件中隐藏整个文本内容的循环可以整理成：

for i in range(len(t)):
    offset = S + T + i * C
    modify(t[i], p, offset, C)

如果把前面读文件、隐藏长度和这里的循环连起来，课件中的核心隐写流程就是：

S = 54  # BMP 文件元数据大小为 54 字节，其后是 Pixel Array
T = 32  # 隐藏文本长度最大所需的像素阵列字节数
C = 4   # 隐藏一个字符所需的像素阵列字节数

with open('hamlet.txt', 'rb') as f:
    t = bytearray(f.read())

with open('./autumn.bmp', 'rb') as f:
    p = bytearray(f.read())

# modify() 是课件中的抽象函数，具体实现后续还需要补。
modify(len(t), p, S, T)

for i in range(len(t)):
    offset = S + T + i * C
    modify(t[i], p, offset, C)

模块五：高德纳的算法定义

5.1 定义主干

高德纳的算法定义可以先抓住主干：

一个算法是一组有限条规则，给出求解特定类型问题的操作序列，并具备下列五个特征。

这个定义不能只背五个特征，更要理解前面的三层含义：

有限条规则：算法的描述本身必须是有限的，不能随着输入规模无限变长。
特定类型问题：算法不是只解决某一个孤立样例，而是解决某一类问题。
操作序列：算法把求解过程拆成一步一步可执行的操作。

例如冒泡排序不是只会排序 12, 35, 99, 18, 76 这一组数，而是可以处理任意给定长度的数组。这才是“求解特定类型问题”。

5.2 五个特征

有限性：算法在有限步骤之后必然终止。
确定性：算法每个步骤都必须精确、严格、无歧义。
输入：算法有零个或多个输入，这些输入可以在开始时给定，也可以在中途动态给定。
输出：算法有一个或多个输出。
能行性：算法中的每个操作都足够基本，原则上一个人可以用笔和纸在有限时间内精确完成。

这里的重点是“可执行”和“可检查”。如果一个步骤本身含糊不清，或者要求完成一个无法保证有限时间内完成的任务，它就不能作为算法中的基本步骤。

5.3 为什么这个定义巧妙

课件评价高德纳定义是简洁、通用、可检验、future-proof。

简洁：它没有依赖某一种编程语言，而是直接抓住“规则”和“操作序列”。
通用：无论是排序、计算斐波那契数，还是图片隐写，都可以放进这个框架里检查。
可检验：可以逐项检查有限性、确定性、输入、输出和能行性。
面向未来：即使进入人工智能时代，程序形态发生变化，我们仍然可以问一个系统的计算过程是否有限、是否明确、是否有输入输出、操作是否可执行。

这也解释了为什么算法思维不是“会写代码”的同义词。代码是某种具体表达，算法定义关注的是背后的计算过程。

模块六：用冒泡排序检查算法定义

6.1 冒泡排序任务

任务：给定 n 个正整数，把它们从小到大排起来。

输入：

待排序数组 A
数组长度 n

输出：

排好序的数组 A

伪代码：

for i = 1 to n - 1
    for j = 1 to n - i
        if A[j] > A[j+1]
            exchange A[j] with A[j+1]

课堂例子：

12, 35, 99, 18, 76

冒泡排序的核心动作是相邻元素比较和交换。每一轮会把当前未排序部分中较大的元素逐步“冒”到后面。这个过程和具体编程语言无关，用 Python、C 或伪代码表达，背后的算法都是同一个。

6.2 为什么冒泡排序符合算法定义

规则有穷性：伪代码只有有限行，行数是 O(1)，不随 n 增长。
步骤有穷性：对任意给定的 n，双重循环都会在有限步后结束。
操作能行性：比较两个整数、交换两个元素都是足够基本的操作。
确定性：每一步比较和交换的条件都明确，没有歧义。
输入输出：输入数组在算法开始前已经在内存中，输出可以理解为同一个数组被排好序后的状态。

这里有一个容易混淆的地方：规则数量有限，不等于执行步骤数量是常数。冒泡排序的伪代码行数是常数级，但执行时间随 n 增长，时间复杂度是 O(n^2)。这正好体现了“程序描述长度”和“运行时间”是两件不同的事。

模块七：确定性、三种有穷性与“什么不是算法”

7.1 确定性：比特精准

确定性要求算法的每一步都必须严格、精确、无歧义。老师用第二周讲过的“比特精准”来解释这一点。

可以作为算法步骤的例子：

比较两个整数大小。

不适合作为严格算法步骤的例子：

比较两条物理线段是否一样长。

整数已经被数字化，比较大小是明确的；物理线段的测量会受到精度、仪器和误差影响，不能直接作为严格算法步骤。除非先把测量规则、精度标准和误差处理方式都形式化，否则“是否一样长”不是比特精准的操作。

7.2 三种有穷性

老师进一步强调，高德纳定义中的有限性至少涉及三种有穷性。

第一，规则有穷性。算法描述本身必须有限，并且不随输入规模增长。图灵机状态转移表的一行可以看作一条规则，程序中的一条语句也可以看作一条规则。对于冒泡排序，n = 10 和 n = 100000 时，算法描述仍然是同一段有限伪代码。

第二，步骤有穷性。给定任意具体输入，算法必须在有限步骤内结束。一个图灵机加法器如果在某些输入上不停机，就违反了这种有限性。

第三，操作能行性。每个基本操作必须能在有限时间内精确完成。例如比较两个整数可以作为基本操作；但“判断哥德巴赫猜想是否为真”不能直接作为某一步基本操作，因为无法保证这一步在有限时间内完成。

7.3 反例：什么不是算法

反例一：求斐波那契数 F(n) 的直线程序。

如果为了计算不同规模的 F(n)，程序行数本身也要跟着 n 增长，那么它违反了规则有穷性。算法应当用有限规则表达一类问题，而不是为每个输入规模单独展开一段越来越长的直线程序。

反例二：不停机的加法图灵机或无穷循环。

如果一个过程在某些输入上永远不停止，就违反了步骤有穷性。它可能是一段程序，也可能是某种计算过程，但不满足高德纳算法定义中的有限性。

反例三：

if 哥德巴赫猜想为真 { ... }

这不是算法中的能行操作。它把一个无法保证有限时间内完成的数学判断塞进了单步操作，因此不满足能行性。

模块八：算法不等于正确算法

8.1 高德纳定义是否要求算法一定正确

高德纳的算法定义没有把“结果一定正确”写进定义。一个过程可能满足有限、确定、有输入、有输出、操作能行，但仍然算错。

因此需要区分三件事：

算法定义解决的问题：这个过程能不能算作算法。
正确性分析解决的问题：这个算法是否真的解决了它声称要解决的问题。
复杂度分析解决的问题：这个算法需要多少时间和空间资源。

这节课的重点不是完整证明某个算法正确，而是先学会度量算法资源消耗，尤其是执行时间。

8.2 和逻辑思维单元的联系

逻辑思维单元讨论图灵机判定问题时，如果机器回答 yes，答案应该真的为 yes；如果回答 no，答案应该真的为 no。这涉及问题和答案之间的正确关系。

高德纳算法定义本身更像是在定义“什么样的操作过程可以叫算法”。它不自动保证算法结果正确，所以在算法学习中还必须额外做正确性分析。

8.3 在人工智能时代的意义

在人工智能时代，这个区分更重要。一个 AI 系统可以有复杂的算法过程，也可以稳定地产生输出，但这不代表输出天然正确。模型可能出现幻觉，程序也可能因为训练数据、目标函数、推理链路或实现细节而产生错误结果。

所以，算法思维不能停在“系统会给答案”。还要继续追问：它的答案是否可靠，错误如何被发现，资源消耗是否可接受。

8.4 输入输出为什么常被伪代码省略

课上还讨论了一个问题：冒泡排序伪代码里没有显式写 input 或 print，那输入输出在哪里？

在算法设计与分析中，通常会暂时忽略冯诺依曼模型中的 I/O 设备，主要关心处理器和内存。因此可以默认：

输入数据在算法开始前已经放在内存中。
输出数据也有一块预先约定的内存空间。
算法执行后，这块空间中保存结果。

以冒泡排序为例，输入数组 A 已经在内存里。排序完成后，还是这个数组 A，但其中元素已经按从小到大排列。于是伪代码不需要像 Python 入门程序那样显式写 input() 或 print()。

模块九：复杂度分析：递归斐波那契

9.1 为什么要做复杂度分析

算法分析关注资源消耗，主要包括：

时间：算法执行需要多久。
空间：算法占用多少内存。

本节课主要讲执行时间。除了问一个算法“是不是算法”“算得对不对”，还要问它“算得快不快”“规模变大以后还能不能用”。

9.2 递归斐波那契代码

def f(n):
    if n == 0 or n == 1:
        return n
    else:
        return f(n - 1) + f(n - 2)


print(f(101))

这里的 print(f(101)) 是课件用来展示指数复杂度会迅速变慢的例子，实际粘贴运行时可以先把 101 改成较小的数观察效果。

调用一次 f(n) 的时间记作：

$$ T(n) $$

当 n 很小时，判断和返回都是常数时间。当 n 较大时，主要时间来自两个递归调用：

$$ T(n-1) $$

和：

$$ T(n-2) $$

因此递推式可以写作：

$$ T(n)=T(n-1)+T(n-2)+O(1) $$

复杂度分析中常先忽略常数项，抓住主要增长趋势：

$$ T(n)\approx T(n-1)+T(n-2) $$

9.3 上下界估计

课件给出的估计是：

$$ 2T(n-2)<T(n)<2T(n-1) $$

上界：

$$ T(n)<2T(n-1)<4T(n-2)<8T(n-3)<\cdots<2^n $$

下界：

$$ T(n)>2T(n-2)>4T(n-4)>8T(n-6)>\cdots>2^{n/2} $$

因此：

$$ 2^{n/2}<T(n)<2^n $$

结论：

$$ T(n)=\Omega(2^{n/2}), \quad T(n)=O(2^n) $$

也就是说，朴素递归斐波那契是指数复杂度。它的问题不是代码难写，而是重复计算太多，同一个子问题会被反复展开。

9.4 指数增长为什么可怕

课上用棋盘放米的故事说明指数增长。

在 10 x 10 棋盘上，第 1 格放 1 粒米，第 2 格放 2 粒，第 3 格放 4 粒，之后每格翻倍。前 10 个格子看起来还不多，课件估算总重量只有二十多克。但如果放满 100 个格子，米粒总数约为：

$$ 2^{101}-1 $$

这个数量已经巨大到不现实。课件用“相当于多个地球质量的米”来强调：指数函数前期增长不显眼，后期会迅速爆炸。

这和递归调用 f(101) 的问题类似。小规模输入时程序还能跑，大规模输入时执行时间会因为指数增长变得不可接受。

模块十：渐进记号：小 o、大 O、Ω、Θ

10.1 为什么需要渐进记号

复杂度分析不是精确计算每台机器上每条指令花了多少秒，而是关注输入规模足够大时，运行时间随规模增长的趋势。为此通常会忽略常数、低阶项和机器差异。

共同假设是：

当 n 足够大时，也就是存在常数 k，当 n > k 时命题成立。

这四个记号分别用来描述两个函数增长阶之间的关系。课件的说法是：g 是 f 的严格上阶、上阶、下阶或等阶。

10.2 四个记号

小 o：严格上界

$$ f(n)=o(g(n)) $$

含义：f(n) 的增长严格慢于 g(n)。形式上可以理解为：

$$ \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 $$

例子：

n^1.58 = o(n^2)
n^1.58 != o(n^1.58)
n^2 != o(n^1.58)

大 O：上界

$$ f(n)=O(g(n)) $$

含义：当 n 足够大时，f(n) 可以被常数倍的 g(n) 上界住。也就是存在常数 c > 0，使得：

$$ f(n)\le c g(n) $$

例子：

n^1.58 = O(n^2)
n^1.58 = O(n^1.58)
n^2 != O(n^1.58)

Ω：下界

$$ f(n)=\Omega(g(n)) $$

含义：当 n 足够大时，f(n) 至少有常数倍的 g(n) 那么大。也就是存在常数 c > 0，使得：

$$ f(n)\ge c g(n) $$

例子：

n^1.58 != Ω(n^2)
n^1.58 = Ω(n^1.58)
n^2 = Ω(n^1.58)

Θ：等阶

$$ f(n)=\Theta(g(n)) $$

含义：

$$ f(n)=O(g(n)) \text{ 并且 } f(n)=\Omega(g(n)) $$

也就是说，f(n) 和 g(n) 在增长阶上相同，只差常数倍。

例子：

n^1.58 != Θ(n^2)
n^1.58 = Θ(n^1.58)
n^2 != Θ(n^1.58)

10.3 等号为什么是单向的

课件提醒：

n^1.58 = O(n^2)
n^1.58 = O(n^3)
但 O(n^2) != O(n^3)

这里的等号不是普通数学等号，更像“属于某个增长阶集合”。n^1.58 = O(n^2) 表示 n^1.58 被 n^2 这个阶上界住；它也当然能被更大的 n^3 上界住。但不能反过来说 O(n^2) 和 O(n^3) 是同一个集合，因为后者包含更多增长更快的函数。

模块十一：构造性与有穷性

11.1 Effectiveness 的拆分

课件表达：

Effectiveness = Constructiveness + Finiteness

也就是：

广义构造性 = 狭义构造性 + 有穷性

这可以和高德纳定义中的“能行性”联系起来。一个计算过程不能只是说“答案存在”，还要说明如何一步一步构造出答案，并且每一步都能在有限资源内完成。

11.2 存在性不等于构造性

课件用香农第二定理作例子：它是存在性定理，不是构造性定理。

存在性定理说明：在某些条件下，存在某种编码方式可以实现无错消息传递。
构造性过程要求：给出具体方法，让我们能够一步一步构造出这样的编码或计算结果。

这一区分很重要。知道某个东西存在，不等于知道怎样把它算出来；知道怎样算，也还要继续问能否在有限时间、有限空间内算出来。

11.3 计算过程是构造性过程

计算过程可以理解为：

输入 -> 第 1 步 -> ... -> 当前步 -> 下一步 -> ... -> 最后一步 -> 输出

计算不是直接“跳”到答案，而是通过一系列明确步骤逐步构造结果。这和算法定义中的“操作序列”一致，也和能行性一致：每一步都必须足够基本，能够被精确执行。

如果某个过程只声称“答案存在”，但没有给出可执行步骤，它还不是计算意义上的构造性过程。如果某个过程有步骤，但步骤数或单步操作无法保证有限完成，也不满足有效计算的要求。

11.4 两类有穷性

课件区分两类资源量：

与问题规模 N 有关：O(f(N))
与问题规模 N 无关：O(1)

存储有穷性通常和问题规模有关。图灵机理论中，纸带可以随问题规模增长，所以空间可以是 O(f(N))。但现实中的一台普通笔记本电脑有固定存储上限，如果把它看成固定容量设备，就是 O(1)，因此不完全等价于图灵机。只有当我们抽象地允许它随着问题规模获得足够大的存储容量时，才更接近图灵机模型。

程序有穷性则要求程序行数与问题规模无关，是 O(1)。循环、递归函数和图灵机有限状态转移表的意义就在这里：用有限规则表达可能很大的计算过程。

本节课总结

12.1 课堂主线复盘

老师先从逻辑思维单元过渡到算法思维单元，说明接下来要关注问题求解过程本身。
接着通过图片隐写任务说明算法和程序的区别：算法可以很简练，程序必须处理更多机器细节。
为了完成图片隐写，需要理解文件系统、路径、元数据、访问权限、bytearray 和 BMP Pixel Array。
在此基础上，老师抽象出高德纳算法定义，强调有限规则、操作序列和五个特征。
冒泡排序用来说明一个算法如何同时满足规则有穷、步骤有穷、确定、能行和有输入输出。
递归斐波那契说明算法描述很短并不代表运行很快，重复递归会导致指数复杂度。
渐进记号帮助我们忽略常数和低阶项，用增长阶描述算法资源消耗。
构造性和有穷性进一步说明：计算过程必须能够一步一步构造结果，并且在有限资源内完成。

12.2 我真正理解了什么

算法不是代码本身，而是对一类问题的有限、明确、可执行的求解步骤描述。
程序比算法更贴近机器，因此必须处理数据结构、文件格式、内存寻址和 I/O 等细节。
复杂度分析关注的是规模增长后的资源趋势，而不是某一次运行的具体秒数。

12.3 我还不清楚什么

modify 函数内部怎样精确地把 2 位写入某个字节的最低两位，还需要自己手写一次。
高德纳定义中的“输出必须有一个或多个”和某些无限运行系统、交互系统之间的关系，还可以继续思考。
构造性和存在性在更多数学定理中的区别，还需要结合后续课程例子理解。

12.4 一句话总结

本节课从图片隐写出发，说明算法和程序的差别；再通过高德纳定义抽象出算法的基本要求；最后用递归斐波那契、渐进记号和构造性/有穷性说明算法不仅要能描述步骤，还要能分析资源消耗和计算边界。

个人 Action Items

手动复盘图片隐写中 S=54, T=32, C=4 的含义。
用自己的话解释一次“算法 + 数据结构 = 程序”。
手动模拟一次冒泡排序，检查它如何满足高德纳定义。
重新推导递归斐波那契的复杂度上下界。
用自己的例子区分 o、O、Ω、Θ。
解释“存在性”和“构造性”的区别。

课件纵览与课堂路径#

本节课的核心问题#

老师的讲课路径#

模块一：从程序转向算法思维#

1.1 为什么进入算法思维#

1.2 算法和程序的区别#

模块二：图片隐写作为最小算法场景#

2.1 任务描述#

2.2 自顶向下的算法步骤#

2.3 算法简单，程序变复杂的原因#

模块三：文件系统、路径与元数据#

3.1 文件系统是一棵树#

3.2 数据与元数据#

3.3 系统管理的元数据与访问权限#

模块四：bytearray、BMP 与最低有效位#

4.1 为什么用字节数组读文件#

4.2 BMP 像素阵列#

4.3 最低有效位隐写#

4.4 隐藏文本内容与地址计算#

模块五：高德纳的算法定义#

5.1 定义主干#

5.2 五个特征#

5.3 为什么这个定义巧妙#

模块六：用冒泡排序检查算法定义#

6.1 冒泡排序任务#

6.2 为什么冒泡排序符合算法定义#

模块七：确定性、三种有穷性与“什么不是算法”#

7.1 确定性：比特精准#

7.2 三种有穷性#

7.3 反例：什么不是算法#

模块八：算法不等于正确算法#

8.1 高德纳定义是否要求算法一定正确#

8.2 和逻辑思维单元的联系#

8.3 在人工智能时代的意义#

8.4 输入输出为什么常被伪代码省略#

模块九：复杂度分析：递归斐波那契#

9.1 为什么要做复杂度分析#

9.2 递归斐波那契代码#

9.3 上下界估计#

9.4 指数增长为什么可怕#

模块十：渐进记号：小 o、大 O、Ω、Θ#

10.1 为什么需要渐进记号#

10.2 四个记号#

小 o：严格上界#

大 O：上界#

Ω：下界#

Θ：等阶#

10.3 等号为什么是单向的#

模块十一：构造性与有穷性#

11.1 Effectiveness 的拆分#

11.2 存在性不等于构造性#

11.3 计算过程是构造性过程#

11.4 两类有穷性#

本节课总结#

12.1 课堂主线复盘#

12.2 我真正理解了什么#

12.3 我还不清楚什么#

12.4 一句话总结#

个人 Action Items#