# 关于本书

作为一个算法小白，在力扣和书本之间来回，看了很多大神耐心的解答和总结，书本里循循善诱的知识整理。总想用一张表格来梳理出算法的知识体系，却也一直没有时间整理。这本笔记里，我选择用比较简单的Python语言来回顾一下数据结构和算法的基本知识。

目的不是覆盖所有的知识点，而是想要把自己读的书越读越薄。用尽量浅显的理解来实现比较常见和实用的数据结构和算法，也当是对自己学习的总结，可能能帮到读者。当中有什么疏漏和错误可以直接评论。

## 语言的选择

### 为什么选择Python？

当然是因为好写啦！

平时在阅读的时候发现，很多经典算法书都是用Java或C++演示代码的，虽然也方便理解，但是用Python来作为范例的不算多数。所以我们主要来做两件事：

1. **用Python简单实现基础的数据结构**。有些数据结构（比如说OrderedDict）都现成调库就行了，但是为了理解它们的读写速度啊，优缺点啊，用相对简单的数据结构（数组和链表）来简单实现能帮助理解。
2. **介绍基本算法，提供一些算法模版。**（1）搜索方法，（2）用动态规划来优化搜索速度，（3）如何求解图的性质或最值，（4）如何用数据流或多个机器来再加速。算法主要是提供一些思维方式，让我们从“能解决“到“能高效解决“地问题。

### 使用Python要注意什么

* 比如说下面这段程序用二分法来寻找长度为`N`排序数组`x`中的`target`。然而因为`x[mid+1:]`或者`x[:mid]`在Python中创建了新的List，所以下面这段程序的时间复杂度退化到了`O(N)`。

```python
def binarySearch(x, target):
    if len(x)==0: return False
    mid = len(x) >> 1
    if target==x[mid]: return True
    if target>x[mid]:
        return binarySearch(x[mid+1:])
    return binarySearch(x[:mid])
```

* Python中函数的值是[passed by assignment](http://docs.python.org/3/faq/programming.html#how-do-i-write-a-function-with-output-parameters-call-by-reference)，所以要注意什么那些数据类型是能改变或会改变的。这个特性和其他语言很不一样。

## 算法总结

很多算法都有“一脉相承“的思路。所以这里我把算法的介绍顺序变成：搜索算法-->动态规划-->图论，因为我觉得有些算法这样引出这样比较好理解。

| 引子                                                   | 算法                                                                                                                                                                                |
| ---------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| [DFS搜索](/python/suan-fa-ji-chu/shen-du-you-xian.md)  | <p><a href="/pages/-MYbGXxlfNAaudu0QDCJ"><strong>动态规划算法</strong></a></p><p>DP可以理解成<strong>Memoization</strong>的迭代写法</p><p>aka带备忘录的DFS</p>                                         |
| [动态规划](/python/hui-su-yu-dong-tai-gui-hua.md)        | <p><a href="/pages/-MY_vbEn6A2kOi3Z1rYd"><strong>DAG/拓扑排序算法</strong></a></p><p>拓扑排序利用了<strong>最优子结构</strong>的性质</p><p>这不就是DP的核心吗？</p>                                             |
| [BFS搜索](/python/suan-fa-ji-chu/guang-du-you-xian.md) | <p><a href="/pages/-MY_z8T2aj65ZwhKuiAJ"><strong>Dijkstra算法</strong></a></p><p>BFS用Queue来存储<strong>最浅层</strong>的frontier</p><p>Dijkstra用PQ来存储<strong>最小cost</strong>的frontier</p> |


---

# 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://maomaoalgo.gitbook.io/python/master.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.