- Boolean Logic
- Boolean Functions
- Conjunctive and Disjunctive Normal Form
- Karnaugh Maps
- Boolean Algebras



# 布尔逻辑

布尔逻辑是关于在一个“简单”的数学结构中进行计算。
- 复杂计算可以完全由这些简单的计算构建
- 可以帮助识别简化措施，这些简化措施可以在电路级别提高性能
- 可以帮助识别简化措施，这些简化措施可以在编程级别提高表现

## 布尔代数

（两元素）布尔代数被定义为：

集合： B = {0,1}

函数：

- !: B → B
- &&: B² → B
- ||: B² → B 

如下所定义：

- !x = (1 - x)
- x && y = min{x, y}
- x || y = max{x, y}

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

# 布尔函数 Boolean Function

## 定义 Definition

一个n元的布尔函数是一个映射：

$$
f: B^n \rightarrow B
$$

一个布尔函数只能输出1位的0或1（F/T）。

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


# 联结和析取范式 Conjunctive and Disjunctive normal form

- 文字（literal）是一个一元布尔函数。
    - 这是最基本的概念。一个文字就是一个变量或者它的否定。比如，x 和 ¬x（或写作 !x）都是文字。
- 最小项（minterm）和最大项（maxterm）：
    - 最小项是所有变量的AND（与）操作，这些变量可能是原始的，也可能是它们的否定。比如，对于两个变量 x 和 y，x AND ¬y 是一个最小项。
    - 最大项是所有变量的OR（或）操作，这些变量可能是原始的，也可能是它们的否定。比如，x OR ¬y 是一个最大项。
    - 每个最小项在变量取特定值时只有一个输出为真（1），其他都为假（0）；每个最大项在变量取特定值时只有一个输出为假（0），其他都为真（1）。
- 合取范式（CNF, Conjunctive Normal Form）:
    - 合取范式是一个布尔函数的表示方法，它是由一个或多个最大项组成的AND操作。例如，(x OR y) AND (¬x OR ¬y) 是一个合取范式，因为它是两个最大项 x OR y 和 ¬x OR ¬y 的AND操作。
- 析取范式（DNF, Disjunctive Normal Form）:
    - 析取范式也是一个布尔函数的表示方法，它是由一个或多个最小项组成的OR操作。例如，(x AND ¬y) OR (¬x AND y) 是一个析取范式，因为它是两个最小项 x AND ¬y 和 ¬x AND y 的OR操作。

简单来说，合取范式像是多个逻辑或表达式的集合，这些表达式被与在一起；析取范式像是多个逻辑与表达式的集合，这些表达式被或在一起。在布尔逻辑中，任何复杂的表达式都可以用这两种范式之一来表示。



:::note{title="注"}
![image.png](/static/img/545e9f0bf16b40e1908e7c34e6c6c939.image.webp)

由于 (x && (!y) && z) 本身是AND的集合体（即最小项），所以它可以视为一个仅有一个最小项组成的OR操作的析取范式；

每一个文字，都可以视作仅有一个元素的最小项/最大项，所以(x && (!y) && z)可以看作三个仅有一个元素的最大项的AND操作，即合取范式。

因此，(x && (!y) && z)既是析取范式，又是合取范式。
:::

> 每一个布尔函数都可以写成DNF和CNF的形式。


## 标准析取范式 Canonical DNF

定义最小项（Minterm）：给定一个n元布尔函数 $f: Bⁿ → B$，其中 $B$ 是布尔代数的集合 $\{0, 1\}$。对于 $Bⁿ$ 中的每个元素 $b = (b₁, ..., bₙ)$，定义一个最小项 $m_b$。这个 $m_b$ 是几个 $lᵢ(xᵢ)$ 的 AND 运算的结果。每个 $lᵢ(xᵢ)$ 要么是变量 $xᵢ$，要么是它的否定 $!xᵢ$（或 $¬xᵢ$），这取决于 $b$ 中对应的元素 $bᵢ$。如果 $bᵢ$ 是 1，那么 $lᵢ(xᵢ)$ 就是 $xᵢ$；如果 $bᵢ$ 是 0，那么 $lᵢ(xᵢ)$ 就是 $!xᵢ$。

