- Motivation
- Standard Approach
- Examples
- Simplifying with Worst Case and Big-O
- Recursive Examples



# 动机 Motivation

算法分析的目的是为了量化和评价算法在处理大量数据时的性能，以便在不同算法之间做出合理选择。通过将算法资源需求表述为输入大小的函数，我们可以更好地理解和预测算法在实际应用中的表现。我们希望比较不同的算法，尤其是那些能够解决任意大规模实例的算法。

# 标准处理流程 Standard Approach

渐近分析：关注的是随着输入规模增加，成本（如运行时间、内存等）如何增长。

标准（默认）方法包括：

- 考虑成本函数的渐近增长。
- 考虑最坏情况（成本最高）的输入。
- 考虑运行时间成本，即基本操作的数量。

还有其他方法，例如：
- 情况分析：考虑算法在所有可能输入上的平均性能。
- 空间（内存）成本：评估算法在运行过程中所需的内存空间。

这些分析方法提供了不同的视角来评估算法的效率，帮助我们了解在不同情况下算法可能的表现。

基本操作被非正式地定义为一个计算步骤，它在计算过程中占用固定数量的计算周期。
一些基本操作的例子包括：

- 算术运算（如加、减、乘、除）
- 两个值的比较
- 赋值操作，即将一个值赋给一个变量
- 访问数组元素
- 调用一个函数
- 返回一个值
- 打印一个字符

在进行算法分析时，应将操作计数为常数因子，$O(1)$，而不是精确数字。这意味着在分析算法的复杂度时，我们不关心具体执行了多少次基本操作，而是关注基本操作的总体趋势。




# 例子 Examples

## 运行时间 vs 执行时间 Running time vs Execution time

- 运行时间是对算法执行时间的一种估计，它基于简化的假设，比如忽略基本操作的具体耗时。
- 在大O记号中通常会隐藏常数因子，这意味着我们关注的是算法性能的增长趋势，而非确切的执行时间。
- 大O记号着重于当输入规模 $n$ 变得非常大时的性能限制。

例如：

一个计算平方的实现，即下文中的 `square(n)`，随着 $n$ 的增大其运行时间会变长。

一个“解决棋类问题”的程序可能会在 $O(1)$ 时间内运行，这意味着不论棋盘的大小，它的解决时间都被认为是常数。这可能指的是对于一个确定的棋局，如固定的开局或结束局面，程序能够立即给出解决方案。

## 具体示例

![image.png](/static/img/9758185f871306b4bf8d5bb32ec6d9ef.image.webp)

![image.png](/static/img/6a960a451552f53408661dd13b9db80e.image.webp)

![image.png](/static/img/aaac1756f0193ecffb96e2406c32dd7c.image.webp)

# 使用最坏情况估计和大O进行问题简化 Simplifying with Worst Case and Big-O

## 最坏情况估计

在本例中，直接使用 $n$ 替换 $i$。

![image.png](/static/img/d576976c80df3b43e2ebbc8a65aecd64.image.webp)

![image.png](/static/img/dbc352c9855da1533dca754078c1fe3e.image.webp)

## 使用大O简化问题

在本例中，没有固定的循环执行的次数，只知道该次数为在0-n中间，即 $O(n)$，那么直接使用 $O(n)$ 替换：

![image.png](/static/img/0efe3ec623bca51194a72b9f275e7867.image.webp)

## 其他方式

最坏情况假设和大O记号的结合可以简化分析，但这种简化可能会导致非最优的界限。为了得到最好的界限，可能需要进行更细粒度的上界分析，或者分析特定情况以找到匹配的下界（大Omega记号）。

大Omega记号用于分析最坏情况的下界，它不是最佳情况分析。也就是说，当我们说某算法的性能是大Omega记号的某个函数时，我们是在说即使在最坏的输入情况下，算法的性能也至少有这么好。

![image.png](/static/img/085297d229c4168e5e59924b4c9af703.image.webp)


# 递归例子 Recursive examples

## 例子 1

![image.png](/static/img/a828d170372aa845aaf60c601c369384.image.webp)

可以假设对于 `fact(n)` 来说，所需要的时间为 $T(n)$，那么：

![image.png](/static/img/e4a942519f84552d75bf14756a7abd93.image.webp)

## 例子 2

![image.png](/static/img/329b4a4808a153a515898532b5d3c380.image.webp)

## 例子 3

![image.png](/static/img/efa7fd46e9f3fc2e9d1e7be734fce87e.image.webp)

## 例子 4

![image.png](/static/img/bd99246c59848952cb7be52d798a05c8.image.webp)

COMP9020 5.1B Algorithmic Analysis

- Functions Recap
- Functional Composition
- Inverse Functions
- Martrices
- Introduction to Big-O Notation



# 函数性质重述 Functions Recap

## 二元关系的性质 Properties of Binary Relations

> 该部分详见 4.1 Relations - 二元关系的性质 Properties of Binary Relations

对于一个二元关系 $R \subseteq S \times T$，它可以有以下若干性质：

- 函数式（Fun） functional：对于每个 $S$ 中的元素 $s$，在关系 $R$ 中至多与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至多映射到一个 $t$。
- 全域性（Tot） total：对于每个 $S$ 中的元素 $s$，在关系 $R$ 中至少与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至少映射到一个 $t$。
- 单射（Inj） injective：对于每个 $T$ 中的元素 $t$，在关系 $R$ 中至多与一个 $S$ 中的元素 $s$ 关联。也就是说不同的 $s$ 映射到不同的 $t$。
- 满射（Sur） surjective：对于每个 $T$ 中的元素 $t$，在关系 $R$ 中至少与一个 $S$ 中的元素 $s$ 关联。也就是说 $T$ 中的每个元素都是某个 $s$ 的映射。
- 双射（Bij） bijective：关系 $R$ 同时满足单射和满射。也就是说，$S$ 到 $T$ 的映射是一对一的（每个 $s$ 只能映射到一个独特的 $t$），并且是覆盖的（$T$ 中的每一个 $t$ 都被 $S$ 中的某个 $s$ 映射到）。

## 函数 Functions

