CSP-J/S第一轮常考知识点万字总结

::::epigraph[声明]
本文章内所有内容不保证覆盖考纲，由于篇幅原因，也不会详细介绍每一个算法，仅用于选手们查阅复习。
::::

**CSP-J/S第一轮测试的考察题型是：**

1. 选择题，共 15 题，每题 2 分，共 30 分；
2. 阅读程序题，共计 40 分。一般（特殊标记除外）三道程序题目，判断题每题 1.5 分，选择题每题 3 分；
3. 完善程序题，共计 30 分，选择题目，每题 3 分；一般两道题目。

**主要考点包括但不限于：**

- 计算机知识
  - 计算机历史/名人
  - 操作系统、硬件和软件
  - 网络协议
  - 其他
- 数论
  - 排列组合
  - 进制转换
  - 原码、反码、补码
  - 其他
- 数据结构
  - 栈 *（常考）*
  - 队列
  - 树 *（常考）*
  - 图
- 算法
  - 计算时间（空间）复杂度 *（常考）*
  - 排序算法
  - 二分查找
  - 递归、递推
  - 高精度运算
  - DP
  - 其他

# 计算机基础

## 计算机历史

| 代别   | 年代        | 元件                     | 应用场景           |
| ------ | ----------- | ------------------------ | ------------------ |
| 第一代 | 1940s-1950s | 电子管                   | 科学计算、军事研究 |
| 第二代 | 1950s-1960s | 晶体管                   | 数据处理、事物处理 |
| 第三代 | 1960s-1970s | 集成电路                 | 工业控制的各个领域 |
| 第四代 | 近代        | 大规模、超大规模集成电路 | 各个领域           |
| 第五代 | 1980s-至今  | 智能计算机系统           | 办公、人工智能     |

### 计算机名人

**冯 · 诺依曼**，美国数学家、科学家、现代计算机之父。提出冯诺依曼理论。

冯 · 诺依曼理论：

1. 计算机硬件设备由五部分组成：输入设备、输出设备、存储器、运算器、控制器。

2. 存储程序思想：将程序指令和数据存储在同一存储器中，并通过指令来控制计算机的操作。

----

**图灵**，英国数学家、生物学家、科学家、计算机科学/人工智能之父，首次提出了计算机科学理论。计算机界的最高奖项"图灵奖"以他命名，被称为"计算机界的诺贝尔奖"。

----

## 基础知识

### 计算机系统的构架与工作原理
一个完整的计算机系统由硬件系统和软件系统构成，没有软件系统的硬件称为”裸机“，”裸机“是无法直接使用的。

#### 硬件系统
##### 中央处理器（CPU）

中央处理器（CPU）主要包括运算器、控制器和寄存器。  
**数据**由内存储器（CPU 外部）传给寄存器，又传给运算器，得到计算结果后穿回寄存器。  
**指令**由内寄存器发送给控制器后，控制器将操作命令交给运算器处理，最终由控制器返回给内存储器。

**CPU 的性能指标**

计算机运算速度指计算机每秒执行的指令数，它是一项综合的性能指标。其中 CPU 的主要性能指标包括主频和字长。

##### 存储器
存储器主要用来存储程序及相关数据信息。

**内存储器**

- RAM：随机存储器。断电后，RAM 中的数据随之丢失。
- ROM：只读存储器。断电后，ROM 中的数据保持不变。
- Cache：高速缓冲存储器。

**外存储器**
分为软盘、硬盘、闪存和光盘

#### 软件系统
- 软件系统
  - 系统软件
    - 操作系统
    - 其他系统软件
      - 语言处理系统
      - 数据库管理系统
  - 应用软件
    - 用户编制软件
    - 各种工具软件
    **操作系统** 的主要功能包括：
1. 处理机管理
2. 存储管理
3. 文件管理
4. 设备管理
5. 进程管理
常见的操作系统包括 Windows 系列、UNIX 系列、Linux 系列、macOS 系列等。

### 计算机存储单位

