# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.