一个函数 $f: S \times T$，本质上是一个满足了函数式（Fun）和全域性（Tot）的一个二元关系 $f \subseteq S \times T$。也就是说，对于所有的 $s \in S$，总能且只能找到一个 $t \in T$，使得 $(s,t) \in f$。

- $f(s)$，指元素 $s$ 经过函数 $f$ 后对应的元素。
- $T^S$，指所有从集合 $S$ 到集合 $T$ 的函数的集合。

### 一些术语符号 Symbols

#### 术语

1. 定义域（domain），包含所有可能的输入，即集合 $S$。
2. 上域（co-domain），包含所有可能的输出，即集合 $T$。
3. 像（image），即值域（range），是函数 $f$ 的实际所有输出，为 $T$ 的子集。

####  符号

1. 定义域：$Dom(f)$
2. 上域：$Codom(f)$
3. 像：$Im(f)$，也可写作 $\{ f(x): x \in Dom(f) \}$

## 单射函数 Injective Functions

单射函数也称一对一函数，需要满足条件：每个元素 $s \in S$ 都映射到一个唯一的元素 $t \in T$ 上，并且不同的元素 $s$ 映射到 $T$ 中不同的元素。

> 注意：单射是一对一的，这意味着诸如绝对值（$y = |x|$）这样的不是单射函数，因为不同的 $s$ 可能会映射到相同的 $t$ 上去。

## 满射函数 Surjective Functions

漫射函数也称“onto”，需要满足条件：如果函数的值域 $Im(f)$ 等于它的上域 $Codom(f)$，那么它就是满射的。

换句话说，如果它的上域中的每一个值都可以被函数通过定义域尽取到，那么我们可以说它就是满射的。

## 有限集上的函数 Functions on Finite Sets

对于一个有限集 $S$，以及一个从 $S$ 到 $S$ 的函数 $f: S → S$，单射和满射的性质是等价的。


# 函数复合 Functional Composition

## 定义 Definition

函数的复合指两个函数按照一定顺序执行，得到一个新的函数。

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

- 函数的复合是满足结合律的。即：

$$
h \circ (g \circ f) = (h \circ g) \circ f
$$

- 对于任何 $g: S \rightarrow T$，复合恒等式并不会改变函数 $g$。即：

$$
id_S(x) = x \text{ for all } x \in S \\
g \circ id_S = g
$$

## 函数自复合 Iteration of Functions

如果一个函数可以映射到它自己，即定义域与上域相等，那么这个函数就可以与自己复合。

$$
f \circ f, f \circ f \circ f, ... \\
f^2, f^3, ...
$$

# 逆函数 Inverse Functions

逆函数是一种特殊的函数，它可以将原函数 $f$ 的输出映射回到原函数的输入。只有当一个函数对于每个输入都有唯一的输出，并且每个输出都来自唯一的输入时（即函数是一一对应的），逆函数才存在。

当关系 $f^{\leftarrow}$ 是一个函数时，也可以被写作 $f^{-1}$。

- 只有当函数 $f$ 是双射时，$f^{-1}$ 才存在。
- 函数的逆 $f^{-1}$ 是撤销函数 $f$ 操作的过程。

## 逆函数的性质

如果函数 $f: S \rightarrow T$，并且 $f^{-1}$ 存在，那么：

$$
f^{-1} \circ f = Id_S \\
f \circ f^{-1} = Id_T
$$

如果函数 $f: S \rightarrow T$ 并且函数 $g: T \rightarrow S$，那么：

$$
g \circ f = Id_S \\
f \circ g = Id_T
$$

此时，$f^{-1}$ 存在，并且等于 $g$。


# 矩阵 Matrices

一个 $m \times n$ 矩阵是一个由m个水平行和n个垂直列构成的矩阵序列。

## 基本矩阵操作 Basic Matrix Operations

一个 $m \times n$ 矩阵 $A$ 的转置写作 $A^T$，是一个 $n \times m$ 的矩阵，原矩阵的第 $i$ 行 $j$ 列的元素，对应了其转置的第 $j$ 行 $i$ 列元素。

- 如果矩阵 $M$ 满足： $M = M^T$，那么该矩阵被称为对称矩阵。

## 矩阵相加 Matrix Sum

矩阵相加的结果，即让各个对应的元素分别相加，组成新的元素。只有行和列的数量完全相同的矩阵之间才可以使用加法。

$$

A=
\begin{bmatrix}
    2 & -1 & 0 & 4 \\
    3 & 2 & -1 & 2 \\
    4 & 0 & 1 & 3
\end{bmatrix}
\ \ \ 
B=
\begin{bmatrix}
    1 & 0 & 5 & 3 \\
    2 & 3 & -2 & 1 \\
    4 & -2 & 0 & 2
\end{bmatrix}
$$
$$
A+B=
\begin{bmatrix}
    3 & -1 & 5 & 7 \\
    5 & 5 & -3 & 3 \\
    8 & -2 & 1 & 5
\end{bmatrix}
$$

矩阵加法之间可以使用交换律和结合律，即：

$$
A + B = B + A \\
(A + B) + C = A + (B + C)
$$

## 标量乘法 Scalar Product

给定一个 $m \times n$ 矩阵 $A = [a_{ij}]$和一个实数 $c$，标量乘积 $cA$ 是一个 $m \times n$ 矩阵，其第 $i$ 行 $j$ 列的元素是 $c \times a_{ij} $。

## 矩阵乘法 Matrix Product

给定一个 $m \times n$ 矩阵 $A=[a_{ij}]$ 和一个 $n \times p$ 矩阵 $B=[b_{jk}]$，它们的乘积是：

一个 $m \times p$ 的矩阵 $C = [c_{ik}]$，且：

$$
c_{ik} = \sum^n_{j=1}a_{ij}b_{jk}
$$

即：矩阵 $C$ 的第 $i$ 行 $k$ 列的元素是通过取 $A$ 的第 $i$ 行与 $B$ 的第 $k$ 列相应的元素乘积之和。

以下是一个2x2的矩阵乘积示例：

![image.png](/static/img/a3e69b5b767e0402c1247d4b5f3b0736.image.webp)