$1 TB=2^{10} GB=2 ^{20} MB=2 ^{30} KB=2 ^{40} B$  
容易得到，  
$1 KiB = 1024 B$  
$1 MiB = 1024 KiB$  
$1 GiB = 1024 MiB$  
$1 TiB = 1024 GiB$  
$1 B (Byte) = 8 b (bit)$

也就是说，$1 Mib = 1024 b = 128 B$，以此类推。

一般情况下，我们省略单位中的 $\text i$。

### 字符编码

字符是人和计算机交互过程中不可缺少的重要信息。要使计算机能处理、存储字符信息，首先也必须用计算机能识别的二进制代码来存储。

`ASCII` 码最初由美国国家标准协会（ANSI）于 1963 年制定，后来得到了广泛采用。`ASCII` 共计 128 个不同的字符，包括了各种英文字母、数字、标点符号以及一些特殊控制字符。

# 数学相关

## 计数问题

计数问题是CSP第一轮认证的“**高频**”知识点，一般出现在单线选择题。

### 加法原理与乘法原理

**加法原理**
适用于“分类”场景，各类方法独立（如选火车或汽车出行）。‌‌

若事件 $A_1$ 至 $A_n$ 互斥且能独立完成任务，分别有 $m_1$ 至 $m_n$ 种方法，则完成该事件的总方法数为：

$$N = m_1+m_2+ \cdots +m_n$$

**乘法原理**

适用于“分步”场景，需步骤连续（如选上衣后再选裤子搭配）。‌‌

如果完成一件任务需要分成 $n$ 个步骤进行，做第1步有 $m_1$ 种方法，做第 $2$ 步有 $m_2$ 种方法⋯ 做第 $n$ 步有 $m_n$ 种方法，那么按照这样的步骤完成这件任务共有不同的方法数为：

$$N = m_1 \times m_2 \times \cdots \times m_n$$

例题：小A同学去吃午饭，去A店在3种不同汉堡里选一种吃，去B店在4种不同汉堡里选一种吃，（答案： $3 × 4 = 12$ 个汉堡）

### 排列组合

#### $A_n^m$与$C_n^m$

n 个不同的元素的全排列有 $n!$ 种方式。

n 个不用的元素中要选择 m 个元素进行全排列有 ${A_n^m} = \frac{n!}{(n-m)!}$，也就是从 $n$ 乘到 $n - m + 1$。

n 个不同的元素种要选择 m 个元素组合不考虑排序有 $C_n^m$ 种，即等于 $\frac{A_n^m}{m!}$。

#### 捆绑法

在做排列的题目时，解决某些元素相邻(要求在一起)问题常用捆绑法：把相邻元素*看作一个整体*，再与其他元素一起排列，同时注意捆绑元素的内部排列。

#### 隔板法/抽空法

插空法，是用来解决某些元素不相邻的排列组合题，即不邻问题。在解决对于某几个元素要求不相邻的问题时，先将其它元素排好，再将指定的不相邻的元素插入已排好元素的间隙或两端位置，从而将问题解决的策略。用这种方法解题思路清晰、简便易懂。

## 进制转换

*整型有4种进制形式：*
**十进制**：由0-9数字组成，逢十进一。是生活中最常见的进制。
**二进制**：由0和1两个数字组成，逢二进一。
**八进制**：由0-7数字组成，为了与其他进制的数字进行区分，通常开头以0作为标记表示八进制。
**十六进制**：由0-9和A-F组成。A代表十进制的11，B代表十进制的12，以此类推。

不同进制的数据有3种书写方式。

1. $10011010_{(2)}, 232_{(8)}, 154_{(10)}, 9 A_{(16)}$ ；
2. $(10011010)_{2}, (232)_{8}, (154)_{10}, (9 A)_{16}$ ；
3. $10011010 B, 232 O, 154 D, 9 A H$ (其中的`B`、`O`、`D`、`H`分别表示二进制、八进制、十进制和十六进制) 。

### 其他进制数与十进制数的转换

#### 二、八、十六进制数转十进制数

二、八、十六进制数转十进制数采用 **“按权展开”** 的方式。

