- 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)

COMP9020 4.1 Relations

发布于2022年的reddit：《How much do game developers in Australia make?》。




[原文地址](https://www.reddit.com/r/cscareerquestionsOCE/comments/qaedtk/how_much_do_game_developers_in_australia_make/)

# 正文

> 注：在本文中，OP指发帖人的ID。Posted by u/SaxOps1

嘿，OP，我在2018年底毕业时，也几乎遭遇了和你一样的情况。你可以查看我的发帖记录来确认，因为我很少用这个账户发帖。基本来说，你几乎什么钱都赚不到。游戏开发是一个娱乐领域，然而，如果你想赚钱， 你就不该入局。与其他娱乐媒介不同，非常不幸，除了变成极少数公司的创始人，你甚至没法脱颖而出成为一个明星制作人，成为一个能赚到大钱的极少数人。我认识一些在游戏开发领域工作了十数年的人，他们的收入甚至还没到我刚毕业的时候。话虽如此，还是会有一些公司会支付给你体面的薪水，虽然比不上那些大科技公司，但比起其他工作室的待遇绝对要好一些。我能想到的有ROIT GAMES、ROBLOX和UNITY。但我需要强调，这样的公司少之又少。

这种情况是国际性的。如果你专注于澳大利亚，那么游戏开发在这里几乎等同于死路一条。几年前曾经有一些大的游戏公司，但最后都因为政府削减游戏开发资金等原因而夭折。与大多数国家相比，在这里建立工作室没有经济激励。不过，仍然有一些工作室存在在这里。墨尔本的TANTALUS（如今几乎只移植游戏）、墨尔本的EA工作室（FIREMONKEYS）和悉尼的WarGaming是剩下的几家大工作室。这些公司的职业空缺并不多，而且因为它们基本上是这里唯一的游戏工作室，所以每个想从事游戏开发的人都在竞争这些职位。这里还有一些独立工作室。这些工作室可能会更难进，因为他们没有足够的资金聘用很多开发人员，很可能会聘用自己认识的人。

关于薪资，我有一个来自悉尼WarGaming公司的实习offer（当时他们还没有管培生招聘，当然我想现在应该也很少），2018年底的全职薪资是5万澳币。这与最低工资标准相差无几，这是可是个技术岗位，而且你很可能还需要用它来偿还学生贷款，因此这并不理想。我想在他们那里，初级职位的工资也不会高到哪里去。我在他们之前的两份实习工作的工资都要高得多。

你可以选择到海外从事游戏工作，但这也会非常困难。海外游戏工作室确实会在国际范围内招聘，并为你的签证提供担保，但要记住，这对于刚刚毕业的学生来说不太可能。这些职位的需求量并不大，而且还会有很多本地的申请者。说说我的故事吧，我在维基百科上找到了一份游戏工作室的名单，并向每一家工作室提出了申请。仅有的几家直接回复我说他们不会聘用我——这意味着我的简历甚至没能通过筛选，其他的工作室更是了无音讯。

如果认为你就是为游戏而生的，我不会劝你放弃，但你真的要好好考虑一下。扪心自问，你是否真的想这样做。我曾经和你一样。我从8岁开始做游戏开发，在高中和大学快毕业时利用业余时间编写游戏引擎，痴迷于实现新的花哨的图形算法。我曾经认为我真的会从事游戏开发，因为那是我的使命。我幻想着要么成立自己的工作室，要么先给别人打工，然后再转行做游戏开发。我知道薪水低、工作时间长（项目的关键节点时尤甚），但我不在乎，因为我想做游戏。当我向所有这些工作室提出申请却没有任何回音时，我非常沮丧，我真的没别的工作室可以申请了。随着年龄的增长，我逐渐意识到自己没能进入任何一家工作室是不幸中的万幸。真正的现实是，你很可能会从事一些并不光彩、没有影响力或没有乐趣的工作。在项目的要紧时间，你的生活中最要命的东西可能就是你手头上的工作。此外，工作可能会让你失去所有对生活的乐趣。我目前在悉尼一家科技公司从事渲染技术工作，收入是悉尼一家游戏公司的10倍，我正在做的项目也与我喜欢的游戏开发的一些东西有些吻合。扪心自问一下，你是否愿意付出极大的代价从事游戏开发工作，因为这基本上就是走上这条路的必然结果。对我来说，我无法回答 "是"。

这篇文章真的很长，但我写这篇文章就像是在和3年前的自己对话。如果你有任何问题，请随时联系我。

# 原文

Hey OP, posting here because I was in the exact same situation when I graduated end of 2018 (you could probably check my posts on here to verify that since I don't post much on this account). Basically the gist of it is you'd get barely anything. Game dev is an entertainment field, you should not go into it if you want to make money. Unfortunately, unlike other entertainment mediums, there's not even a way to stand out like a celebrity and have at least a very small portion of the people making a lot (aside from founders in a very few of the companies). For context, I know people that have worked 10+ years in gamedev and still make less than I did as a grad. That being said, there are some companies that will pay somewhat decently. You still won't be making as much as you would at a normal big tech company but it's definitely better. Some that come to mind are riot games, roblox, unity. I want to stress that these companies are few and far between.

That's internationally though, if you're focusing on Australia game development is pretty much dead here. There used to be a few big name companies years ago but they all died after government funding cuts for game development here among other things. There's no real financial incentive to setup a studio here compared to most other countries. There's still a few studios around though. There's tantalus in Melbourne (which pretty much just do ports these days), an EA studio Melbourne working on mobile apps/engines (Firemonkeys) and WarGaming in sydney to name the big ones left. There aren't many job openings at these companies and since they're basically the only game studios here, everyone that wants to work in game dev is competing for them. There's also a few indie studios here too. These would likely be even harder to get into as they don't really have the funding for many developers and likely will hire people they know.

In terms of salaries, for some tangible numbers, I had an internship offer from wargaming sydney (they weren't offering grad roles at the time and I think it's very rare that they do) for 50k full time at the end of 2018. That's not that far off minimum wage, which for a skilled position and one you likely will be using to pay off your student debt, isn't ideal. I assume a junior role wouldn't be much more with them. Both internships I had before them paid a lot more.

You can take the route of moving overseas to work on games, but it too is going to be insanely hard. Overseas game studios do hire internationally and sponsor visas, but keep in mind that it's very unlikely for a grad role. These roles are not really in demand and will have a lot of local applicants. To give you my story, I went through a wikipedia list of game studios and applied to every single one. The only ones that got back to me said they wouldn't hire me (didn't even make it pass the resume screening for any of them) and the rest I heard nothing from.

If your passion is working on games for a living, I'm not going to dissuade you from doing it but really do think about it. Ask yourself if you really want to do it. I used to be like you. I started game dev when I was 8, wrote game engines in my spare time towards the end of highschool and uni, was obsessed with implementing the new fancy graphics algorithms, ect. I thought I was really committed to doing game dev and it was my calling. I was either going to start my own studio or start by working for someone else and then pivot to it. I knew about the bad pay and longer hours (crunch time is real) but I didn't care because I wanted to work on games. I was so depressed when I was hearing nothing back from applying to all these studios (I literally ran out of places to apply). As I've gotten older I've realised it was a blessing in disguise that I never got into any of them. The reality is you'd likely be working on things that aren't that glamorous or impactful or fun. It's going to be working on what's the most required thing for the project at the given time. Furthermore, having a job will probably suck all enjoyment you get out of it. I'm currently working at a Sydney tech company on rendering tech and making 10x minimum what I would at a game company in sydney. The project I'm on also somewhat aligns with some of the things I loved about game development. Really ask yourself if you would want to be paying large sums of money to be working in gamedev, since that's essentially what you would be doing. For me I can't answer yes to that.

This is really long, but I'm basically writing this as though I'm talking to myself from 3 years ago. If you have any questions feel free to reach out.