注意：

- $A$ 的行数必须与 $B$ 的列数相同。
- 1xn的矩阵与nx1的矩阵的乘积，通常被称为两个n维向量（n-dimensional vector）的内积(inner product)/点积。
- 矩阵乘法不满足交换律。即：$AB \ne BA$。

![image.png](/static/img/a88a6f507fe8e50f0532c8c760db49be.image.webp)



# 大O符号简介 Introduction to Big-O Notation

“大O符号”是计算机科学中常用的一种数学记号，特别是在算法分析中用于表达算法的时间复杂度或空间复杂度。这个记号捕捉了函数随着输入规模增加的增长趋势。

假设有两个函数 $f$ 和 $g$，它们将自然数集 $N$ 映射到非负实数集 $R_{\ge 0}$。

如果存在某个常数 $n_0 \in N$ 和一个实数常数 $c \gt 0$，使得对所有的 $n \ge n_0$，都有 $g(n) \le c \cdot f(n)$，那么我们说 $g$ 是渐近小于等于 $f$ 的（或者说 $f$ 是 $g$ 的一个渐近上界）。

我们用 $O(f(n))$ 来表示所有渐近小于等于 $f$ 的函数 $g$ 的集合。

![image.png](/static/img/4bdcd50059510402788ce1aad0647f36.image.webp)

### 替代定义 Alternative Definition

如果 $f(n) \in O(g(n))$，当且仅当：

$$
\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} < \infty
$$

### 性质 Properties

给定如下几个函数：

$$
f(n) \in O(g(n)) \\
g(n) \in O(h(n)) \\
j(n) \in O(k(n))
$$

则有如下性质：

1. 传递性

$$
f(n) \in O(h(n))
$$

2. 加法性

$$
f(n) + j(n) \in O(g(n) + k(n))
$$

3. 乘法性

$$
f(n) \cdot j(n) \in O(g(n) \cdot k(n))
$$

![image.png](/static/img/942dead9d432b6f25a59104d2ab41765.image.webp)



## 大Omega符号与渐近下界 Big-Omega Asymptotic Lower Bounds

假设有两个函数 $f$ 和 $g$，它们将自然数集 $N$ 映射到实数集 $R$。

如果存在某个常数 $n_0 \in N$ 和一个实数常数 $c \gt 0$，使得对所有的 $n \ge n_0$，都有 $g(n) \ge c \cdot f(n)$，那么我们说 $g$ 是渐近大于等于 $f$ 的（或者说 $f$ 是 $g$ 的一个渐近下界）。

我们用 $\Omega(f(n))$ 来表示所有渐近大于等于 $f$ 的函数 $g$ 的集合。

![image.png](/static/img/33790d0977698c21747396dbc418d950.image.webp)

## 大Theta符号 Big-Theta Notation

两个函数 $f$ 和 $g$ 具有相同的增长阶（order of growth）或者是渐近等价的（asymptotically equivalent），如果它们以相同的方式随着输入大小的增加而增长。

如果存在某个常数 $n_0 \in N$ 和两个实数常数 $c,d \gt 0$，使得对所有的 $n \ge n_0$，都有 $c \cdot f(n) \le g(n) \le d \cdot f(n)$，那么我们说 $f$ 和 $g$ 具有相同的增长阶。

我们用 $\Theta(f(n))$ 来表示所有具有和 $f$ 相同增长阶的函数 $g$ 的集合。

关于界限：

- 如果 $g \in O(f)$ 或 $g \in \Omega(f)$，我们说 $f$ 是 $g$ 增长阶的上界或下界。
- 如果 $g \in \Theta(f)$，我们称之为紧确界（tight bound），因为它同时为 $g$ 的上界和下界。

### 性质

1. 对称性

$$
g \in \Theta(f) \leftarrow \rightarrow f \in \Theta(g)
$$

2. 由定义出发的包含性

$$
\Theta(f(n)) \subseteq O(f(n)) \\
\Theta(f(n)) \subseteq \Omega(f(n))
$$

3. 由定义出发的交集

$$
\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))
$$

4. 逆反性

$$
\text{if } g \in O(f), \text{ then } f \in \Omega(g)
$$

## 观察值定理 Ovservations

- 对于所有的 $k, \epsilon > 0$:

    $$
    O((log n)^k \subsetneq O(n^{\epsilon}))
    $$
    
    对数的任何多项式级别的增长都会小于任何正指数级别的增长。
    
    $$
    O(n^k) \subsetneq O((1+\epsilon)^n)
    $$

    任何多项式级别的增长都小于指数级别的增长。

- 所有的对数无论底数为何都具有相同的增长阶：

    $$
    O(log_2n) = O(log_3n) = ... = O(log_9n) = ...
    $$

- 不同底数的指数函数具有不同的增长阶：
    $$
    O(r^n) \subsetneq O(s^n) \subsetneq O(t^n) \subsetneq ...
    \text{ for } r < s < t ...
    $$
- 对于多项式函数也是类似的：
    $$
    O(n^k) \subsetneq O(n^l) \subsetneq O(n^m) \subsetneq ...
    \text{ for } k < l < m ...
    $$

## O(1)

$O(1)$ 表示常数时间复杂度，这意味着无论输入规模如何，执行时间（或复杂度）都保持不变。该复杂度通常是理想的，因为它意味着算法的运行时间或所需资源与输入大小无关。

从技术上讲，它可以是任何在两个常数 $c$ 和 $d$ 之间变化的函数，只要这个函数的值不依赖于输入规模 $n$。

COMP9020 5.1A Functions

Test started Mar 6, 2024 6:00 PM to Mar 13, 2024 6:00 PM



## 1.1

### Question

Consider the relation:

$$
R=\{(m,n) \in Z \times Z: m^2 = _{(5)}n^2\}
$$

Which of the following properties does R satisfy?

Select all that apply:

```
- Symmetry (S)
- Transitivity (T)
- Antisymmetry (AS)
- Reflexivity (R)
- Antireflexivity (AR)
```
### Answer

该关系可以被分解为：

$$
R=\{(m,n) \in Z \times Z: m = _{(5)}n \text{ or } m = _{(5)}-n\}
$$