构造DNF公式：对于函数 $f$ 对每个可能的输入 $b$ 产生输出 1 的情况，找出所有对应的最小项 $m_b$。然后，将这些最小项通过 OR 运算（析取）组合起来，形成函数 $f$ 的析取范式公式 $f_DNF$。符号 $∑$ 表示对所有使得 $f(b) = 1$ 的 $b$ 对应的最小项 $m_b$ 进行 OR 运算。

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


:::note{title="注"}
考虑所有可能的输入组合：比如对于两个输入的函数，可能的输入组合有 (0,0), (0,1), (1,0), (1,1)。

找出函数输出为1的所有输入组合：这就是说，我们要找到函数 f 返回1的所有可能情况。

为每个输出为1的情况创建一个最小项：一个最小项是一串用AND连接的输入，如果输入是1我们就直接写下它，如果是0我们就写它的否定形式（比如 !x 或 ¬x）。例如，如果 x=1, y=0 时函数输出为1，那么对应的最小项就是 x AND !y。

将所有这些最小项用OR连接起来：这样做就创建了一个表达式，它精确地描述了函数 f 何时会输出1。如果我们有多个最小项，我们就把它们用OR（||）连接起来，表示这个函数在这些最小项对应的输入情况下都会输出1。
:::

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


# 卡诺图 Karnaugh Maps

制作卡诺图: 根据你的变量个数，画出一个表格。比如两个变量就画2x2的表格，三个变量就画2x4的表格，四个变量则是4x4的表格。

标记变量：表格的行和列要代表所有变量可能的状态组合，这些状态要按格雷码顺序排列，也就是说，每次只变化一个变量的状态。（例：00 - 01 - 11 - 10）

找规律：找出那些可以合并的标记的格子。合并的原则是形成尽可能大的矩形区域，且每个矩形里的单元格数必须是2的幂次个（1, 2, 4...）。这些矩形代表了函数的简化形式。

写出表达式：每一个矩形都对应一个表达式的部分，你只需查看未改变的变量，将它们连接起来。如果变量在矩形中的所有单元格中都是1，就直接写这个变量；如果都是0，就写它的否定形式。如果变量在矩形内的状态既有0也有1，就忽略这个变量。

合并表达式：最后，将所有找到的矩形对应的表达式用OR连接起来，这就是简化后的布尔表达式。

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


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


# 布尔代数 Boolean Algebra

## 性质

交换律（Commutativity）：

- $x ∨ y = y ∨ x$
- $x ∧ y = y ∧ x$

结合律（Associativity）：

- $(x ∨ y) ∨ z = x ∨ (y ∨ z)$
- $(x ∧ y) ∧ z = x ∧ (y ∧ z)$

分配律（Distributivity）：

- $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
- $x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)$

同一律（Identity）：

- $x ∨ 0 = x$
- $x ∧ 1 = x$

补足律（Complementation）：

- $x ∨ x′ = 1$
- $x ∧ x′ = 0$

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


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



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


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


## 对偶性 Duality

对偶性定义:
如果 $E$ 是用变量（比如 $x,y,z$）和常数（0 和 1）以及布尔代数操作（∧ 表示与，∨ 表示或，′ 表示非）定义的表达式，那么 $E$ 的对偶表达式 $dual(E)$ 就是通过将所有的 ∧ 替换为 ∨，将所有的 ∨ 替换为 ∧，将所有的 0 替换为 1，将所有的 1 替换为 0 得到的。

布尔代数的对偶:
如果有一个布尔代数 $(T,∧,∨,′,0,1)$，它的对偶布尔代数是 $(T,∨,∧,′,1,0)$。这里只是交换了与（∧）和或（∨）操作，以及常数 0 和 1 的位置。

对偶性原理定理:
如果你能通过布尔代数的定律证明 $E1=E2$，那么 $dual(E1)=dual(E2)$ 也成立。这个原理告诉我们，一个布尔等式的对偶等式也是成立的。

COMP9020 8.1 Boolean logic

Test started Mar 13, 2024 6:00 PMtoMar 27, 2024 6:00 PM



## 1.1

### Question


Suppose $f:S→S$ and $g:S→S$ are bijections.

Which of the following are true for all such functions?

Select all that apply


