算法学习（四）：《算法图解》笔记(一)

前段时间一直在看《算法图解》，这本书图文并茂，深入浅出，还是比较易读的。在阅读的过程中，记了一些笔记，都是一些算法领域相关的比较基础的一些知识。
我总觉得，读一本书，要有一本书的收获这句话是比较贪婪的说法，抱着功利心去读书，反而不如平常心去读更有乐趣点。但对于技术类的书来说，这句话我觉得还是比较贴切的（废话，技术书里面又没有那么多跌宕。
关于读书笔记这件事，我并不会照着抄一些书里加粗黑体的概念来充数，主要是记录一些我对书中内容的理解。
内心OS：其实我知道上面说这么一堆并没有什么用。因为并不会有人看我的博客。我日。

第一章：算法简介

主要介绍了关于算法的一些基本知识，例如大O表示法等。关于大O表示法在此不多记录，需要的同学可以去看我算法学习的第一篇博客，就是关于大O表示法的。

二分查找

作为最简单和容易理解的查找算法，它的步骤如下：

取列表的中间值与要查找的目标元素进行比较
根据比较结果选择列表的前半部分或后半部分为一个新列表
对新列表重复步骤1，直到找到目标元素。

二分查找只能应用于有序列表。因为它需要根据目标元素与列表中间元素的比较结果来缩小列表，从而进一步确定目标元素所处的位置，如果是无序列表的话，与列表中间元素的比较毫无意义。

也比较容易得出，二分查找的时间复杂度为O(logn)

旅程最短问题

旅程最短问题，即某个人，要去n个城市，各个城市之间距离不同，求出它的最短旅程。

抽象出来就是：求出遍历n个互相距离不同的点的最短路线。

此问题的最基本解决思路如下：

确定遍历顺序，也就是列举出所有可能的路线
计算每种路线的路程
选出最短路径

我们知道，n个元素的排列顺序，有n！种，因此上面的解决办法，其时间复杂度为O(n！)。当n>20`之后，此类解决方法需要列举的路线已经是一个天文数字了，因此上面的解决办法已经近乎无能为力了。

对于旅程最短问题，至今仍没有比较完美的解决办法。但通过二叉树等算法，我们可以得到一个近似的最短路径结果。

第二章：选择排序

数据结构之数组

数组作为存储元素的一种数据结构，它的所有元素在内存中都是连续的，因此它有着很快的读取速度，例如我们需要第5个元素，数组通过第一个元素的内存地址，就可以直接得到第5个元素的内存地址。

但数组的插入速度是非常慢的，主要有以下两个原因：

在数组中间插入一个元素，就必须移动插入位置之后的所有元素

如果数组的后面的内存已经被占用，数组就无法再加长了，如果想加长，就必须将整个数组都移动到可以容纳更长数组的内存空位去。（虽然可以通过为数组后面预留空位来解决这个问题，但也只是权宜之计

同理，当删除数组元素时，必须前移其后的所有元素，所以数组的删除速度也很慢。

具体的，数组的读取速度为O(1)，插入和删除速度为O(n)

另外，数组这种数据结构还有一点需要注意，它的所有元素的类型必须相同。

数据结构之链表

链表的元素在内存中并不是相邻的，而是分散的，通过前一个元素存储下一个元素的地址，将一系列内存地址串成一个链表。这也是链表名字链字的由来。

对于链表来说，它的插入和删除速度是非常快的，因为在插入和删除时，都只需要修改它前一个元素存储的内存地址即可，不需要移动其他元素。

但链表的读取速度非常慢，因为无法像数组一样，通过第一个元素的内存地址就得出任意索引位置的地址。它必须从头开始，顺序得到每个元素的地址。

具体的，链表的读取速度为O(n)，插入和删除速度为O(1)

选择排序

选择排序，是一种时间复杂度为O(n²) 的排序算法。具体步骤如下：

遍历列表，找出列表的最大值，取出放入一个空列表
重复步骤1，直到列表中元素全被取出。

第三章：递归

递归函数，即在函数运行时又调用了自身的函数。

递归函数中，递归条件指函数调用自己的条件，基线条件是指，递归函数停止调用自己的条件。

递归函数必须有基线条件，这样才能避免无限循环。

数据结构之栈

栈(stack)是一种先进后出（FILO - first-in/last-out) 的数据结构，数据只能在栈顶进行添加和删除，即栈的压入和弹出。

对于函数调用来说，存在一个函数的调用栈，存储了函数调用所需的变量和上下文。

如果递归层数过多，会产生非常多的函数调用栈，占用大量内存，造成栈溢出，此时可以借助尾递归优化。

尾递归优化，就是指所有递归函数都使用同一个栈，大部分语言针对递归进行了尾递归优化。必须保证递归函数只返回自身调用，没有其他多余返回值时，才能使用。

第四章：快速排序

分而治之(D&C - divide and conquer)策略，是指找出递归的基线条件和递归条件，通过递归来解决问题的一种策略。

快速排序就是使用分而治之策略的一种排序算法。具体步骤如下：

在列表中选取一个基准值
将小于基准值的元素和大于基准制的元素分别放入一个列表。
如果得到的列表长度小于2，返回列表，否则，对得到的列表递归进行快速排序

采用递归进行排序的快速排序算法，时间复杂度和基准值的选择关系较大，最糟情况下（选取列表端值作为基准），时间复杂度为O(n²)，平均时间复杂度为O(n log n)

第五章：散列表

散列表，有多种叫法，在python中叫字典，在ruby中叫哈希，在PHP中叫关联数组。但在作为数据结构时，通常都称为散列表。散列表用于存储映射关系，也就是我们常说的键名和键值。

散列表是由散列函数和数组共同组成的一种数据结构，具有O(1)时间复杂度的查找速度。

散列函数

散列函数，是指接受任意输入，并返回一个数字的函数，即可以将输入映射到一个数字。

散列函数必须保证以下两个要求：

一致性。对于相同的输入，必须返回相同的数字。
差异性。对于不同的输入，尽可能的映射到不同数字。

通过散列函数的这种特性，将键名输入散列函数，得到一个数字，将键值存入数组中对应此索引的位置，就实现了散列表。

在散列表中通过键名查找键值时，将键名输入散列函数，就可以得到存储对应键值的数组索引。

冲突

不可能存在将所有不同输入映射到不同数字的散列函数，因为数组的长度并不是无限的。因此，在有限的数组前提下，散列函数一定会存在将不同键名映射到数组相同索引的情况，也就是冲突。

解决冲突的方法，最简单的，就是在冲突的位置不存储单个键值，而是存储一个链表，在链表中存储此索引处的所有键名键值。

填装因子

填装因子，即散列表键值元素数占散列表数组长度的比值。一般来说，当填装因子大于0.7时，散列表当前的数组已经不适合继续使用了，应该对数组调整长度（别忘了我们前面说的，调整数组长度是比较耗费性能的。

散列表如果想实现比较好的性能，就要尽可能避免冲突，尽量满足以下要求：

良好的散列函数，能尽可能的将键值均匀的分布在数组中
较低的填装因子，使数组有较多空位来继续容纳新元素

以上就是《算法图解》中前面章节前五章我记的一些笔记。为避免篇幅过长，这篇博客就到这里，下一篇博客再继续，关于算法中图的相关知识，记得回来^_^。