那么，我们可以进一步将之写为：

$$
m = k_1 \times 5 + p \\
n = k_2 \times 5 + p \\
-n = -k_2 \times 5 - p = -k_2 \times 5 + p
$$

- 选项1：对称性。

无论怎么改变顺序，都不影响它们的值，也就不影响两个数的平方除以5后余数相同，因此这个选项是正确的。

- 选项2：传递性。

无论如何传递，都不影响它们的值，也就不影响三个数的平方除以5后余数相同，因此这个选项是正确的。

- 选项3：反对称性。

既然对称性能选，并且它们可以不相等，因此这个选项是不正确的。

- 选项4：自反性。

相同的数的平方除以5后的余数当然相同，因此这个选项是正确的。

- 选项5：反自反性。

显然，$(m,m)$ 是可以存在在这个关系中的，因此这个选项是错误的。

```
- Symmetry (S)
- Transitivity (T)
- Reflexivity (R)
```

## 1.2

### Question

Let $Σ = \{a,b,c\}$ and define a binary relation $R$ on $Σ*$ as follows:

$(w,v) ∈ R$ if and only if $length(w) = length(v)$.

Which of the following is true?

```
- R is neither an equivalence relation nor a partial order
- R is both an equivalence relation and a partial order
- R is a partial order and not an equivalence relation
- R is an equivalence relation and not a partial order
```

### Answer

根据定义，等价需要满足：自反性，对称性，传递性；偏序需要满足：自反性，反对称性，传递性。

- 自反性。

显然， $(x,x) \in R$，因为相同的字符串长度相等。

- 对称性。

显然，$(x,y) \in R$，同时 $(y,x) \in R$，因为顺序改变不影响它们的长度。

- 传递性。

显然，$(x,y) \in R, (y,z) \in R$，能够推断出 $(x,z) \in R$，因为它们的长度完全相同。

- 反对称性。

显然，在上文对称性的例子中，没有强制要求 $x=y$，因此反对称性不成立。

综上所述，我们可以认为，该关系具有等价关系，而不具有偏序关系。

```
- R is an equivalence relation and not a partial order
```

## 1.3

### Question

Consider the poset $\{(1,3,5,9,15,45), \mid \}$

What is glb(15,9)?

```
- 1
- 3
- 5
- 9
- 15
- 45
- Doesn't exist
```

### Answer

我感觉这个题目多少有点问题，应该写：what is glb({15,9})?

满足能够整除这两个数的元素有：1，3

因此最大的下界元素就是3。

```
- 3
```

## 1.4

### Question

True or false:

For all relations $R$, if $R$ is symmetric, then $R = R^←$

### Answer

因为具有对称性，所以对于任何反序的数对，其仍然存在于 $R$ 中。因此答案为：

```
- True
```

## 1.5

## Question

True or false:

For all relations $R$, if $R$ is transitive and antisymmetric, then $R$ is reflexive

### Answer

反例：

$$
R = \{(1,2), (2,3), (1,3)\}
$$

这个关系满足传递性、反对称性，但显然不满足自反性。

因此，答案为：

```
- False
```

## 2.1


Let $Σ = {0,1}$ and consider the relation on $Σ^*$ given by $R = \{(w,v) : length(w) ≥ 2 \times length(v)\}$

Which of the following properties does R satisfy?

Select all that apply:

```
- Antireflexivity (AR)
- Symmetry (S)
- Transitivity (T)
- Reflexivity (R)
- Antisymmetry (AS)
```

### Answer

- 选项1：反自反性。

如果 $x$ 的长度为0，那么 $(x,x)$ 存在与关系 $R$ 中。因此反自反性不成立。

- 选项2：对称性。

显然，长度的二倍关系在调换顺序后并不成立。

- 选项3：传递性。

显然，长度的二倍关系在传递后会变成4倍关系（反正比2倍大），因此总是成立。

- 选项4：自反性。

如果 $x$ 的长度不为0，那么 $(x,x)$ 不存在与关系 $R$ 中。因此自反性不成立。

- 选项5：反对称性。

显然，长度的二倍关系在调换顺序后并不总是成立，除非长度都为0。成立。

综上所述，答案为：

```
- Transitivity (T)
- Antisymmetry (AS)
```

## 2.2

### Question

Which of the following relations (over $ℕ$) are also functions?
Select all that apply:

```
- The | relation
- The ≤ relation
- The = relation
- The relation {(n-1, n) : n ∈ ℕ > 0}
- The relation {}
- The relation {(n, m, n+m) : n,m ∈ ℕ}
```

### Answer

对于集合 $S$ 中的每一个元素 $s$，都有且只有一个元素$t$ 在集合 $T$ 中与之关联。

- 选项1：整除

这显然是不对的。对于这个关系来说，一个输入可以有很多输出。即：一个数可以被很多数整除，因此不满足定义。

- 选项2：小于等于

这显然是不对的。对于这个关系来说，一个输入可以有很多输出。即：一个数可以大于等于很多数，因此不满足定义。

- 选项3：等于

对于这个关系来说，一个输入可以有很多输出。即：一个数可以一个数，因此满足定义。（这是个偏序关系）

- 选项4：某种运算定义

这个关系意为一个数对，该数对内容为$(n-1,n)$。我们每输入一个数 $n$ 就可以得到一个唯一的 $n-1$，因此满足定义。（这是个等价关系）

- 选项5：空函数

它没有输入，没有输出。

- 选项6：某种运算定义

这是个三元组，完全违反了函数的定义。（需要是一个二元关系）

综上所述，答案为：

```
- The = relation
- The relation {(n-1, n) : n ∈ ℕ > 0}
```

## 2.3

### Question

Let $F=ℕ^ℕ$ denote the set of functions from ℕ to ℕ.  Define the relation $R$ on $F×F$ as follows:

$$
(f,g) \in R \text{ if } f(n) \ne g(n) \text{ for only finitely many } n \in ℕ
$$

Which of the following properties does $R$ satisfy?

```
- Antisymmetry (AS)
- Transitivity (T)
- Symmetry (S)
- Reflexivity (R)
- Antireflexivity (AR)
```