- $(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (f^{-1})∘(g^{-1})$
- $(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (g^{-1})∘(f^{-1})$
- $(f;g)^←$ always exists and $(f;g)^← = (f^←);(g^←)$
- $(f;g)^←$ always exists and $(f;g)^← = (g^←);(f^←)$
- None of the above

### Answer

因为是双射，所以反函数一直存在，逆关系一直存在。

令： $(b,c) \in f, (a,b) \in g$

则有：
$$
(a,c) \in f \circ g \\

(b,a) \in g^{-1} \\
(c,b) \in f^{-1} \\

(c,a) \in (f \circ g)^{-1} \\
(c,a) \in g^{-1} \circ f^{-1}

$$

因此，答案为：

- $(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (g^{-1})∘(f^{-1})$
- $(f;g)^←$ always exists and $(f;g)^← = (g^←);(f^←)$


## 1.2

### Question

$$
A = 
\begin{pmatrix}
3 & 1 \\
4 & 1
\end{pmatrix}
$$

Which of the following matrices is $AA - 2A^T$?

### Answer

$$
AA = 
\begin{pmatrix}
3*3 + 1*4 & 3*1 + 1*1 \\
4*3 + 1*4 & 4*1 + 1*1
\end{pmatrix}
=
\begin{pmatrix}
13 & 4 \\
16 & 5
\end{pmatrix}
$$

$$
2A^T = 
\begin{pmatrix}
6 & 8 \\
2 & 2
\end{pmatrix}
$$

因此，答案为：

$$
\begin{pmatrix}
7 & -4 \\
14 & 3
\end{pmatrix}
$$

## 1.3

### Question

Suppose $T(n)$ is defined recursively as:

- $T(0) = 1$
- $T(n) = 3T(n/3) + O(n)$

True or false: $T(n) ∈ O(n)$

### Answer

这里使用主定理。

首先将该式子化成一个简单些的式子：

$$
T(n) = 3T(n/3) + cn
$$

之后，我们可以假设 $n = 3^k$，以此简化操作：

$$
\begin{align*}
    T(n) &= 3(3T(n/9)+cn/3)+cn \\
         &= 9T(n/9) + 2cn \\
         &= 9(3T(n/27)+cn/9)+2cn \\
         &= 27T(n/27)+3cn \\
         &= ... \\
         &=3^kT(1)+kcn \\
         &=n + cnlog_n \\
         &\in O(nlogn)
\end{align*}
$$

因此，答案为：False

## 1.4

### Question

Suppose $f,g:{a,b}^*→{a,b}^*$ are defined recursively as follows:

- $f(λ)=a$
- $g(λ)=b$
- $f(aw) = f(w)g(w)$
- $f(bw) = g(w)f(w)$
- $g(aw)=g(bw)=f(w)$

What is f(bba)?

### Answer

$$
\begin{align*}
    f(bba) &= g(ba)f(ba) \\
           &= f(a)g(a)f(a)
\end{align*}
$$

$$
\begin{align*}
    f(a) &= f(aλ) \\
         &= f(λ)g(λ) \\
         &= ab
\end{align*}
$$

$$
\begin{align*}
    g(a) &= g(aλ) \\
         &= f(λ) \\
         &= a
\end{align*}
$$

$$
f(bba) = f(a)g(a)f(a) = abaab
$$

因此，答案为：abaab

## 1.5

Consider the following code snippet:

```
myFunc(n):
    if n==0:
        return 1
    else:
        return myFunc(n-1) + myFunc(n-1)
```
Which of the following hold with regard to the running time T(n) of this code

Select all that apply

- $T(n) ∈ O(n^2)$
- $T(n) ∈ O(n)$
- $T(n) ∈ O(log n)$
- $T(n) ∈ O(2^n)$
- None of these options

### Answer

假设：`myFunc(n)` 的用时是 $T(n)$，则 `myFunc(n-1)` 的用时是 `T(n-1)` 。

因为return中调用了两次，**所以时间也要计算两倍**！具体可对比1.6。

$$
\begin{align*}
    T(n) &= 2T(n-1) + O(1) \\
         &= 4T(n-2) + 3 \cdot O(1)\\
         &= ... \\
         &= 2^nT(n-n) + \frac{(1+n)n}{2} \cdot O(1) \\
         &= 2^n + \frac{n^2+n}{2} \cdot O(1)\\
         &\in O(2^n)
\end{align*}
$$

因此，答案为：
- $T(n) ∈ O(2^n)$

## 1.6

Consider the following code snippet:

```
myFunc(n):
    if n==0:
        return 1
    else:
        return 2 * myFunc(n-1)
```
Which of the following hold with regard to the running time T(n) of this code

Select all that apply

- $T(n) ∈ O(n^2)$
- $T(n) ∈ O(n)$
- $T(n) ∈ O(log n)$
- $T(n) ∈ O(2^n)$
- None of these options

### Answer

假设：`myFunc(n)` 的用时是 $T(n)$，则 `myFunc(n-1)` 的用时是 `T(n-1)` 。

$$
\begin{align*}
    T(n) &= T(n-1) + O(1) \\
         &= T(n-2) + 2 \cdot O(1) \\
         &= ... \\
         &= T(0) + n \cdot O(1) \\
         &= n \cdot O(1) \\
         &\in O(n)
\end{align*}
$$

因此，答案为：

- $T(n) ∈ O(n)$

## 1.7

### Question


Recall the definition of a valid expression for the proof checker:

- ∅ and U are valid expressions
- Any single letter A-Z or a-z is a valid expression
- If E is a valid expression, then:
    - (E) is a valid expression
    - Eᶜ is a valid expression
- If E₁ and E₂ are valid expressions, then:
    - (E₁ ∩ E₂) is a valid expression
    - (E₁ ∪ E₂) is a valid expression
    - (E₁ \ E₂) is a valid expression
    - (E₁ ⊕ E₂) is a valid expression

Based on the above definition, which of the following are valid expressions?

Select all that apply:

- $Aᶜᶜᶜ$
- $(((U \backslash ∅) \backslash U) \backslash ∅)$
- $((A ∩ B) ∪ (C ∩ (D)))$
- $((A ∪ a) ∩ (B ∪ b) ∩ (C ∪ c))ᶜ$
- $((A1 ⊕ A2)ᶜ)ᶜ$
- $((A ∩ B))$

### Answer

- 选项1
    
    根据规则，一个单字母是有效的表达式。如果 E 是有效表达式，则 Eᶜ 也是有效表达式。因此，对一个单字母连续进行三次补集操作是有效的。
- 选项2
    
    根据规则，∅ 和 𝓤 是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ \ E₂) 也是有效表达式。因此，从 𝓤 中减去 ∅，然后再进行两次相似的操作是有效的。
- 选项3
    
    根据规则，单个字母是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ ∩ E₂) 和 (E₁ ∪ E₂) 也是有效表达式。因此，这个表达式有效。
- 选项4
    
    单字母是有效表达式，(E₁ ∪ E₂) 和 (E₁ ∩ E₂) 也是有效表达式。如果 E 是有效表达式，则 Eᶜ 也是有效表达式。因此，这个表达式有效。
- 选项5
    
    A1和A2不是有效表达式，因此它们的组合也不应该是。
- 选项6
    
    根据规则，单字母是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ ∩ E₂) 也是有效表达式。果 E 是有效表达式，则 (E) 也是有效表达式。因此，这个表达式有效。

