# Algorithm and Data Structure

<!--more-->

# 数据结构与算法

## 数据结构

### 结构性数据结构

结构性数据结构对其数据元素之间的相关关系都做了一些明确规定，元素之间确实满足某种关系（如线性关系等），通常遵循该关系对数据进行存储方式设计和实现增删改查操作，典型的有集合结构、线性结构、层次结构、树形结构、图结构等。

- 集合结构

    - 集合

- 线性结构（序列结构）

    - 列表
    - 链表

- 层次结构
- 树形结构
- 图结构

### 功能性数据结构

功能性数据结构并未对其元素的相互关系提出任何结构性的规定，而是要求实现某种计算中非常有用的功能，同时只要求具备数据存储和使用（元素访问）功能，对其数据如何存储、元素之间如何关联，并不做明确要求，因此该种支持元素存储和访问的数据集结构也被称为容器。

- 栈
- 队列
- 优先队列
- 字典

由于只有功能性要求，功能性数据结构理论上可以使用任何技术实现。而在实际使用中 ，通常是首先把功能性数据结构映射到结构性数据结构，而后采用相应的实现技术，如栈和队列通常使用线性结构，以列表或者链表方式具体实现。

## 算法

### 算法设计模式

- #### 枚举法

    > 根据具体问题枚举出各种可能，从中选取有用信息或者问题的解。

- #### 贪心法

    > 根据问题的信息尽可能做出部分的解，并基于部分解逐步扩充得到完整的解。

- #### 分治法

    > 将复杂问题分解为相对简单的子问题，分别求解，最后通过组合起子问题解的方式得到原问题的解。

- #### 回溯法

    > 专指通过搜索的方式求解，如果问题很复杂，没有清晰的求解路径，可能就需要分步骤进行，由于每一步骤都有很多选择，因此只能采用试探的方式，根据实际情况选择一个可能方向，然其后续步骤无法进一步求解时，就需要退回到前面的步骤，选择其他求解路径，如此往复的动作称作回溯。

- #### 动态规划法

    > 在一些复杂情况下，问题求解很难直截了当进行，因此需要在前面的步骤中积累信息，在后续步骤中根据已知信息，动态选择一致的最好求解路径（同时可能进一步积累信息），如此方式称作动态规划。

- #### 分支限界法

    > 作为搜索方法的一种改良形式，如果在搜索过程中可以得到一些信息，确定某些可能的选择实际上并不真正有用，就可以及早将其删除，以缩小可能的求解空间，加速问题求解过程。

### 算法分析

算法复杂度分析包括时间复杂度和空间复杂度。

- 时间复杂度

    - 最少时间
    - 最长时间
    - 平均时间

- 空间复杂度

    - 内存大小