### Answer

关系R在函数集F上定义，如果函数f和g在自然数集N上只有有限个n使得f(n) ≠ g(n)，那么f和g就处于这个关系R中。

太抽象的话，想象函数的图像，该关系被描述为两图像仅有有限个交点。

因此，答案为：

```
- Transitivity (T)
- Symmetry (S)
- Reflexivity (R)
```

## 2.4

### Question

Let $F=ℕ^ℕ$ denote the set of functions from ℕ to ℕ.  Define the relation $R$ on $F×F$ as follows:

$$
(f,g) \in R \text{ if } f(n) \le g(n) \text{ for infinitely many } n \in ℕ
$$

Which of the following properties does $R$ satisfy?

```
- Reflexivity (R)
- Transitivity (T)
- Antisymmetry (AS)
- Symmetry (S)
- Antireflexivity (AR)
```

### Answer

关系R在函数集F上定义，如果函数f和g在自然数集N上有无穷个n使得f(n) 小于等于 g(n)，那么f和g就处于这个关系R中。

太抽象的话，想象函数的图像，该关系被描述为f(n)有无穷个点是在g(n)下方的。（有一小段就行，因为可以无限微分）

- 选项1：自反性

显然是成立的，自己肯定无限等于自己。

- 选项2：传递性

想想f,g,h。如果f有一小段小于等于g，g有一小段小于等于h，但这并不代表f有一小段能小于等于h，因为(f,g)、(g,h)关系成立的区间可能是不相同的。因此不成立。

![image.png](/static/img/04406c6d206030bb32e5e85b13d04a0a.image.webp)

- 选项3：反对称性

如果(f,g)存在，那么(g,f)就一定不存在吗？未必，只需要g也有一小段小于f就可以了。不成立。

- 选项4：对称性

如果(f,g)存在，那么(g,f)就一定存在吗？也未必，只需要g永远大于f就可以了。不成立。

- 选项5：反自反性

显然是不成立的，因为自反性成立了。

综上所述，答案为：

```
- Reflexivity (R)
```

## 2.5

### Question


Let $Σ = \{0,1\}$ and define $f:Σ^*×Σ^*→Σ^*$ and $g,h,k:Σ^*→Σ^*$ as follows:

$f(v,u) = uv \text{ for all } v,u ∈ Σ^*$

$g(w) = f(01,w)$

$h(w) = f(10,w)$

$k = g∘h$

What is g(110)?  

What is h(110)? 

What is k(110)?

### Answer

g(110) = f(01, 110) = 11001

h(110) = f(10, 110) = 11010

k(110) = g(h(100)) = g(11010) = 1101001

COMP9020 Quiz 4

Lecture 8: Equivalence Relations and Partial Orders

- Equivalence Relations
- Partial Orders



# 等价关系 Equivalence relations

等价关系是一种捕捉“相等”这一概念的二元关系，它必须满足以下三个属性：

- 自反性。每个对象都应当与自身相等。$(x,x) \in R$
- 对称性。如果 $(x,y) \in R$，那么 $(y,x) \in R$
- 传递性。如果$(x,y) \in R, (y,z) \in R$，那么 $(x,z) \in R$

根据定义，一个二元关系 $R$ 是集合 $ S $上的等价关系，当且仅当它满足自反性（R）、对称性（S）和传递性（T）。

## 等价类 Equivalence Classes

假设 $R \subseteq S \times S$ 是一个等价关系。

集合 $S$ 中的元素 $s$ 的等价类（记作 $[s]$）是所有与 $s$ 相等（根据关系 $R$）的元素的集合。形式上，有：

$$
[s] = \{ t \in S | sRt \}
$$

等价类的概念指，如果你取了集合 $S$ 中的任意一个元素 $s$ 并且找到了所有与它相等的元素 $t$，那么这些元素 $t$ 形成的集合就是 $s$ 的等价类。

$s$ 和 $t$ 在关系 $R$ 下相等当且仅当它们属于同一个等价类，即 $[s]=[t]$。

## 划分 Partitions

集合 $S$ 的划分是一组集合 $S_1,S_2,...S_k$，满足：
- 对于任意不相同的 $i,j$，均有 $S_i \cap S_j=\empty$，即任意两集合不相交。
- 集合 $S$ 是这些集合的并集，即 $S=S_1 \cup S_2 \cup ... \cup S_k$。

如果你有集合 $S = S_1 \cup ... \cup S_k$，那么划分实际上也定义了一个等价关系。每个元素都有属于自己的一个子集 $S_i$。如果想定义两个元素等价，我们可以定义等价关系 $\sim \subseteq S \times S$ 上如下：

- $s\sim t$ 当且仅当 $s$ 和 $t$ 属于同一个子集 $S_i$。

该定义表示 $s$ 与 $t$ 等价。


# 偏序集 Partial Order

如果一个关系 $\preceq$ 在集合 $S$ 上是偏序地，需要满足以下三个条件：

- 自反性。
- 反对称性。
- 传递性。

集合 $S$ 与偏序关系 $\preceq$ 一起构成一个偏序集，简称为poset。

以下是一些常见的偏序集例子：

- $(Z, \le)$
- $(N, |)$

## 哈斯图 Hasse diagram

它是一种表示有限偏序集的图形工具。

- 每个节点代表偏序集 $S$ 中的一个元素。
- 如果 $x \prec y$，并且中间没有元素 $z$ 使得 $x \prec z \prec y$，那么在哈斯图中从 $x$ 向上画一条到 $y$ 的边。

![image.png](/static/img/29e57ae7e391b8de6ed128150e61ba6b.image.webp)

## 元素排序 Ordering Concepts

在偏序集 $(S, \preceq)$ 中，一些基本概念如下：

- 极小元素 Minimal element：在偏序集 $(S, \preceq)$ 中，如果不存在另一个不同的元素 $y$ 满足 $y \preceq x$，那么称 $x$ 为极小元素。
- 极大元素 Maximal element：在偏序集 $(S, \preceq)$ 中，如果不存在另一个不同的元素 $y$ 满足 $x \preceq y$，那么称 $x$ 为极大元素。
- 最小元素 Minimum element：如果对于所有 $y \in S$，都有 $x \preceq y$，那么 $x$ 被称为最小元素。
- 最大元素 Maximum element：如果对于所有 $y \in S$，都有 $y \preceq x$，那么 $x$ 被称为最大元素。