因此，答案为：

- $Aᶜᶜᶜ$
- $(((U \backslash ∅) \backslash U) \backslash ∅)$
- $((A ∩ B) ∪ (C ∩ (D)))$
- $((A ∪ a) ∩ (B ∪ b) ∩ (C ∪ c))ᶜ$
- $((A ∩ B))$

## 2.1

### Question

Suppose T(n) is defined recursively as:

- $T(0) = 1$
- $T(n) = 3T(n-3) + O(n)$

True or false: $T(n) ∈ O(2^n)$

### Answer

这里使用主定理。

我们可以假设 $n = 3i$，首先将该式子化成一个简单些的式子：

$$
\begin{align*}
    T(n) &= 3T(n-3) + c_1 \cdot n \\
    T(n-3) &= 3T(n-6) + c_1 \cdot (n-3) \\
    & ... \\
    T(3) &= 3T(0) + c_1 \cdot 3
\end{align*}
$$

我们看到每次递归成本减少 $n$ 的三分之一，但是成本的系数会翻三倍。

$$
\begin{align*}
    T(n) &= 3^iT(0) + c_1 \cdot (n+(n-3) + (n-6) + ... +3 + 0) \\
         &= 3^{\frac{n}{3}} + c_1 \cdot (\frac{n \cdot n}{3} - 3 \cdot (1 + \frac{n}{3}) \cdot \frac{n}{3 \cdot 2}) \\
         &\in O(3^{\frac{n}{3}})
