## 介绍
**Markdown** 是一种轻量级标记语言，它允许你使用易于阅读、易于编写的纯文本格式来创建富文本内容。通过简单的标记符号，如井号（\#）、星号（\*）和下划线（\_），可以快速地添加标题、粗体、斜体、链接等基本样式，从而使得排版和格式化变得非常简单。



这里一些[基础语法](https://www.markdownguide.org/basic-syntax/)或者[拓展语法](https://www.markdownguide.org/extended-syntax/)就不再介绍，可以直接看官方文档
- 基础语法：https://www.markdownguide.org/basic-syntax/
- 拓展语法：https://www.markdownguide.org/extended-syntax/
 
本篇主要讲一下数学公式，MarkDown支持使用 [LaTeX](https://zh.wikipedia.org/wiki/LaTeX) 语法编写数学公式，常见的数学符号和操作都可以再MarkDown进行输入。

### 表达式

使用 $ 符号包裹起来表示行内数学公式，使用 $$ 符号包裹起来表示独立数学公式块。例如：

```
$E=mc^2$
```
$$
E=mc^2
$$

```
$$ 
\begin{aligned}
\frac{\partial u}{\partial t} + u \frac{\partial u}{\partial x} = - \frac{1}{\rho} \frac{\partial p}{\partial x} + \nu \frac{\partial^2 u}{\partial x^2} \\
\frac{\partial \rho}{\partial t} + \frac{\partial (\rho u)}{\partial x} = 0
\end{aligned} 
$$
```
$$ 
\begin{aligned}
\frac{\partial u}{\partial t} + u \frac{\partial u}{\partial x} = - \frac{1}{\rho} \frac{\partial p}{\partial x} + \nu \frac{\partial^2 u}{\partial x^2} \\
\frac{\partial \rho}{\partial t} + \frac{\partial (\rho u)}{\partial x} = 0
\end{aligned} 
$$

在行间公式中，可通过 `\\` 强制分行，也可在适当位置使用 `\quad`、`\qquad` 等命令控制行间距离。

### 希腊字母

支持输入希腊字母，例如：

```
$\alpha, \beta, \gamma, \delta, \epsilon, \varepsilon, \zeta, \eta, \theta, \vartheta, \iota, \kappa, \lambda, \mu, \nu, \xi, o, \pi, \varpi, \rho, \varrho, \sigma, \varsigma, \tau, \upsilon, \phi, \varphi, \chi, \psi, \omega$
```
$$
\alpha, \beta, \gamma, \delta, \epsilon, \varepsilon, \zeta, \eta, \theta, \vartheta, \iota, \kappa, \lambda, \mu, \nu, \xi, o, \pi, \varpi, \rho, \varrho, \sigma, \varsigma, \tau, \upsilon, \phi, \varphi, \chi, \psi, \omega
$$

### 上下标

使用 `_` 和 `^` 分别表示下标和上标，例如：

```
$x_1, x_2, ..., x_n$

$a^{b^c}$ 或 $a^{bc}$
```
$$
x_1, x_2, ..., x_n \qquad a^{b^c}  \qquad a^{bc}
$$

可以通过 `{}` 包含起来实现多位数的上下标，例如：

```
$ {X}_{abc}x^{def} $
```
$$
 {X}_{abc}x^{def} 
$$

### 分式

使用 `\frac{numerator}{denominator}` 表示分式，例如：

```
$\frac{1}{2}$
```

$$
\frac{1}{2}
$$
### 开方

使用 `\sqrt[n]{expression}` 表示开 n 次方，例如：

```
$\sqrt{x}, \sqrt[3]{x}, \sqrt[n]{x}$
```

$$
\sqrt{x},\qquad \sqrt[3]{x},\qquad \sqrt[n]{x}
$$


### 求和、求积

使用 `\sum_{lower}^{upper} expression` 表示求和，使用 `\prod_{lower}^{upper} expression` 表示求积，例如：

```
$\sum_{i=0}^{n} i^2$

$\prod_{i=1}^{n} i$
```

$$
\sum_{i=0}^{n} i^2 \qquad \quad  \prod_{i=1}^{n} i
$$


### 极限

使用 `\lim_{x \to a} expression` 表示极限，例如：

```
$\lim_{x \to 0} \frac{\sin x}{x} = 1$
```
$$
\lim_{x \to 0} \frac{\sin x}{x} = 1
$$

### 积分

使用 `\int_{lower}^{upper} expression` 表示积分，例如：

```
$\int_{a}^{b} f(x) dx$
```
$$
\int_{a}^{b} f(x) dx
$$


还可以加入微分符号：

```
$\int_{a}^{b} \frac{\partial f(x)}{\partial x} dx$
```

$$
\int_{a}^{b} \frac{\partial f(x)}{\partial x} dx
$$

### 矩阵

使用 `\begin{matrix} ... \end{matrix}` 表示矩阵，例如：

```
$\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}$
```
$$
\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}
$$



可以使用括号、中括号、大括号来表示不同的矩阵：

```
$\left(\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}\right)$
```
$$
\left(\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}\right)
$$
```
$\left[\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}\right]$
```