例：  
将 $(1011.101)_{2}$ 转为十进制数。

转换整数部分：  
$(1011)_{2} = 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0$

转换小数部分：  
$(0.101)_{2} = 1\times 2^{-1} + 0\times 2^{-2} + 1\times 2^{-3}$

所以：  
$(1011.101)_{2} = 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0 + 1\times 2^{-1} + 0\times 2^{-2} + 1\times 2^{-3} = 8 + 0 + 2 + 1 + \frac{1}{2} + 0 + \frac{1}{8} = (11.625)_{10}$

#### 十进制数转二、八、十六进制数

十进制数转$n$进制数的方法是：

整数部分：除以$n$取余数，直到商为0，余数反向排列。  
小数部分：乘以$n$取整数，整数从左到右排列。  
例：$100.345_{10} = 1100100.01011{2}$

![计算](https://i-blog.csdnimg.cn/direct/08148aa0fb694e41be39009e1d020100.jpeg)

## 原码、反码、补码

机器数是将*符号*“数字化”的数。一般在计算机中用二进制表示。

### 原码

原码的表示方法非常直观。与真值、十进制数的转换非常方便。

- 对于有符号数而言，规定最高位是符号位，`0` 表示正数，`1`  表示负数，非符号位是该数字绝对值的二进制。

例如，用1字节来存储一个整数时，十进制的 $+36$ 与 $-36$ 的原码表示为：
$$
[+36]_{原}=0010\, 0100
$$
$$
[-36]_{原}=1010\, 0100
$$

### 反码

原码的负数加减法运算复杂，且原码中的0表示不唯一。为了克服原码的缺点，采用反码表示。

- 规定正数的反码与原码一致，负数的反码是对原码按位取反，只是最高位（符号位）不变。

例如，用1字节来存储一个整数时，十进制的 $+36$ 与 $-36$ 的反码表示为：
$$
[+36]_{反}=0010\, 0100
$$
$$
[-36]_{反}=1101\, 1011
$$

### 补码

反码中的0任然表示不唯一。则采用补码。

- 规定正数的补码与原码一致，负数的补码对反码 $+1$ 。

例如，用1字节来存储一个整数时，十进制的 $+36$ 与 $-36$ 的补码表示为：
$$
[+36]_{补}=0010\, 0100
$$
$$
[-36]_{补}=1101\, 1100
$$

## 数论
### 数论四大定理
#### 威尔逊定理
$(p-1)!\equiv -1(mod\,p)$ 和 $p$ 为素数等阶。
#### 费马小定理
若 $p$ 为素数，且 $gcd(a,p)=1$，则 $a^{p-1}\equiv 1(mod\,p)$。
#### 欧拉定理
若 $gcd(a,n)=1$，则 $a^{\varphi (n)}\equiv 1(mod\,n)$。
#### 中国剩余定理（CRT）
求解同余方程，

$$
\left\{\begin{matrix}x\equiv a_1(mod\,m_1)
 \\x\equiv a_2(mod\,m_2)
 \\ \cdots
 \\x\equiv a_n(mod\,m_n)
\end{matrix}\right.
$$

其中 $m_1,m_2,...,m_n$ 均为两两互素的整数。

# 数据结构

## 线性数据结构

### 栈

栈：只能在某一端插入或删除的特殊线性表，即 `FILO`。

我们可以把栈想象成一个单开口的瓶子。例如，我们有元素 `1`，`2`，`3`。我们可以按照顺序依次将它们放入“瓶子”（入栈），此时我们只能拿到最后放入“瓶子”的 `3`，因为 `1` 和 `2` 都在 `3` 的下面，无法得到。当我们拿出（出栈）`3` 时，就可以得到 `2` 了，一次类推。

**典型考题：合法出栈顺序**

方法：依次枚举

例题：入栈顺序`A B C D`，以下出栈顺序**不合法的**是（D）：

- A. `A B C D`(A入栈→A出栈→B入栈→B出栈→C入栈→C出栈→D入栈→D出栈)
 - B. `D C B A`(ABCD入栈→DCBA出栈)
 - C. `B A C D`(AB入栈→BA出栈→C入栈→C出栈→D入栈→D出栈)
 - D. `A D B C`(A入栈→A出栈→BCD入栈→D出栈，此时栈内C在B上面，B无法出栈)

**实现栈的主要方法** 有数组模拟栈和`STL`两种。

**数组模拟栈：**
1. 准备数组 `sta` 和标记变量 `t=0` 。
2. 入栈：将 `sta[++t]` 赋值为新入栈元素。
3. 出栈：`t--;` 。
4. 栈顶元素：`sta[t]`。
5. 判断栈为空：`t==0` 。

**STL栈：**

一、导入库。
例如：
```cpp
#include <stack>
```
二、定义变量。
常见定义方法：`stack<数据类型> 变量名;`
例如：
```cpp
stack<int> sta; // 定义一个元素为整数的栈sta
```
三、栈的常用成员函数。
下表中的`stack`为栈的变量名称。
| 函数            | 作用                                                    |
| --------------- | ------------------------------------------------------- |
| `stack.empty()` | 判断栈是否为空。如果栈为空，返回 `true`，否则返回 `false`。 |
| `stack.size()`  | 返回栈中实际的元素个数。                                |
| `stack.push(e)` | 将元素 `e` 压入栈顶。                                       |
| `stack.top()`   | 访问栈顶元素。                                          |
| `stack.pop()`   | 使栈顶元素出栈。                                        |

### 队列

一种从一端删除(队头)另一端插入(队尾)的特殊线性表，即`FIFO`。

**实现队列的主要方法**有数组模拟队列和 `STL` 两种。

**数组模拟**

1. 准备数组 q，队头标记变量 h=1，队尾标记变量 t=0；
2. 入队：q[++t] = 要入队的元素；
3. 出队：h++;
4. 队首元素：q[h]；
5. 判断为空：t<h。

**STL**

导入：`#include <queue>`
定义：`queue<数据类型>变量名称;`
例如：
```cpp
#include <queue>
queue<int>que;
```
队列常用的成员函数：
| 函数          | 作用                      |
| ------------- | ------------------------- |
| `que.empty()` | 判断队列是否为空。如果为空，返回 `true`，否则返回 `false`。 |
| `que.size()`  | 返回队列中实际的元素个数。                              |
| `que.push(e)` | 将元素 `e` 压入队尾。                                       |
| `que.front()` | 访问队首元素。                                          |
| `que.pop()`   | 使栈队首素出队。                                        |

## 树与图

### 树

树型结构是一类重要的非线性数据结构。直观看来，树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树，也就是说它常是根朝上，而叶朝下的。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。

树的性质（其一）：对于一颗有 $n$ 个节点的树，有 $n-1$ 条边（总节点数-根节点=边数）

#### 二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。对于一颗深度为 $k$ 二叉树，其节点数最多为 $2^{k}-1$，第 $i$ 层节点数最多为 $2 \ ^{i - 1}$。

二叉树树便利：遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。二叉树遍历分**先序遍历、中序遍历、后序遍历**。

1. 先序遍历：根据“**根 - 左 - 右**”的原则，先处理根，再处理左子树，再处理右子树，子树按同样的方法处理。
2. 中序遍历：根据“**左 - 根 - 右**”的原则，先处理左子树，再处理根，再处理右子树，子树按同样的方法处理。
3. 后序遍历：根据“**左 - 右 - 根**”的原则，先处理左子树，再处理右子树，最后输出根，子树按同样的方法处理。

我们只需要知道中序遍历和任意其他一种遍历，即可得知另一种遍历，这也是考试中常考的知识点。如：
前序遍历为`1234`，中序遍历为`2134`，后续遍历为（答案：`2431`）。

#### 哈夫曼编码

首先，将符号按照出现概率由大到小排队，如图1所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。
寻找一个符号的哈夫曼编码，只需从哈夫曼树的根节点开始，往左写`0`, 往右则写`1`.
### 图

[图](https://baike.baidu.com/item/%E5%9B%BE/13018767?fromModule=lemma_sense-layer#viewPageContent)也是一类重要的非线性数据结构。

#### 有向图、无向图
如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

#### 图的相关术语

**度**：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
**入度** 和 **出度**：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
**环**：当从一个节点出发，不走回头路，能回到这个节点，则称它为一个环。
**自环**：若一条边的两个顶点为同一顶点，则此边称作自环。
**路径**：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简*单路径*，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

#### 图的遍历

常见的图遍历方式有两种：**深度优先遍历**和**广度优先遍历**，这两种遍历方式对有向图和无向图均适用。

##### 深度优先遍历

深度优先遍历的遍历过程可以描述为：从图中某个节点出发，访问该节点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余节点，直至图中所有与起始节点有路径相通的节点都被访问完为止。

例如：有个图：
```plain
    a--b--c
   /   |   \
  d -- e    f
```
这时，假设我们从`a`节点开始遍历，那么遍历的大致过程为（以下为递归过程，每个缩进表示为上一层产生的递归）：
- 遍历 a，层数为 1，并将 a 存入标记数组，表示已经遍历过该节点。
  - 遍历 b，层数为 2，并将 b 存入标记数组。
    - 遍历 e，层数为 3，并将 e 存入标记数组。
      - 回到 b，发现 b 已经被标记，没有可以遍历的地方，结束。
    - 遍历 c，层数为 3，并将 c 存入标记数组。
      - 遍历 f，层数为 4，并将 f 存入标记数组。
        - 回到 c，发现 c 已经被标记，没有可以遍历的地方，结束。
     - 回到 b，发现 b 已经被标记，没有可以遍历的地方，结束。
  - 遍历 d，层数为 2，并将 d 存入标记数组。
    - 回到 a，发现 a 已经被标记，返回。
    - 来到 e，发现 e 已经被标记，没有可以遍历的地方，结束。

##### 广度优先遍历

广度优先遍历对图的广度优先遍历方法描述为：从图中某个节点v出发，在访问该节点v之后，依次访问v的所有未被访问过的邻接节点，然后再访问每个邻接节点的邻接节点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有节点都被访问为止。

## 链表

### 单链表

单链表中的节点都有一个指针指向它的后继节点。

$$
\texttt{[元素1]} \to \texttt{[元素2]} \to \texttt{[元素3]} \cdots
$$

在 `a` 的后面插入元素 `p`:

```cpp
p->next = a->next;
a->next = p;
```

删除元素 `p`:

```cpp
a->next = p->next;
delete p;
```

# 双链表

双链表中的每个节点都有两个指针，分别指向它的前驱节点和后继节点。

$$
\texttt{[元素1]}\rightleftharpoons\texttt{[元素2]}\rightleftharpoons\texttt{[元素3]}\cdots
$$

插入 `p`：

```cpp
q->next = p;
q->prev = p->prev;
p->prev->next = q;
p->prev = q;
```

删除 `p`：

```cpp
p->prev->next = p->next;
p->next->prev = p->prev;
// 下面这行可写可不写，建议写上
delete p;
```

## 表达式

### 中缀表达式

同普通表达式。

### 前缀表达式

**前缀表达式**是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家 Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，$- 1 + 2\;{}\,3$，它等价于 $1-(2+3)$。  
将表达式里最低级的运算符作为根，一个进行运算的数按同样的方式作为左孩子，右子树同上；将得到的这棵树进行前序遍历，得到的结果即为此表达式的前缀表达式。

### 后缀表达式

**后缀表达式**（将运算符写在操作数之后），也叫逆波兰式（RPN，或逆波兰记法）。  
将一个普通的中缀表达式转换为逆波兰表达式的一般算法是：首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为存放结果（逆波兰式）的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：

1. 若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈。
2. 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
3. 若取出的字符是“（”，则直接送入S1栈顶。
4. 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
5. 重复上面的1~4步，直至处理完所有的输入字符。
6. 若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。完成以上步骤，S2栈便为逆波兰式输出结果。

不过S2应做一下逆序处理，便可以按照逆波兰式的计算方法计算了。

# 算法
算法是指解题方案的准确而完整的描述。

算法拥有以下特征：
- 有穷性：算法必须能在执行有限个步骤之后终止
- 确切性：算法的每一步骤必须有确切的定义
- 可行性：也称之为有效性
- 输入项：一个算法有输入，以刻画运算对象的初始情况
- 输出项：没有输出的算法是毫无意义的

我们可以通过**时间复杂度**和**空间复杂度**来衡量算法的优劣。

## 时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。  
一个算法的时间复杂度为 $x$ 的算法的时间复杂度可用 $O(x)$ 来表示。  
一般的，当一个算法的时间复杂度更小时，我们认为这个算法更快，在一定程度上更佳。

顺序结构的算法的时间复杂度为 $O(1)$。  
对于循环结构的算法的时间复杂度，我们举个例子：

```cpp
for (int i = 1; i <= n; i++)
```
以上这部分程序的时间复杂度为 $O(n)$。

```cpp
for (int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
```
以上这段程序的时间复杂度为 $O(n\cdot m)$。

**当一个算法有多处可计算时间复杂度时，选择时间复杂度（通常为时间复杂度的次数）最高的一处的时间复杂度作为整个算法的时间复杂度。**
例如：

```cpp
while (m--)
    // 此处的时间复杂度为O(m)
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        // 此处的时间复杂度为O(n²)
```
以上这段程序的时间复杂度为 $O(n^2)$ 。

## 空间复杂度
*空间复杂度在CSP-J中考察频率及难度并不高。*  
算法的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

对于单个变量或常量，它们的空间复杂度都是 $O(1)$  的。  
一维数组的空间复杂度都是 $O(n)$ 的。  
二维数组的空间复杂度都是 $O(n^2)$ 的。

## 排序算法
我们可以通过稳定性、时间复杂度、空间复杂度等信息来比较各个排序算法。

排序算法的 *稳定性* 指相等元素在排序后的相对位置是否保持不变。
即在原序列中，`r[i]=r[j]`，且`r[i]`在`r[j]`之前，而在排序后的序列中，`r[i]`仍在`r[j]`之前，则称这种排序算法是稳定的；否则称为不稳定的。

下表通过展示7种常见（常考）的排序算法的稳定性、时间复杂度和思想来比较这些排序算法。
| 名字     | 稳定性   | 平均时间复杂度 | 最坏时间复杂度 | 类别               |
| -------- | -------- | -------------- | -------------- | ------------------ |
| 插入排序 | 稳定     | $O(n^2)$       | $O(n^2)$       | 基于大小比较的排序 |
| 冒泡排序 | 稳定     | $O(n^2)$       | $O(n^2)$       | 基于大小比较的排序 |
| 选择排序 | 不稳定   | $O(n^2)$       | $O(n^2)$       | 基于大小比较的排序 |
| 归并排序 | 稳定     | $O(n\log n)$   | $O(n\log n)$   | 基于分治策略的排序 |
| 快速排序 | 不稳定   | $O(n\log n)$   | $O(n^2)$       | 基于分治策略的排序 |
| 计数排序 | **稳定** | $O(n)$         | $O(n)$         | 线性排序           |
| 希尔排序 | 不稳定   | $O(n^{3/2})$   | $O(n^{3/2})$   | -                  |

### 插入排序

插入排序的方法是：将待排序的序列视为两部分——已排序部分和未排序部分。初始时已排序部分仅包含第一个元素，然后依次将未排序部分的每个元素插入到已排序部分的正确位置。具体操作时，从后向前扫描已排序序列，将当前元素与已排序元素逐个比较，若已排序元素较大则向后移动一位，直到找到合适位置后插入。这个过程重复进行，直到所有元素都被插入到已排序序列中，最终完成整个序列的排序。其特点是在原数组上进行操作，是一种稳定的原地排序算法。

### 冒泡排序
冒泡排序是最简单和最通用的排序方法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序。

### 选择排序
它的工作原理是第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

### 归并排序
归并排序是一种高效且稳定的排序算法，采用经典的分治策略。其核心思想是将待排序数组递归地分成两半，分别对左右两部分进行排序，左右两部分序列也按照此方法分割后排序，以此类推。然后将两个已排序的子数组合并成一个有序数组。合并过程中，通过比较两个子数组的元素，按顺序依次选取较小（或较大）的元素放入新数组，确保合并后的数组有序。

### 快速排序
快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素 `p`，利用 `p` 将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列变得有序。

### 计数排序
计数排序是一种非比较型的整数排序算法，适用于数据范围不大但数据量较大的场景。它的核心思想是通过统计每个整数在序列中出现的次数，然后根据统计结果直接确定每个元素在排序后数组中的位置。  
简单地说，就是统计每个数字在序列中出现的次数，然后遍历统计数组输出即可。

### 希尔排序
希尔排序是对前面几种基于大小比较的排序的较大改进的排序算法。

希尔排序步骤如下：

1. 选择一个补偿序列， $t_1$ ， $t_2$ ，...， $t_k$ ，其中 $t_i>t_i+1$ ，$t_k=1$。
2. 按步长序列个数k，对序列进行k次排序。
3. 每次排序根据对应的步长$t_i$，将待排序列分割为若干长度为$m$的子序列，分别对各子表进行直接插入排序，仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

## 贪心算法

贪心思想的核心思想是在每一步决策中都选取局部最优解，期望通过一系列的局部最优选择达到全局最优解。 **并非所有问题都能通过贪心算法找到真正的全局最优解**，因为某些情况下这种策略可能会导致次优的结果。在下面我们将详细解释。

贪心并没有一个具体的模板。
贪心适用于在每一步选择中，局部最优解可以导向全局最优解的问题。

**先来看一非常经典的例子：**

*接水问题* ：有 $n$ 人排队接水，第 $i$ 个人需要的节水时间为 $a_i$，如何让所有人的平均等待时长最短？
根据贪心思想，一般地，会让节水时间更短的人排到更前面。这样一来，所有人的节水时间都是最短的。

*区间类贪心* ：即区间覆盖问题。寻找能够完全遮盖某个实数轴区间的最少数目线段集。

*时间安排问题* ：即活动选择问题，给定一组相互冲突的任务列表及其起始结束时间，目标是挑选最多互斥任务执行。

贪心思想的优点：
- 贪心算法通常非常直观和易于理解，解决问题的思路简单直接。
- 贪心算法的时间复杂度通常较低，适合解决某些大规模问题。常见的时间复杂度为 $O(n \log n)$ 或 $O(n)$。
- 贪心算法在诸如图论（如最小生成树、最短路径）、任务调度、资源分配等多个领域有广泛的应用。

贪心思想的缺点：

- 贪心算法并不总能找到问题的最优解。它依赖于每一步的局部最优选择，可能会错过全局最优解。例如，背包问题（经典的DP）的贪心算法不能保证找到最优解。
- 贪心算法只有在某些特定类型的问题（满足贪心选择性质和最优子结构性质）中才能有效工作。对于不满足这些性质的问题，贪心算法无法保证最优解。
- 贪心算法一旦做出选择，就不会回溯或改变决定。因此，一旦做出错误的选择，就无法修正。

## 二分算法
二分算法一般分为**二分查找**和**二分答案**。注意：二分查找和二分答案并不是同一种算法！！！

二分算法一般用于在**单调不减**或**单调不增**的线性表中寻找大于某数的最小值或小于某数的最大值，也可以用于实数的枚举（例如开根号）。  
**单调不减**或**单调不增**是指一个线性表是有序的。  
一般做法是：将一个线性表用中间值一分为二，发现中间值大了，就数值小的一块再一分为二。类似地，如果中间值小了，就把大的那一块一分为二。以此类推。
在下面的介绍中，将用“数组”代替“线性表”。

### 二分查找
**我们首先来看模板：**  
模板1：
```cpp
	while (l < r)
    {
        int mid = l + r >> 1;	//(l+r)/2
        if (/*判断条件*/)  r = mid;    // 判断是否满足性质
        else l = mid + 1;
    }
```
模板2：
```cpp
	while (l < r)
    {
        int mid = l + r >> 1;	//(l+r)/2
        if (/*判断条件*/)  r = mid;    // 判断是否满足性质
        else l = mid + 1;
    }
```
第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。
只要是往左找答案，就用第一个模板，`mid` 不用加一，`r=mid`，`l` 加一；   
只要是往右找答案，就用第二个模板，`mid`要加一，`l=mid`，`r` 要减一;
二分套这两个模板，肯定没错！（只要判断条件写对）

模板3：实数二分
```cpp
	while(r-l>1e-5) //需要一个精度保证
	{
		double mid = (l+r)/2;
		if(/*判断条件*/) l=mid; //或r=mid;
		else r=mid; //或l=mid;
	}
```

### 二分答案
二分算法的区别：
二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

----

什么是二分答案？

答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

当题目中有“**求...最大值的最小 、 求...最小值的最大**”，我们一般优先考虑用二分答案。

**模板：**

- 尽量往左找答案：
  ```cpp
  //求最小的最大值
  int bsearch(int l, int r)
  {
  while (l < r)
  {
      int mid = l + r >> 1;
      if (check(mid)) r = mid;
      else l = mid + 1;
  }
  return l;
  }
  ```
- 尽量往右找答案
  ```cpp
  //求最大的最小值
  int bsearch(int l, int r)
  {
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
  }
  ```

## 动态规划
动态规划，也称 DP，是一种广泛应用于数学、计算机科学和经济学等领域的方法论。其核心思想是通过将复杂问题分解为相对简单的子问题，并存储子问题的解以避免冗余计算，从而显著提高计算效率。

### 主要思想
动态规划常常适用于具有重叠子问题和最优子结构性质的问题。其基本思想是将待求解的问题分解为若干个相关联的子问题，先求解子问题，然后利用这些子问题的解来构造原问题的解。  
对于重复出现的子问题，只在第一次遇到的时候对他进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

通俗来讲，动态规划算法是解决一类具有重叠子问题和最优子结构性质的问题的有效方法。其基本原理是将大问题分解为小问题，通过保存中间结果来避免重复计算，从而提高算法的效率。动态规划方法所耗时往往远少于朴素解法。

动态规划的基本过程包括定义子问题，解决子问题，合并子问题的解来求解原问题。动态规划通常采用自底向上的方式进行，通过迭代计算子问题并存储子问题的解，逐步求解更大规模的问题，直到求解出原问题。

我们做题时需要考虑状态设计（一般情况下，题目要求的答案可以作为状态）和状态转移方程（难点之一），以及优化方法（如滚动数组、最值优化等，难点之一）。

### DP
下面是动态规划的非常经典的问题：
> - 最长公共子序列
> - 背包问题
> - 矩阵链路乘法
> - 硬币找零问题

优点：

- 对于具有重叠子问题和最优子结构性质的问题，动态规划可以显著提高求解效率，避免不必要的重复计算。通过存储和复用子问题的解，动态规划算法能够避免重复计算相同的子问题，从而大大减少计算量。
- 动态规划算法的代码通常比较简洁，易于理解和实现。一旦确定了问题的状态转移方程和边界条件，动态规划算法的代码实现往往非常直观和简洁。

缺点：

- 对于没有重叠子问题和最优子结构性质的问题，动态规划算法可能并不适用，此时需要考虑其他算法。动态规划算法的有效性建立在问题的重叠子问题和最优子结构性质上，如果问题不具备这些性质，那么动态规划算法就无法发挥其优势。
- 动态规划算法的空间复杂度通常较高，需要存储所有子问题的解，以便后续使用。这可能导致算法在处理大规模问题时需要消耗大量的内存空间。在某些情况下，可能需要考虑使用滚动数组或其他优化技巧来降低空间复杂度。滚动数组是一种常用的优化方法，它只保留当前需要使用的子问题解，从而避免了存储所有子问题的解。

# 后记
欢迎各位dalao改正本蒟蒻的错误。

正在渲染内容...