数据结构与算法 / 系统课时

函数与映射

函数与映射

本课用函数描述算法中的确定性转换:每个合法输入都对应唯一输出。你将区分定义域、陪域与像,并通过单射、满射、双射和复合函数判断映射是否可逆、是否覆盖目标空间。

学习目标

  • 准确定义函数的定义域、陪域和值域
  • 判断一个函数是否为单射、满射或双射
  • 使用复合函数描述多阶段算法处理流程

函数的本质

函数 f:A→Bf: A \to B 是从集合 AA 到集合 BB 的映射规则。对每个 x∈Ax \in A,必须存在且只存在一个 y∈By \in B 与之对应,记为 y=f(x)y = f(x)。这里 AA 是定义域,BB 是陪域。

“只存在一个输出”并不意味着不同输入必须得到不同输出。两个输入可以映射到同一个值,只要每个输入自己的结果是确定的。反过来,如果某个定义域元素没有结果,或同一个输入同时对应两个不同结果,该规则就不能作为从 AA 到 BB 的总函数。若程序拒绝某些输入,要么缩小定义域,要么把错误显式纳入约定的输出类型。

函数实际产生的所有输出组成像集,也常称值域:

f(A)={f(x)∣x∈A}f(A) = \{f(x) \mid x \in A\}

像集一定是陪域的子集,但不一定等于陪域。区分二者是判断满射的关键。

单射、满射与双射

单射、满射与双射的映射关系

类型 形式化条件 直观含义 重要结果
单射 f(x1)=f(x2)f(x_1) = f(x_2) 可推出 x1=x2x_1 = x_2 不同输入不会碰撞 输出可唯一追溯到输入
满射 对每个 y∈By \in B,存在 x∈Ax \in A 使 f(x)=yf(x) = y 陪域中的元素都被覆盖 像集等于陪域
双射 同时是单射和满射 一一对应且完全覆盖 存在反函数 f−1f^{-1}

对于有限集合,若 f:A→Bf: A \to B 是单射,则 ∣A∣≤∣B∣|A| \le |B|;若是满射,则 ∣A∣≥∣B∣|A| \ge |B|;若是双射,则 ∣A∣=∣B∣|A| = |B|。这些结论常用于证明某种编码不可能无碰撞,或证明两个有限对象集合具有相同数量。

例如,函数 f(x)=x2f(x) = x^2 从整数映射到非负整数时不是单射,因为 f(2)=f(−2)f(2) = f(-2);它也不是满射,因为 2、3 等非负整数不是任何整数的平方。若把陪域改为非负完全平方数集合,它才成为满射。由此可见,只有先明确定义域与陪域,结论才有意义。

复合函数:连接多个处理阶段

设 f:A→Bf: A \to B,g:B→Cg: B \to C,先执行 ff 再执行 gg 得到复合函数:

(g∘f)(x)=g(f(x))(g \circ f)(x) = g(f(x))

复合顺序从右向左读取。只有当前一个函数的输出属于后一个函数的定义域时,复合才有定义。复合函数满足结合律,即 h∘(g∘f)=(h∘g)∘fh \circ (g \circ f) = (h \circ g) \circ f,但通常不满足交换律,g∘fg \circ f 与 f∘gf \circ g 甚至可能无法同时定义。

算法流水线可以自然地表示为复合函数。例如,先把文本标准化,再提取特征,最后分类,可以写成 classify(feature(normalize(text)))。这种表达有助于明确每个阶段的输入输出契约。

反函数与可逆性

只有双射函数才在整个陪域上存在反函数。若 f:A→Bf: A \to B 为双射,则 f−1:B→Af^{-1}: B \to A 满足:

f−1(f(x))=xf^{-1}(f(x)) = x

以及:

f(f−1(y))=yf(f^{-1}(y)) = y

单射但非满射的函数,只能在其像集上定义反向映射;满射但非单射时,可在有限例子中为每个输出选一个原像,得到右逆,但双向都能还原的反函数不存在。工程中所谓“可逆编码”本质上要求编码函数在目标集合上保持双射或至少保存足够信息以恢复原输入。

算法分析中的典型应用

哈希函数通常不是单射,因为较大的键空间被映射到较小的槽位集合,碰撞不可避免。排列可以看作有限集合到自身的双射,因此每个元素恰好出现一次。若按原位置把每个元素一对一移到目标位置,下标映射应为双射。即使元素值重复,也应保留下标的区分。

归约和多阶段数据处理常用复合函数描述。把复杂算法拆成若干职责单一的映射,可以分别验证每一步的定义域、输出约束和复杂度,再分析整体行为。

用有限映射核对可逆性

对一个有限映射,可先检查定义域和陪域约束,再比较像集大小与覆盖率。下例的分类结果按“单射、满射”输出。最后按下标重排并还原,避免靠值识别重复元素。

python
def classify_mapping(domain, codomain, mapping):
    if set(mapping) != domain:
        raise ValueError("映射必须恰好覆盖定义域")
    image = set(mapping.values())
    if not image <= codomain:
        raise ValueError("结果必须属于陪域")
    return len(image) == len(domain), image == codomain

example = {1: "a", 2: "b", 3: "c"}
print(classify_mapping({1, 2, 3}, {"a", "b", "c", "d"}, example))
print(classify_mapping({1, 2, 3}, {"a", "b", "c"}, example))

order = [2, 0, 1]  # 原位置 i 放到新位置 order[i]
values = ["甲", "乙", "甲"]
reordered = [None] * len(values)
for old, new in enumerate(order):
    reordered[new] = values[old]
print(reordered, [reordered[new] for new in order])

同一组键值对在第一个陪域下输出 (True, False),在缩小后的陪域下输出 (True, True)。重排后是 [乙, 甲, 甲],按原位置读取可恢复 [甲, 乙, 甲]。

常见错误

  1. 不写定义域和陪域就判断单射或满射。同一个公式在不同集合上可能得到不同结论。
  2. 把值域与陪域视为同一概念。值域是实际达到的输出,陪域是声明允许的输出集合。
  3. 认为任何函数都有反函数。只有双射才能在整个陪域上定义唯一反函数。
  4. 把复合函数顺序读反。g∘fg \circ f 表示先执行 ff,再执行 gg。
  5. 认为哈希函数应当完全无碰撞。当输入空间大于槽位空间时,单射在数学上不可能成立。

本课练习

  1. 设 f:{1,2,3}→{a,b,c,d}f: \{1, 2, 3\} \to \{a, b, c, d\},且 f(1)=af(1)=a、f(2)=bf(2)=b、f(3)=cf(3)=c。判断它是否为单射、满射和双射,并分别说明理由。
  2. 设 f(x)=x+1f(x)=x+1,g(x)=2xg(x)=2x,计算 (g∘f)(3)(g \circ f)(3) 与 (f∘g)(3)(f \circ g)(3),并据此说明复合函数通常不满足交换律。
  3. 为一个长度为 nn 的数组设计下标重排规则,并写出该规则成为合法双射必须满足的验收条件,不需要给出具体程序。

本课总结

  • 函数要求每个定义域元素恰好对应一个陪域元素,像集不一定等于陪域。
  • 单射控制碰撞,满射控制覆盖,双射同时保证一一对应与可逆性。
  • 复合函数用于连接多阶段转换,其顺序、定义域兼容性和可逆性必须分别检查。

下一课预告

下一阶段将继续使用集合与函数语言学习算法分析中的数量关系、增长速度和证明方法,为渐近分析与正确性证明建立统一表达基础。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

函数与映射

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通