# Algorithm

**数据结构是指一组数据的存储结构**，如队列、栈、堆，**算法是操作数据的一组方法**，如二分查找、动态规划。

数据结构与算法是相辅相成的，**数据结构是为算法服务的，算法需要作用在特定的数据结构上**。比如数组具有随机访问的特点，二分查找需要用数组来存储数据，若用链表，二分查找就无法工作了。

十个重要的数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。

十个重要的算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

对于数据结构和算法，不只是要了解它是什么，更重要的是要知道：它的**来历**、**特点**、**解决的问题**、**应用场景**。

* [复杂度分析](https://yunzhao.gitbook.io/notes/computer-science/algorithm/complexity)
  * [时间复杂度](https://yunzhao.gitbook.io/notes/computer-science/complexity#shi-jian-fu-za-du)
  * [空间复杂度](https://yunzhao.gitbook.io/notes/computer-science/complexity#kong-jian-fu-za-du)
* [线性表结构](https://yunzhao.gitbook.io/notes/computer-science/algorithm/list)
  * [Array](https://yunzhao.gitbook.io/notes/computer-science/list#array)
  * [List](https://yunzhao.gitbook.io/notes/computer-science/list#list)
  * [Stack](https://yunzhao.gitbook.io/notes/computer-science/list#stack)
  * [Queue](https://yunzhao.gitbook.io/notes/computer-science/list#queue)
* [排序](https://yunzhao.gitbook.io/notes/computer-science/algorithm/sort)
* [查找](https://yunzhao.gitbook.io/notes/computer-science/algorithm/search)
* [跳表](https://yunzhao.gitbook.io/notes/computer-science/algorithm/skip-list)
* [哈希表](https://yunzhao.gitbook.io/notes/computer-science/algorithm/hash-table)
* [Tree](https://yunzhao.gitbook.io/notes/computer-science/algorithm/tree)
  * [二叉查找树](https://yunzhao.gitbook.io/notes/computer-science/tree#er-cha-cha-zhao-shu)
  * [平衡二叉查找树](https://yunzhao.gitbook.io/notes/computer-science/tree#ping-heng-er-cha-cha-zhao-shu)
  * [红黑树](https://yunzhao.gitbook.io/notes/computer-science/tree#hong-hei-shu)
  * [递归树](https://yunzhao.gitbook.io/notes/computer-science/tree#di-gui-shu)
  * [堆](https://yunzhao.gitbook.io/notes/computer-science/tree#dui)
  * 并查集
  * [B 树](https://yunzhao.gitbook.io/notes/computer-science/tree#b-shu)
  * [B+ 树](https://yunzhao.gitbook.io/notes/computer-science/tree#b-shu-1)
* [图](https://yunzhao.gitbook.io/notes/computer-science/algorithm/graph)
* [字符串匹配算法](https://yunzhao.gitbook.io/notes/computer-science/algorithm/string-matching)
* [布隆过滤器](https://yunzhao.gitbook.io/notes/computer-science/algorithm/bloom-filter)
* 算法思想：
  * [贪心算法](https://yunzhao.gitbook.io/notes/computer-science/algorithm/greedy-algorithm)
  * [分治算法](https://yunzhao.gitbook.io/notes/computer-science/algorithm/divide-and-conquer)
  * [回溯算法](https://yunzhao.gitbook.io/notes/computer-science/algorithm/back-tracking)
  * [动态规划](https://yunzhao.gitbook.io/notes/computer-science/algorithm/dynamic-programming)

四种算法思想比较：

* 分治算法解决的问题大部分都不能抽象成多阶段决策问题；贪心、回溯、动态规划解决的问题都可以抽象成多阶段决策。
* 回溯算法是“万金油”，能用动态规划、贪心解决的问题，基本都能用回溯解决，回溯相当于穷举，时间复杂度非常高。
* 动态规划能解决的问题需要满足最优子结构、无后效性、重复子问题三个特性；动态规划高效的原因就是回溯算法中有大量重复子问题，而分治算法相反，要求子问题不能重复。
* 贪心算法本质是动态规划的一种特殊情况，解决问题需要满足最优子结构、无后效性、贪心选择性，不用强调重复子问题。贪心选择性的意思是通过局部的最优选择，能产生全局的最优选择。

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-LuGBwN6BNHeHFOD12X3%2F-LuGWB0hlE3GrKQ6cWks%2Fimage.png?alt=media\&token=163f8099-293e-40cd-ab1d-db4c28325581)