:::note{title="注"}
可能会有多个极小元素或极大元素。

如果最大元素/最小元素存在，那么它们就是唯一的极小元素/极大元素。

极小元素/极大元素在有限偏序集中总是存在，但在无限偏序集中不一定存在。
:::

- 上界 upper bound：如果 $x$ 满足对集合 $A$ 中的所有元素 $a$，都有 $a \preceq x$，那么 $x$ 就是 $A$ 的一个上界。
- 下界 lower bound：如果 $x$ 满足对集合 $A$ 中的所有元素 $a$，都有 $x \preceq a$，那么 $x$ 就是 $A$ 的一个下界。
- 上界集合 set of upper bounds：$ub(A)=\{x: a \preceq x \text{ for all } a \in A\}$
- 下界集合 seet of lower bounds：$lb(A)=\{x: x \preceq a \text{ for all } a \in A\}$
- 最小上界 least upper bound：如果存在，集合 $A$ 的最小上界是上界集合中的最小元素，记作 $lub(A)$。也称上确界。
- 最大下界 greatest lower bound：如果存在，集合 $A$ 的最大下界是下界集合中的最大元素，记作 $glb(A)$。也称下确界。

:::note{title="注"}

要证明一个元素 $x$ 是集合 $A$ 的下确界，你需要证明：

1. $x$ 是 $A$ 的一个下界，即对于所有 $a \in A$，都有 $x \preceq a$。
2. $x$ 是所有下界中最大的元素，即对于所有满足条件的 $y$，都有 $y \preceq x$。

:::

- 格 lattice：对于偏序集 $S, \preceq$，如果对于任意两个元素 $x,y \in S$，它们的上确界 $lub(S)$ 和下确界 $glb(S)$ 都存在，那么称该偏序集为一个格。
- 完备格 complete lattice：对于偏序集 $S, \preceq$，如果对于 $S$ 的任意子集 $A$，它的上确界 $lub(A)$ 和下确界 $glb(A)$ 也都存在，那么称该偏序集为一个完备格。

:::note{title="注"}
有限格总是完备格。因为在有限的情况下，你总是可以通过比较有限个元素来找到最小上界和最大下界。

一个无限格不一定有对其任意无限子集的最小上界或最大下界，尤其是可能不存在一个界限能够涵盖所有元素。
:::

## 全序 Total orders

全序是一种特殊的偏序关系，它除了满足偏序的基本条件（自反性、反对称性、传递性）之外，还满足线性性（Linearity）。这意味着集合中的任何两个元素都可以进行比较：

- 对于所有的 $x,y$，要么出现 $x \le y$，要么出现 $y \le x$。（如果 $x = y$ 则两者都成立）

在有限集合上，所有的全序关系都是“同构”的。这意味着在有限集合上的任意两个全序关系，你总能找到一种方式将一个全序集映射到另一个全序集，保持其顺序结构不变。

在无限集合上，存在多种全序关系的可能性。这表示无限集合上的全序可以有多种不同的结构，不能简单地通过同构关系进行映射。


## 拓扑排序 Topological Sort

对于一个偏序集 $(S, \preceq)$，任何与偏序 $\preceq$一致的全序 $\le$ 都成为拓扑排序。这意味着在偏序关系中如果 $a \preceq b$，那么在拓扑排序中一定有 $a \le b$。

![image.png](/static/img/29414eef40e30e744a95c940d0515ab6.image.webp)


## 良序集 Well-Ordered Sets

良序集是一个偏序集，其中每个子集都有一个最小元素。良序集不要求有最大元素。

自然数集N是一个良序集，每个子集都一定有一个最小元素。

$$
N = \{0,1,2,...\}
$$

良序集是一个重要的数学工具，用于证明程序的终止。因为在良序集中，你可以总是找到一个最小的元素，所以在迭代或递归的情况下，你可以保证每个步骤都是向终止条件靠近，而不是无限进行下去。这在证明算法正确性和计算复杂性时非常有用。

## 笛卡尔积乘积序 Orders for Cartesian products

给定两个偏序集 $(S, \preceq_S)$ 和 $(T, \preceq_T)$，可以定义它们的乘积序如下：

对于 $S \times T$ 中的任意两个元素 $(s,t)$ 和 $(s',t')$，当且仅当 $s \preceq_S s'$，并且 $t \preceq_T t'$ 时，有：

$$
(s,t) \preceq (s',t')
$$

乘积序有以下特点：

- 没有隐含的权重。这意味着在比较两个元素时，$S$ 和 $T$ 中的元素被平等对待。
- 没有对任何组成部分的偏见。乘积序中没有一个方向比另一个更重要。
- 通常，乘积序只是一个偏序，即使是将全序结合起来也是如此。也就是说，即使 $S$ 和 $T$ 上各自的序是全序，它们的乘积也不一定是全序。

乘积序是理解多维数据结构中元素顺序的重要概念，例如，在数据库、多维数组或是在编程语言中处理多个有序集合时非常有用。它允许我们从多个维度组合和比较数据点。

## 笛卡尔积字典序 Orders for Cartesian lexicographic

给定两个偏序集 $(S, \preceq_S)$ 和 $(T, \preceq_T)$，可以定义它们的字典序如下：

对于 $S \times T$ 中的任意两个元素 $(s,t)$ 和 $(s',t')$，当 $s \preceq_S s'$，或者 $s=s', t \preceq_T t'$ 时，有：

$$
(s,t) \preceq_{lex} (s',t')
$$

这意味着先比较第一个元素，如果第一个元素相同，再比较第二个元素。

字典序有以下特点：

- 没有隐含的权重：即没有一个组件比另一个更重要。
- 当组合两个全序时，会给出全序。
- 可以扩展到单词：这意味着可以用来对字符串数组进行排序，比如在字典中排序单词一样。
- 不适合枚举。