\end{align*}
$$

$3^{\frac{n}{3}}$ 是一个指数函数，但是它要比 $2^n$ 慢很多。

因此，答案为：False

## 2.2

### Question

Consider the following code fragment that works on an array:

```
myFunc(A, lo, hi):
    if lo + 1 >= hi:
        return
    
    j = (lo + hi) / 2
    if A[lo] < A[hi]:            
        myFunc(A, lo, j)
        myFunc(A, j, hi)
    else:
        myFunc(A, j, hi)
        myFunc(A, lo, j)
 
    for i ∈ [lo, hi):
        print(A[i])
```
In terms of n = hi - lo, which of the following hold for the running time T(n) of this code?

- $T(n) ∈ O(n log n)$
- $T(n) ∈ O(2^n)$
- $T(n) ∈ O(1)$
- $T(n) ∈ O(n²)$
- $T(n) ∈ O(n)$
- $T(n) ∈ O(log n)$

### Answer

在递归部分，每次都会把区间分为两部分进行两次递归调用，所以递归树的每一层都有两倍于上一层的调用次数，这种行为在二叉树中是常见的。递归的深度是 O(log n)，因为每次调用都将问题的规模减半。

递归调用中的分支因素是2（因为最坏情况下，两次递归都会执行），但在每层递归中，对区间的打印操作是线性的。这意味着，即使递归深度是 O(log n)，但是每一层递归都要执行 O(n) 的打印操作。所以我们需要将这两者结合起来，得到整体的复杂度。

所以整体复杂度是每层 O(n) 的打印操作乘以 O(log n) 层的递归深度，即 T(n) ∈ O(n log n)。

所以正确的选项是：

- $T(n) ∈ O(n log n)$

## 2.3

### Question

Consider a subset, EXP, of valid expressions (see Question 1.7), defined recursively as follows:

- ∅ and U are elements of EXP
- X,Y,Z ∈ EXP
- If E ∈ EXP, then:
    - (E) ∈ EXP
    - Eᶜ ∈ EXP
- If E₁, E₂ ∈ EXP, then:
    - (E₁ ∩ E₂) ∈ EXP
    - (E₁ ∪ E₂) ∈ EXP

Consider dual: EXP → EXP defined recursively as follows:

- dual(∅) = U
- dual(U) = ∅
- dual(X) = X, dual(Y) = Y, dual(Z) = Z
- If E ∈ EXP, then
    - dual( (E) ) = ( dual(E) )
    - dual( Eᶜ ) = dual(E) ᶜ
- If E₁, E₂ ∈ EXP, then
    - dual( (E₁ ∩ E₂) ) = ( dual(E₁) ∪ dual(E₂) )
    - dual( (E₁ ∪ E₂) ) = ( dual(E₁) ∩ dual(E₂) )
 
What is $dual(((X ∩ Yᶜ) ∪ U))$?

- $((Xᶜ ∩ Y) ∪ ∅)$
- $∅$
- $((X ∪ Yᶜ) ∩ ∅)$
- $((Xᶜ ∪ Y) ∩ ∅)$
- None of the above

### Answer

首先，根据dual( (E) ) = ( dual(E) )，我们将内部最外层的括号提取到外部最外层：

$$
dual(((X ∩ Yᶜ) \cup U)) = (dual((X \cap Y^C) \cup U))
$$

这样，我们提取括号内的dual，相当于变相去除了一层括号。

根据dual( (E₁ ∪ E₂) ) = ( dual(E₁) ∩ dual(E₂) )，我们把两部分分开：

$$
dual((X \cap Y^C) \cup U) = dual((X \cap Y^C)) \cap dual(U)
$$

对于 $dual((X \cap Y^C))$，可以单拎出来继续拆分：

$$
\begin{align*}
    dual((X \cap Y^C)) &= (dual(X) \cap Y^C)) \\
                       &= (dual(X) \cup dual(Y^C)) \\
                       &= (dual(X) \cup dual(Y)^C) \\
                       &= (X \cup Y^C)
\end{align*}
$$

且：dual(U) = ∅

因此答案为：

- $((X \cup Y^C) \cap \empty)$

COMP9020 Quiz 5

- 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