$$
\left[\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}\right]
$$
```
$\left\{\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}\right\}$
```

$$
\left\{\begin{matrix}
1 & 2 \\
3 & 4
\end{matrix}\right\}
$$


### 分段函数

使用 `\begin{cases} ... \end{cases}` 来表示分段函数，例如：

```
$$ f(x) =
\begin{cases}
0 & x\leq 0 \\
x & 0<x<1 \\
1 & x\ge
1 \end{cases} $$
```

$$
f(x) =
\begin{cases}
0 & x\leq 0 \\
x & 0<x<1 \\
1 & x\ge
1 \end{cases} 
$$
### 比例

使用 `\propto` 或者 `\sim` 表示比例关系，例如：

```
$a \propto b$

$c \sim d$
```


$$
a \propto b  \qquad  c \sim d
$$

### 矢量

使用 `\vec{a}` 来表示向量，例如：

```
$\vec{a}, \vec{b}, \vec{c}$
```
$$
\vec{a}, \qquad  \vec{b}, \qquad  \vec{c}
$$

### 其他常用命令

- `\infty`: 表示无穷大。  例:`$lim_{x\to\infty}f(x)$` （$lim_{x\to\infty}f(x)$）
- `\times`, `\pm`, `\div`: 分别表示乘号、正负号、除号。例：`$\pm (a \times b  +  c  \div d) $`（$\pm (a \times b  +  c  \div d) $）
- `\limits`（$$）: 限制上下标的位置，一般用于求和、求积、积分等符号。例：`$\sum\limits_{i=1}^n a_i$` $\sum\limits_{i=1}^n a_i$

以上常见的MarkDown数学公式语法，根据自己的需求灵活运用即可。

MarkDown --- 数学公式语法集

## 引言