字典序是一种重要的序，因为它允许我们对组合数据进行有序排列，这在数据结构、数据库索引以及编程语言中处理字符串时特别有用。它在数学和计算机科学中有广泛的应用。

COMP9020 4.2 Equivalence Relations and Partial Orders

Lecture 7: Relations

- Definition and Examples
- Binary Relations
- Properties of Binary Relations
- Functions




# 定义与例子 Definition and Examples

## 关系 Relations

n元关系（n-ary relation）是n个集合的笛卡尔积的子集，记作：

$$
R \subseteq S_1 \times S_2 \times ... \times S_n
$$

特殊地，当 $n=2$ 时，我们称之为二元关系（binary relation），记作：

$$
R \subseteq S \times T
$$

并且展示相关联的数对时，写作：

$$
(x,y) \in R \ \ \ \ \ or \ \ \ \ \ R(x,y) \ \ \ \ \ or \ \ \ \ \ xRy
$$

笛卡尔积的结果集合 $U=S_1 \times S_2 \times ... \times S_n$ ，称之为 $R$ 的定义域（domain）。如果关系 $R$ 定义域在 $U$ 上，我们就说 $R$ 是 $U$ 上的关系。

## 例子


![image.png](/static/img/684ffb6e0838df2fffb75dca1eb69124.image.webp)


![image.png](/static/img/a1403027b35b1d219cf2699836f206f2.image.webp)

在这个关系中，enrolment显然是学生与课程的对（pair），但应当不是笛卡尔积的全集（因为不太可能每一名学生都会修掉所有的课）。


![image.png](/static/img/2c9479f0acdacecec9c23c0494bb42e3.image.webp)


## 定义关系 Defining Relations

有以下几种方式定义一个关系 $R$ ：

1. 通过明确地列举相关的k元组来定义：这里的k元组指的是在二元关系的情况下的有序对。
2. 通过识别大的笛卡尔积内部的相关元组的属性来定义：这意味着关系可以通过满足特定关系的元组的等式/不等式/关系式等描述。
3. 通过其他关系构建定义：例如通过交集，并集，补集等。

![image.png](/static/img/ca0b1e6a93529b517ee1e5f16a833ef5.image.webp)


![image.png](/static/img/a5d990dc197e36184043db2e8ce6f35b.image.webp)

# 二元关系 Binary relations

在集合S和T之间的二元关系是 $S \times T$ 的子集，即有序对的集合。

特殊的二元关系例子：

- 恒等关系（Identity）：这是对角线关系，也称等价琯溪，定义为 $I = \{(x,x)|x \in S\}$，其中每个元素与自身形成对。
- 空关系（Empty）：不包含任何元素的关系，记作 $\empty$。
- 全域关系（Universal）：包含所有可能有序对的关系，定义为 $U=S \times T$。

## 定义二元关系的方法 Definition binary relations

### 基于集合定义 Set-based definitions

参考：定义关系部分。

### 矩阵描绘 Matrix representation


![image.png](/static/img/5f4d3658fb41e596f5aeeeafb039d50d.image.webp)

### 图像描述 Graphical representation

#### 集合图表示

![image.png](/static/img/d86bc96487e7281616b35f4a4c5b2777.image.webp)

#### 有向图表示

![image.png](/static/img/5e1b1a707374c4340e06f26068f1a15a.image.webp)

## 二元关系操作 Operations for binary relations

### 逆关系 Converse

如果有一个关系 $R \subseteq S \times T$，那么它的逆关系 $R^←$ 定义为：

$$
R^←=\{(t,s) \in T \times S: (s,t) \in R\}
$$

这意味着在逆关系中，每个有序对的元素顺序会被反转。并且，显然有：

$$
(R^←)^←=R
$$

### 复合关系 Composition

如果 $R_1 \subseteq S \times T$ 并且 $R_2 \subseteq T \times U$，那么它们的符合关系 $R_1 ; R_2$ 定义为：

$$
R_1 ; R_2 = \{ (s,u) \in S \times U: \exist t \in T \text{ such that } (s,t) \in R_1,(t,u) \in R_2 \}
$$

复合关系意味着从集合S到U存在一个通过集合T中介的关系路径。


## 关系映像 Relational images

> 想象一下你在学校的学生和他们参加的俱乐部之间有一个列表，这个列表就是一个关系，它告诉你哪个学生参加了哪个俱乐部。
> 
> 现在，如果你想知道某个特定学生参加了哪些俱乐部，你就会查找与这个学生相关的所有俱乐部，这就是关系映像。就像你拿着学生的名字去映射找出他们参加的所有俱乐部。
> 
> 反过来，如果你手头有一个俱乐部的名单，你想找出所有参加这个特定俱乐部的学生，你就会查找与这个俱乐部相关的所有学生，这就是关系预映像。这就像是你从俱乐部的角度出发，反向映射回去找到所有相关的学生。
> 
> 简单来说，关系映像就是从一个集合（比如学生）出发，找到与它们相关联的另一个集合（比如俱乐部）中的成员。而关系预映像则是反过来的操作。

给定关系 $R \subseteq S \times T$，$A \subseteq S$，并且 $B \subseteq T$。

### 关系映像 Relational image

关系映像 $R(A)$ 被定义为：

$$
R(A)=\{ t \in T: (s,t) \in R \text{ for some } s \in A \}
$$

简而言之，$R(A)$ 包含了所有与集合A中的元素通过关系R相关联的T中的元素。

### 关系预映像 Relational pre-image

关系预映像 $R^←(B)$ 被定义为：

$$
R^←(B)=\{ s \in S: (s,t) \in R \text{ for some } t \in B \}
$$

简而言之，$R^←(B)$ 包含了所有能够通过关系R找到与B中元素相对应的S中的元素。


# 二元关系的性质 Properties of Binary Relations

- 函数式（Fun） functional：对于每个 $S$ 中的元素 $s$，在关系 $R$ 中至多与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至多映射到一个 $t$。
    ![image.png](/static/img/b07e9f281d66f46a26a9780a0bde173f.image.webp)
