《算法图解》读书笔记

左手的ㄟ右手 2023-02-13 14:59 47阅读 0赞

## chapter 1 简介 ##

**本章内容：二分查找，简单查找，大O表示法**

仅当列表是有序的时候，二分查找才管用。使用二分查找时，最多需要检查log *n*个元素。

大 O 表示法指出了最糟情况下的运行时间。算法的速度指的并非时间，而是操作数的增速。

![20200529222636519.png][]

## chapter 2 选择排序 ##

**本章内容：**

*  **学习两种最基本的数据结构——数组和链表。**
 *  **很多算法经过排序后才能使用，比如二分查找法是针对有序的一组数据。选择排序是下一章将介绍的快速排序的基石。**

需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。

*  使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。
 *   链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

对于数组\[2,20\]。元素的位置称为索引。因此，不说“元素20的位置为1”，而说“元素20位于索引1处”。

熟悉了数组、链表和大O表示法，就能认识第二种算法——选择排序。（注：这里的第一种算法是指二分查找法）。

## Charpter 3 递归 ##

**本章内容：递归是很多算法都使用的一种编程方法。**

本节将介绍一个重要的编程概念——调用栈（call stack）。调用栈不仅对编程来说很重要，使用递归时也必须理解这个概念。

栈是一种简单的数据结构，他有2种操作：压入（插入）和弹出（删除并读取）。

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。

### 3.3.1 调用栈 ###

计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 3][]

![20200530054938791.png][]

### 3.3.2 递归调用栈 ###

递归函数也使用调用栈，栈在递归中扮演着重要角色。

注意，栈顶的方框指出了当前执行到了什么地方。

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。

![20200530060001303.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 6][]

## charpter 4 快速排序 ##

**本章内容：学习分而治之。学习快速排序，快速排序使用分而治之策略。**

我们将探索分而治之（divide and conquer，D&C）——一种著名的递归式问题解决方法。

快速排序的思想：我们暂时将数组的第一个元素用作基准值。 接下来，找出比基准值小的元素以及比基准值大的元素。这被称为分区（partitioning）。之后进行递归。现在你有：

*  一个由所有小于基准值的数字组成的子数组；
 *  基准值； 
 *   一个由所有大于基准值的数组组成的子数组。

例如，对数组\[33,10,15,7\]进行快速排序的示意图：

![20200530061333820.png][]

快速排序的独特之处在于，其速度取决于选择的基准值。在平均情况下，快速排序的运行时间为*O*(*n* log *n*)。

## charpter 5 散列表 ##

**本章内容：**

*  **学习散列表——最有用的基本数据结构之一。散列表用途广泛，本章将介绍其常见的用途。** 
 *  **学习散列表的内部机制：实现、冲突和散列函数。这将帮助你理解如何分析散列表的性能。**

**未完待续**

[20200529222636519.png]: https://img-blog.csdnimg.cn/20200529222636519.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530054700360.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200530054727232.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200530054821690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200530054909756.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[20200530054938791.png]: https://img-blog.csdnimg.cn/20200530054938791.png
[20200530060001303.png]: https://img-blog.csdnimg.cn/20200530060001303.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200530060022661.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200530060042430.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200530060102140.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xha2Vzb24=,size_16,color_FFFFFF,t_70
[20200530061333820.png]: https://img-blog.csdnimg.cn/20200530061333820.png