在上一篇[复杂度分析专题（一）](https://niuery.com/post/38)中，学习了复杂度的大O表示法和一些常见复杂度（$O(1)$、$O(n)$、$O(logn)$、$O(n^2)$等等）的分析方法，下面介绍4个更加细分的复杂度概念：
- 最好情况时间复杂度（best case time complexity）。
- 最坏情况时间复杂度（worst case time complexity）。
- 平均情况时间复杂度（average case time complexity）。
- 均摊时间复杂度（amortized  time complexity）。


## 最好时间复杂度和最坏时间复杂度
现有如下C#代码：

```csharp
//假设arr 是无序的，无重复的数组
public int FindIndex(int[] arr,int param)
{
    int pos = -1;
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == param) pos = i;
    }

    return pos;
}
```
代码功能是在一个无序数组中，找出`param`在数组中的位置，若没有找到，则返回-1。

按照上一篇中介绍的复杂度计算方法，该方法的复杂度为$O(n)$。

但是在数组中查找一个元素时，不一定会全部遍历一遍，又可能提前找到，遍历就结束了，所以可以像这样优化一下代码：
```csharp
public int FindIndex(int[] arr,int param)
{
    int pos = -1;
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == param) 
        {
            pos = i;
            break;
        }   
    }

    return pos;
}
```

那这个时候算法复杂度就不再是$O(n)$了

- **若数组中的第一个元素正好是要查询的元素，那么此时的时间复杂度就是$O(1)$**。
- **若数组中没有相匹配的元素，就需要将整个数组遍历一遍，那么此时的时间复杂度就是$O(n)$**。

所以针对上述第一种情况，称之为**最好情况时间复杂度$O(1)$**,针对上述第一种情况，称之为**最坏情况时间复杂度$O(1)$**

## 平均时间复杂度

最好时间复杂度和最坏时间复杂度对应的都是极端情况下的复杂度，发生概率低。所以就引入了平均情况下的复杂度，平均时间复杂度。

**平均时间复杂度指的是代码被执行无数次，对应的时间复杂度的平均值。**

整个平均值实际上指的是概率论中的加权平均值，也称期望值。

**期望值是概率论和统计学中一个非常重要的概念，通常指随机变量的平均值。在离散情况下，期望值的计算公式为：**

$$
E(X)=\sum_{i}x_i × P(x_i)
$$
**其中，X是一个随机变量，$x_i$是X可以取到的每个值，$P(x_i)$是X取到$x_i$的概率。**


依旧借助上文中第二段代码的例子，要查找元素`param`在数组中的位置，有两种情况，在数组内或者不在数组内，两种情况出现的概率都是$\frac{1}{2}$，另外，要查找的数据出现在0到n-1的位置的概率是一样的，都是$\frac{1}{n}$，因此根据概率乘法法则，要查找的数据出现在0到n-1中任意位置的概率是$\frac{1}{2n}$，总共是n+1中情况。

所以上文中例子的时间复杂度的计算过程如下：

$$
1×\frac{1}{2n}+2×\frac{1}{2n}+3×\frac{1}{2n}+...+n×\frac{1}{2n}+n×\frac{1}{2}=\frac{3n+1}{4}
$$

所以最后计算到期望值为$\frac{3n+1}{4}$，根据大O复杂度表示法表示，去掉系数和常量，最后的得到平均时间复杂度为$O(n)$。


:::tip{title="提示"}
只有当同一段代码在不通过情况下性能表现不同，并且时间复杂度有量级的差别时，才会使用这三种不同的复杂度来表示。
:::


## 均摊时间复杂度

下面介绍一平均时间复杂度的特殊情况：均摊时间复杂度，使用平摊分析法。

有如下代码：

```csharp
private int[] arr = new int[n];
private int count = 0;

public void Insert(int value)
{
    if (count == arr.Length)
    {
        int sum = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            sum += arr[i];
        }
        count = 0;
    }
    arr[count] = value;
    count++;
}
```

上述代码实现了向数组中插入数据的功能，如果数组中有未占用空间，就直接将数据插入到数组中，当数组满了之后`count == arr.Length`，遍历数组求和，同时清空数组`count = 0`，然后将新数据插入。

分析一下它的时间复杂度：
- 最好情况，数组中有未占用空间，只需要将数据插入到数组下标为count的位置，此时为最好时间复杂度$O(1)$。
- 最坏情况，数据中全满，先遍历求和，再插入数据，此时为最坏时间复杂度$O(n)$。
- 平均情况，假设数组长度是n，
    - 当有未占用空间时，分别能插入下标为0到n-1的位置，共有n中情况。
    - 当全满时，是一种情况。
    - 这n+1种情况的概率是一样为$\frac{1}{n+1}$
    
    所以根据期望值的计算方法，转化为大O表示法得到的平均时间复杂度如下
    
$$
1×\frac{1}{n+1}+1×\frac{1}{n+1}+1×\frac{1}{n+1}+...+1×\frac{1}{n+1}+n×\frac{1}{n+1}=O(n)
$$

但是仔细观察`Insert`方法，它其实在大部分情况下时间复杂度都为$O(1)$，只有极个别情况，时间复杂度才为$O(n)$，且两者在出现的频率是有规律的，两者有一定的前后时序关系，在一个$O(n)$时间复杂度的插入之后，紧跟着会有n-1个$O(1)$时间复杂度的插入操作，不断循环。

针对这样一个特殊场景的平均时间复杂度分析，可以使用一种更加简单的分析方法：平摊分析法，通过平摊分析法得到的时间复杂度，命名为：均摊时间复杂度。

具体怎么分析均摊时间复杂度呢？

我们观察到，每一次$O(n)$时间复杂度的插入操作都会跟着n-1个$O(1)$时间复杂度的插入操作，因此，可以将耗时多的那次操作的耗时均摊到接下来的n-1次的耗时少的操作上，那么均摊下来，这一组的连续插入操作的均摊时间复杂度就变为了$O(1)$。


:::tip{title="提示"}
对一个数据结构进行一组连续的操作，在大部分情况下，时间复杂度很低，只有个别情况的时间复杂度高，且这些操作之间存在前后连贯的时序关系，这个时候，就可以将这一组操作放在一起分析，观察是否能将较高时间复杂度的那次操作的耗时均摊到其他较低时间复杂度的操作上。

能够应用均摊时间复杂度分析的场景中，一般均摊时间复杂度就等于最好时间复杂度。
:::

> 参考资料
> 
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6

数据结构与算法 --- 复杂度分析专题（二）

## 意义
算法复杂度分析的意义在于评估算法的执行效率，找出最优解决方案，是优化算法和改进程序性能的基础。通过对算法的时间复杂度和空间复杂度进行分析，可以帮助我们预估该算法运行所需的资源，从而提高程序的性能。



## 大O复杂度表示法

### 例1
有如下代码
```csharp
1    public int Calculate(int n)
2    {
3        int sum = 0;
4        for (int i = 0; i < n; i++)
5        {
6            sum += i;
7        }
8        return sum;
9    }
```

上述代码段中，假设每条语句执行的时间一样，为1个单位，记为$1u$。那么在上述代码片段中：
- 第3、8行执行分别需要1$u$

- 第4、5、6、7行代码循环执行了$n$次，那么就需要$4n$个$1u$

- 总的执行时间为$T(n)=4n+2$个$1u$。

我们借助[在线函数绘图工具](https://www.desmos.com/calculator)画出该函数的曲线如下：


![image.png](https://niuery.com/static/img/28cff64c2045a777019bc338229787e0.image.png)


我们可以看出一个规律：执行时间一定为正数，所以代码执行的总时间(($4n+2$)X$1u$)是和语句的执行次数($4n+2$)成正比的。

### 例2

```csharp
1    public int Calculate(int n)
2    {
3        int sum = 0;
4        for (int i = 0; i < n; i++)
5        {
6            for (int j = 0; j < n; j++)
7            {
8                sum += i;
9            }
10       }
11       return sum;
12   }
```
同上，假设每条语句执行的时间一样，为1个单位，记为$1u$。那么在上述代码片段中：
- 第3、11行分别需要$1u$

- 第4、5、10行分别循环执行了$n$次，即执行需$3n$个$1u$

- 第6，7，8，9分别执行了$n^2$次，即执行需$4n^2$个$1u$

- 总的执行时间为$t(n)=4n^2+3n+2$个$1u$


画出该函数的曲线如下：

![image.png](https://niuery.com/static/img/260d726e42656a6246465f4626e6b410.image.png)

由上边两段推导代码执行时间的过程，可以得到一个重要规律：一段代码的执行时间$T(n)$与每一条语句的总执行次数（累加数）成正比，可以把这个规律总结为一个公式，如下：
$$
T(n)=O(f(n))
$$

其中，**$T(n)$表示代码执行的总时间，$n$表示数据规模，$f(n)$表示每条语句执行次数的累加和，这个值与$n$有关，因此用$f(n)$这样一个表达式来表示，公式中的$O$符号，表示代码的执行时间$T(n)$与$f(n)$成正比。**

实际上，**大$O$时间复杂度并不具体表示代码真正执行的时间，而是表示代码执行时间随着数据规模增大的变化趋势，因此，也称为渐近时间复杂度（asymptomatic time complexity）,简称时间复杂度。**

当$n$很大时，100000，1000000级别时，公式中的低阶，常量，系数3部分并不左右增长趋势，例如下面的曲线：

$T(n)=4n+2$曲线：

![image.png](https://niuery.com/static/img/bfad1ce1aec2742b8559ee84411a853d.image.png)

$t(n)=4n^2+3n+2$曲线，该曲线即使只到十位数的数量级，曲线就已经趋向于笔直的竖线：

![image.png](https://niuery.com/static/img/40596e104dbaa296bab8b27d0a1421f4.image.png)

所以低阶，常量，系数3部分可以忽略。我们只需要记录一个最大量级。如果用大$O$表示法表示上面的两个复杂的则是这样：

$$
T(n)=O(n)
$$


$$
T(n)=O(n^2)
$$

## 时间复杂度的分析方法

大O复杂度表示方法只表示一种变化趋势，我们通常会忽略公式中的常量，低阶和系数，只记录最大量级，因此，我们在分析一段代码时间复杂度的时候，我们也只需要关注**循环执行次数最多的那段代码**。
### 加法法则
**加法法则：代码的总复杂度等于量级最大的那段代码的复杂度。**

    有如下代码片段，分析一下它的时间复杂度：
```csharp
public int Calculate(int n)
{
    //第一段  
    int sum1 = 0;
    for (int i = 0; i < 100; i++)
    {
        sum1 += i;
    }
    
    //第二段 
    int sum2 = 0;
    for (int i = 0; i < n; i++)
    {
        sum2 += i;
    }
    
    //第三段
    int sum3 = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sum3 += i;
        }
    }
    
    //第四段
    return sum1+ sum2+ sum3;
}
```

分析结果：
- 第一段，执行时间固定为常数，复杂度记为$O(1)$。

- 第二段，复杂度为$O(n)$。

- 第三段，复杂度为$O(n^2)$。

- 第四段，只执行一次，复杂度记为$O(1)$。



:::tip{title="提示"}
**为什么第一段复杂度为常数？**

注意大O复杂度的概念，时间复杂度表示的是代码执行时间随数据规模（$n$）的增长趋势，第一段代码中，无论$n$如何变化，它始终执行100次。在曲线图上画出来就是一条平行于X轴的直线，并不会体现出增长趋势，
:::

加法法则定义代码的总复杂度等于量级最大的那段代码的复杂度，用公式表达则是

如果有
$$
T_1(n)=O(f(n));T_2(n)=O(g(n));
$$
那么

$$
T_总(n)=T_1(n)+T_2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)));
$$

所以结论就是`Calculate`方法的时间复杂度为$O(n^2)$。

### 乘法法则 

**乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积**。

有如下代码片段，计算`CalculateA`方法的时间复杂度：

```csharp
public int CalculateA(int n)
{

    int sum = 0;
    
    for (int i = 1; i <= n; i++)
    {
        sum += CalculateB(n);

    }
    return sum;
}

public int CalculateB(int n)
{

    int sum = 0;
    
    for (int i = 1; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

```

分析结果：
- `CalculateA`方法的时间复杂度为$O(n)$。

- `CalculateB`方法的时间复杂度为$O(n)$。

乘法法则定义嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，用公式表达则是

如果有
$$
T_1(n)=O(f(n));T_2(n)=O(g(n));
$$
那么

$$
T_总(n)=T_1(n) × T_2(n)=O(f(n))×O(g(n))=O(f(n)×g(n));
$$
 
所以结论就是`CalculateA`的时间复杂度为$O(n×n)$=$O(n^2)$
 
## 常见的时间复杂度量级
### 常量级

只要代码的执行时间不随数据规模$n$变化，代码就是常量级时间复杂度，统一记作$O(1)$。

:::tip{title="注意"}
$O(1)$是常量级时间复杂度的一种表示方法，并不意味着只执行了一行代码。
:::
### 对数阶

对数阶时间复杂度非常常见，但它是最难分析的时间复杂度之一。

有如下代码段：

```csharp
public int Calculate(int n)
{
    int i = 1;
    while (i <= n)
    {
        i *= 2;
    }
    return i;
}
```
如果想要分析该方法的时间复杂度，那就需要看执行次数最多的语句，一共执行多少次？

由上述代码中可以看出，变量i从1开始取值，每循环一次就乘以2，当i值大于n时，循环结束。写成公式则是这样：

$$
1×2×2×2×2×2×...×2\leqslant n
$$
我们简化一下就是这样：

$$
1×2^x =n
$$

所以得出解为：x的值为以2为底，n的对数

$$
x=log_2n
$$

所以上文`Calculate`方法的时间复杂度为$O(log_2n)$

那如果我们把上述代码段中的`i *= 2` 修改为`i *= 3`，得到的时间复杂度就变成了$O(log_3n)$

那为什么标题中的表示的时间复杂不体现对数的底数呢？

因为根据对数的换底公式，
$$
log_3n=log_32×log_2n
$$
因此
$$
O(log_3n)=O(C×log_2n)
$$
其中$C=log_32$是一个常量，采用大O复杂度表示法的时候，忽略系数，即
$$
O(C×f(n))=O(f(n))
$$
因此，
$$
O(log_3n)=O(log_2n)
$$
所以**对于对数阶时间复杂度，忽略对数的底数，统一表示为$O(logn)$**。

### 多数据规模
这是一种特殊情况，时间复杂度由多个数据规模来决定。

有如下代码：

```csharp
public int CalculateA(int m, int n)
{
    int sum = 0;

    for (int i = 1; i <= m; i++)
    {
        sum += i;
    }

    for (int i = 1; i <= n; i++)
    {
        sum += i;
    }

    return sum;
}

public int CalculateB(int m, int n)
{
    int sum = 0;

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            sum += i;
        }

    }

    return sum;
}
```
上述代码中，m,n表示两个无关的数据规模，最终代码的复杂度跟这两者都有关系，对于这两者无法事先评估谁的量级更大，所以在表达时间复杂度时都不可以省略，因此，上述代码中
- CalculateA符合加法法则，m，n不可省略，则得到的时间复杂度为$O(m+n)$
- CalculateB符合乘法法则，m，n不可省略，则得到的时间复杂度为$O(mn)$

## 空间复杂度

时间复杂度全称渐近时间复杂度，表示算法的执行时间于数据规模之间的增长关系，类比一下就能得到空间复杂度定义：

**空间复杂度全称渐近空间复杂度，表示为算法的存储空间与数据规模之间的增长关系**。

其分析规则与时间复杂度一致，类比学习即可。常见的空间复杂度有$O(1)$，$O(logn)$，$O(n)$，$O(nlogn)$，$O(n^2)$ 等。其中$O(logn)$，$O(nlogn)$对数阶复杂度常见于递归代码。



> 参考资料
> 
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6
> 
> [2] 大话数据结构 / 程杰 著. --北京：清华大学出版社，2011.6

数据结构与算法 --- 复杂度分析专题（一）

## 开场白

算法介绍从一个简单加法开始，现要求写一个求1+2+3+..+100的结果的程序，那我可以这样写：

```csharp
int count = 100;

int sum = 0;

for (int i =1; i <= count; i++)
{
    sum += i;
}
```



这就是最简单的程序之一，这就是算法。但是它是最优的吗？是最高效的吗？

儿时数学家高斯提出了另一种解法，他将两组1+2+3+..+100一组升序，一组降序进行组合，变成(1+100)+(2+99)+...(100+1)，像这样：    

![image.png](https://niuery.com/static/img/8e5f794f6069a15426169f2b8e09161d.image.png)

最后得到的公式就是后世的等差数列求和公式（首项 + 末项）x 项数 / 2）：
$S_n = \frac{(a_1 +a_n )n}{2}$

这样用程序来实现就是这样：

```csharp
int count = 100;

int sum = 0;

sum = (1 + count) * count / 2;
```

这样的话，程序由运行一百次，就变成了运行一次，这就是更高效的算法。


## 算法的定义

什么是算法呢？算法就是描述解决问题的方法。

**算法是解决特定问题求解步骤的描述，在计算机中表表现为指令的有限序列，并且每条指令表示一个或多个操作。**


## 算法的特性

算法具有五个基本特性：**输入**、**输出**、**有穷性**、**确定性**和**可行性**。

- 输入输出
   
    输入和输出特性比较容易理解，算法具有零个或多个输入。尽管对于绝大多数算法来说，输入参数都是必要的，但对于个别情况，不需要任何输入参数，因此算法的输入可以是零个。算法至少有一个或多个输出，输出的形式可以是打印输出，也可以是返回一个或多个值等。
- 有穷性
    
    有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。
- 确定性
    
    确定性：算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。
- 可行性
    
    可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

## 算法设计的要求
一个合格的算法要基本符合这些要求，例如**正确性**，**可读性**，**健壮性**，**时间效率高和存储量低**。
### 正确性
正确性：**算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案**。但是算法的“正确”通常在用法上有很大的差别，大体分为以下四个层次。
1. 算法程序没有语法错误。
2. 算法程序对于合法的输入数据能够产生满足要求的输出结果。
3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。
4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。


对于这四层含义，层次1要求最低，但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱，不能算是生活幸福一样。而层次4是最困难的，我们几乎不可能逐一验证所有的输入都得到正确的结果。因此算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，我们把层次3作为一个算法是否正确的标准。

### 可读性

可读性：**算法设计的另一目的是为了便于阅读、理解和交流。**
可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难于调试和修改。

我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了自己都不知道写了些什么。可读性是算法（也包括实现它的代码）好坏很重要的标志。

### 健壮性

一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。

健壮性：**当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。**


### 时间效率高和存储量低
时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。

存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。**设计算法应该尽量满足时间效率高和存储量低的需求**。


## 算法效率的度量方法

### 事后统计方法
**这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低**。

但是有缺陷：
- 必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法，不是竹篮打水一场空吗？

- 时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。

- 算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现。

### 事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算。

经过分析，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
- 算法采用的策略、方法。

- 编译产生的代码质量。

- 问题的输入规模。

- 机器执行指令的速度。

第1条当然是算法好坏的根本，第2条要由软件来支持，第4条要看硬件性能。也就是说，抛开这些与计算机硬件、软件有关的因素，**一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少**。

## 函数的渐进增长

函数的渐近增长是指当自变量趋近于正无穷时，函数增长的趋势。通俗来说，可以想象一条直线在平面上向右无限延伸，而函数就是这条直线上的一个点，当自变量趋近于正无穷时，函数的值会随着自变量的增加而增加。而函数的渐近增长就是描述这个增长的速度和趋势。

举个例子，如果一个函数的渐近增长是线性的，那么当自变量增加一单位时，函数的值也会增加一单位，这种增长趋势可以用直线来描述。而如果一个函数的渐近增长是指数级的，那么当自变量增加一单位时，函数的值会增加很多单位，这种增长趋势可以用指数函数来描述。

在算法分析和计算机科学中，函数的渐近增长非常重要，因为它可以帮助我们预估算法的时间复杂度和空间复杂度，从而优化算法的效率。通过对函数的渐近增长的分析，我们可以找到最优的算法实现方式，以达到最快的运行速度和最少的资源消耗。

## 算法的时间复杂度
### 定义
在进行算法分析时，**语句总的执行次数$T(n)$是关于问题规模$n$的函数，进而分析$T(n)$随$n$的变化情况并确定$T(n)$的数量级**。

**算法的时间复杂度，也就是算法的时间量度，记作：$T(n)=O(f(n))$。它表示随问题规模n的增大，算法执行时间的增长率和$f(n)$的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中$f(n)$是问题规模$n$的某个函数**。

这样用大写$O()$来体现算法时间复杂度的记法，称之为**大O算法**。

一般情况下，随着$n$的增大，$T(n)$增长最慢的算法为最优算法。

### 算法的渐进复杂度

在计算机科学中，大O表示算法的渐进复杂度。它是用来描述算法的时间或空间复杂度的一种方式。当我们说一个算法的复杂度为$O(f(n))$时，我们指的是当输入大小为$n$时，算法的运行时间或空间复杂度与$f(n)$成正比。通常，我们会使用最高阶的项来表示算法的复杂度，因为它在输入趋近于无穷大时最能反映算法的增长率。

**推导算法的时间复杂度**通常可以通过以下步骤来实现：

1. **确定算法的基本操作**：算法中最基本的操作是什么？例如，基本操作可以是赋值、比较、加减乘除等。

2. **分析算法的代码**：对算法代码进行分析，找到每个基本操作所对应的执行次数。

3. **计算时间复杂度**：将每个基本操作的执行次数乘以其所需的时间复杂度，再将所有操作的时间复杂度相加，得到总的时间复杂度。

4. **推导大O阶**：将得到的总的时间复杂度，经过系列步骤推导，最终得到的就是大O阶。

**推导大O阶方法**：
- **用常数1取代运行时间中的所有加法常数**。

- **在修改后的运行次数函数中，只保留最高阶项**。
 
- **如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶**。


推导大O阶的过程涉及到分析算法的每个步骤的时间复杂度，并计算这些步骤的总时间复杂度。最终，我们将得到一个表示算法复杂度的数学表达式。例如，如果我们正在分析一个简单的循环，其中每次迭代的时间复杂度为$O(1)$，并且循环执行$n$次，则总时间复杂度为$O(n)$。如果我们分析的是一个递归算法，那么我们需要使用递归方程来推导出算法的复杂度。

推导大O阶需要对算法的实现细节有深入的理解，以便能够准确地计算每个步骤的时间复杂度，并最终得出算法的总时间复杂度。

### 常见的时间复杂度
常见的时间复杂度如下所示：

| 执行次数函数 | 阶 | 非正式术语|
| --- | --- |---|
| $10$ | $O(1)$ |常数阶 |
| $2n+3$ | $O(n)$ | 线性阶 |
| $3n^2+2n+1$ | $O(n^2)$ | 平方阶 |
| $5log_2n+20$ | $O(logn)$ | 对数阶 |
| $2n+4log_2n+12$ | $O(nlogn)$ | nlogn阶 |
| $3n^3+2n^2+5n+13$ | $O(n^3)$ | 立方阶 |
| $2^n$ | $O(2^n)$ | 指数阶 |

常用的时间复杂度所消耗的时间从小到大排序为

$O(1)$ < $O(logn)$ < $O(n)$ < $O(nlogn)$ < $O(n^2)$ < $O(n^3)$ < $O(2^n)$ < $O(n!)$ < $O(n^n)$

### 最坏情况与平均情况

我们查找一个有个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为$O(1)$，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是$O(n)$，这是最坏的一种情况了。

**最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。**

而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为$n/2$次后发现这个目标元素。

**平均运行时间是所有情况中最有意义的，因为它是期望的运行时间**。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。

对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。**一般在没有特殊说明的情况下，都是指最坏时间复杂度**。

## 空间复杂度

算法的空间复杂度是指在算法执行过程中所需要的内存空间大小，通常用空间复杂度来衡量算法所占用的内存资源大小。算法空间复杂度的计算公式记作：$S(n)=O(f(n))$，其中，$n$为问题的规模，$f(n)$为语句关于$n$所占存储空间的函数。

## 结尾语

**错误思想**：

认为现在CPU速度越来越快，内存越来越大，算法的细微的优劣是用户体验不到的。

**数据验证**：

假设CPU在短短几年间，速度提高了100倍，这其实已经很夸张了。而我们的某个算法本可以写出时间复杂度是$O(n)$的程序，却写出了$O(n^2)$的程序，仅仅因为容易想到，也容易写。即在$O(n^2)$的时间复杂度算法程序下，速度其实只提高了10倍（$\sqrt[2]{100}$=10），而对于$O(n)$时间复杂度的算法来说，那才是真的100倍。

**结论**：

也就是说，一台老式CPU的计算机运行$O(n)$的程序和一台速度提高100倍新式CPU运行$O(n^2)$的程序。最终效率高的胜利方却是老式CPU的计算机，原因就在于算法的优劣直接决定了程序运行的效率。


> 参考资料
> 
> [1] 大话数据结构 / 程杰 著. --北京：清华大学出版社，2011.6

数据结构与算法 --- 算法绪论

## 数据结构起源
早期人们都把计算机理解为数值计算工具，就是感觉计算机当然是用来计算的，所以计算机解决问题，应该是先从具体问题中抽象出一个适当的数据模型，设计出一个解此数据模型的算法，然后再编写程序，得到一个实际的软件。

可现实中，我们更多的不是解决数值计算的问题，而是需要一些更科学有效的手段（比如表、树和图等数据结构）的帮助，才能更好地处理问题。所以**数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科**。


 

## 基本概念和术语

1. 数据

    **数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合**。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

2. 数据元素

    **数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。**

3.  数据项

    **数据项：一个数据元素可以由若干个数据项组成。** **数据项是数据不可分割的最小单位。**

4. 数据对象

    **数据对象是性质相同的数据元素的集合，是数据的子集。**

5. 数据结构

    结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。那数据结构是什么？

    **数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。**

## 逻辑结构与物理结构

### 逻辑结构
**逻辑结构**是指数据对象中数据元素之间的相互关系，主要分为一下四种：
1. 集合结构

    **集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系**。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”。数据结构中的隹合关系就类似干数学中的集合。
![image.png ](https://niuery.com/static/img/7c167ad79c850eafc6204349184c881a.image.png)
    
2. 线性结构

    **线性结构中的数据元素之间是一对一的关系**。
![image.png](https://niuery.com/static/img/73b71fb0bafd536dfec6288070dd7b7f.image.png)

3. 树形结构

    **树形结构的数据元素是一对多的层关系。**

    ![image.png](https://niuery.com/static/img/9f3de4ad218deb3a638436145d69ffdf.image.png)

4. 图形结构
 
 
   **图形结构的数据元素是多对多的关系。**
    
    ![image.png](https://niuery.com/static/img/95ee1bfe5d0b6b963c23889ab1fbe5dc.image.png)


:::tip{title="提示"}
我们在用示意图表示数据的逻辑结构时，要注意两点：
- 将每一个数据元素看做一个结点，用圆圈表示。
-  元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示。
:::

### 物理结构
**物理结构**是指数据的逻辑结构在计算机中的存储形式。
存储形式有两种：
1. 顺序存储结构
    
    **顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。**

![image.png](https://niuery.com/static/img/1c41ae49b6301171821d76d0fe1b97a0.image.png)

2. 链式存储结构 

    **链式存储结构是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的也可以是不连续的。**
    
    
    ![image.png](https://niuery.com/static/img/d02f16edb077815ddde9a8884fc50868.image.png)


## 抽象数据类型
### 数据类型

**数据类型是指一组性质相同的值的集合及都定义在此集合上的一些操作的总称。**

数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

数据类型可以分为两类：
- 原子类型：是**不可以再分解的基本类型**，包括整形，字符型等。
- 结构类型：有**若干个类型组合而成，是可以再分解**的。例如，整形数组由多个整形数据组成的。
### 抽象数据类型

**抽象数据类型是指一个数学模型及定义在该模型上的一组操作。**

抽象数据的类型的定义仅取决与它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

比如各种计算机，不管是大型机、小型机、PC、平板电脑、PDA,甚至智能手机都拥有“整数”类型，也需要整数间的运算，那么整型其实就是一个抽象数据类型，尽管它在上面提到的这些在不同计算机中实现方法上可能不一样，但由
于其定义的数学特性相同，在计算机编程者看来，它们都是相同的。因此，**“抽象”的意义在于数据类型的数学抽象特性。**

一个抽象数据类型定义了**一个数据对象，数据对象中各数据元素之间的关系及对数据元素的操作**。它体现了程序设计中**问题分解**，**抽象**和**信息隐藏**的特性。



> 参考资料
> 
> [1] 大话数据结构 / 程杰 著. --北京：清华大学出版社，2011.6