- 全域性（Tot） total：对于每个 $S$ 中的元素 $s$，在关系 $R$ 中至少与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至少映射到一个 $t$。
- 单射（Inj） injective：对于每个 $T$ 中的元素 $t$，在关系 $R$ 中至多与一个 $S$ 中的元素 $s$ 关联。也就是说不同的 $s$ 映射到不同的 $t$。

    ![image.png](/static/img/e7d3bdccb8c5ea4277d6ff8edab77e52.image.webp)
- 满射（Sur） surjective：对于每个 $T$ 中的元素 $t$，在关系 $R$ 中至少与一个 $S$ 中的元素 $s$ 关联。也就是说 $T$ 中的每个元素都是某个 $s$ 的映射。

    ![image.png](/static/img/77254c6d4ba4aa80aeec972f67fa9a89.image.webp)
- 双射（Bij） bijective：关系 $R$ 同时满足单射和满射。也就是说，$S$ 到 $T$ 的映射是一对一的（每个 $s$ 只能映射到一个独特的 $t$），并且是覆盖的（$T$ 中的每一个 $t$ 都被 $S$ 中的某个 $s$ 映射到）。
    
    ![image.png](/static/img/6e8f65ee5fe3c87f6567da6e6d1885ef.image.webp)


## 同一集合上的二元关系性质 Properties of Binary Relations $R \subseteq S \times S$

- 自反性（R）reflexive：对于集合 $S$ 中的所有元素 $x$，都有 $(x,x) \in R$。也就是说，每个元素都与自己本身在关系 $R$ 中有关联。
- 反自反性（AR）antireflexive：对于集合 $S$ 中的所有元素 $x$，都有 $(x,x) \notin R$。也就是说，没有任何元素与自己本身在关系 $R$ 中有关联。
- 对称性（S）symmetric：如果有序对 $(x,y) \in R$，且 $(y,x) \in R$。
- 反对称性（AS）antisymmetric：如果有序对 $(x,y)$ 和 $(y,x)$ 都在 $R$ 中，必须有 $x=y$。
- 传递性（T）transitive：如果有序对 $(x,y)$ 和 $(y,z)$ 都属于关系 $R$，那么 $(x,z) \in R$。

如果某关系具有该性质，意味着这些性质是对关系中的所有元素都成立的。

其中，S，AS，T是条件语句，如果没有任何元素满足“如果”部分的条件，那么属性被认为是成立的。例如，如果在关系中不存在任何两个不同元素 
$x, y$使得 $(x,y)$ 和 $(y,x)$ 同时存在，那么该关系就被视为反对称的。

## 性质的交互 Interaction of Properties

一个关系可以同时是对称的和反对称的。这种情况发生在关系 
$R$ 仅由形如 $(x,x)$ 的有序对组成时，也就是说，除了自反元素之外没有其他元素。在这种情况下，每个元素与自己相关联，但没有不同的元素 $x,y$ 使得 $(x,y)$ 和 $(y,x)$ 同时在 $R$ 中。

关系不能同时是自反的和反自反的，除非集合 $S$ 是空集。这是因为自反性要求集合 $S$ 中每个元素与自己相关联，而反自反性要求没有任何元素与自己相关联，这两个定义是相互矛盾的。

不具有自反性（nonreflexive）或不具有对称性（nonsymmetric）的关系，不等同于反自反的（antireflexive/irreflexive）或反对称的（antisymmetric）关系。这是关系属性的一个重要区别，因为“不具有某属性”（如不自反或不对称）并不一定意味着它具有对应的“反属性”（如反自反或反对称）。

例如，一个关系，如果它对某些元素是自反的，而对其他元素则不是自反的，那么该关系既不是自反的也不是反自反的。


# 数学函数 Functions

一个函数 $f:S→T$，是从集合 $S$ 到集合 $T$ 的一个二元关系 $f \subseteq S \times T$，且满足函数式（Fun）和全域性（Tot）两个属性。也就是说，对于集合 $S$ 中的每一个元素 $s$，都有且只有一个元素 $t$ 在集合 $T$ 中与之关联。

如果 $s$ 唯一关联 $t$，我们用 $f(s)$ 来表示 这个唯一关联的 $t$。

我们用函数集 $T^S$ 表示从 $S$ 到 $T$ 的所有可能的函数的集合。


![image.png](/static/img/7cba91a32f4805b2708cb27fcd5c3477.image.webp)

### 术语

1. 定义域（domain），包含所有可能的输入，即集合 $S$。
2. 上域（co-domain），包含所有可能的输出，即集合 $T$。
3. 像（image），即值域（range），是函数 $f$ 的实际所有输出，为 $T$ 的子集。

###  符号

1. 定义域：$Dom(f)$
2. 上域：$Codom(f)$
3. 像：$Im(f)$，也可写作 $\{ f(x): x \in Dom(f) \}$

### 要点

定义域，上域，方法，三者完全相同的，才能认为是相同的函数。不同的定义域/上域，会影响函数的性质和应用。

当函数 $f$ 同时满足单射和满射（即双射，或称一一对应函数）时， 关系 $f^←$ 才能也是一个函数。

## 双射的性质 Properties of bijections

1. 如果 $f: S → T$ 和 $g: T → U$ 是双射，那么它们的逆函数也是双射的。
2. 函数 $f$ 和 $g$ 的复合 $(f;g): S → U$ 也是双射。
3. 函数 $f$ 与它的逆函数 $f^←$ 的复合等于在 $S$ 上的恒等关系，记作 $f;f^←=I_S$，它包含所有形如 $(x,x)$ 的元素对，其中 $x \in S$。
4. 逆函数 $f^←$ 与函数 $f$ 的符合等于在 $T$ 上的恒等关系，记作 $f^←;f=I_T$，它包含所有形如 $(x,x)$ 的元素对，其中 $x \in T$。

最后两个性质实际上定义了双射函数的逆函数关系，也就是说，你可以通过 $f$ 找到 $T$ 中的每个元素的原像，反过来通过 $g$ 找到 $S$ 中的每个元素的原像，没有遗漏也没有重复。


![image.png](/static/img/c17180b21ba75d2d7ed59d21e8d7149a.image.webp)