“算法是计算机科学领域最重要的基石之一“
“编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。“
——《算法的力量》
2.1.1案例一
设有一组N个数而要确定其中第k个最大者，称之为选择问题。常规的解法如下：
其实还有很多可以解决这个问题，比如二叉堆，归并算法等等。
2.2.2案例二
输入是由一些字母构成的一个二维数组以及一组单词组成。目标是要找出字谜中的单词，这些单词可能是水平、垂直、或沿对角线上任何方向放置。下图所示的字谜由单词this、two、fat和that组成。
图1字谜单词字符排列示意图
现在至少也有两种直观的算法来求解这个问题：
那么，使用自动机理论可以快速的解决这个问题，下一篇中给大家详细的分析。
03
数据结构与算法基础
3.1数据结构基础
3.1.1什么是数据结构
在计算机领域中，数据是信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号的总称。数据结构是指数据元素和数据元素之间的相互关系或数据的组织形式。数据元素是数据的的基本单位，数据元素有若干基本项组成。
3.1.2数据之间的关系
数据之间的关系分为两类：
·逻辑关系
表示数据之间的抽象关系，按每个元素可能具有的前趋数和直接后继数将逻辑结构分为线性结构和非线性结构。
逻辑关系或逻辑结构有如下特点：
逻辑结构的分类如下：
·物理关系
逻辑关系在计算中的具体实现方法，分为顺序存储方法、链式存储方法、索引存储方法、散列存储方法。
物理关系或物理结构有如下特点：
物理结构分类如下：
3.2算法基础
3.2.1基础概念
3.2.2数学基础
一般来说，估算算法资源消耗所需的分析是一个理论问题，因此需要一套数学分析法，先从数学定义开始。
这些定义的目的是要在函数间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值，因此，一般宣称f(N)，是没有什么意义的。于是，比较他们的相对增长率。当将相对增长率应用到算法分析时，会明白它是重要的度量。
如果用传统的不等式来计算增长率，那么第一个定义T(N)=O(f(N))是说T(N)的增长率小于或者等于f(N)的增长率。第二个定义T(N)=Ω(g(N))是说T(N)增长率大于或者等于g(N)的增长率。第三个定义T(N)=θ(h(N))是说T(N)的增长率等于h(N)的增长率。最后一个定义T(N)=o(p(N))说的则是T(N)的增长率小于p(N)的增长率。他不同于大O，因为大O包含增长率相同的可能性。
要证明某个函数T(N)=O(f(N))，通常不是形式的使用这些定义，而是使用一些已知的结果（比如说T(N)=O(log(N))）。一般来说，这就意味着证明是非常简单的计算而不应涉及微积分，除非遇到特殊情况。如下是常见的已知函数结果
在使用已知函数结果时，有几点需要注意：
3.2.3复杂度函数
正常情况下的复杂度函数包含如下两种：
3.3知识储备
3.3.1质数分辨定理（HashTree的理论基础）
简单的说就是，n个不同的质数可以分辨的连续数的个数和他们的乘机相同。分辨是指这些连续的整数不可能有相同的余数序列。
3.3.2Hash算法
1）Hash
2）常见的Hash算法
3）Hash碰撞
解决Hash碰撞常见的方法有一下几种：
3.3.2树结构的基本概念
3.3.4二叉搜索树
二叉搜索树是一棵二叉树，其中每个节点都不能有多于两个子节点。
对于二叉查找树的每一个节点X，它的左子树中所有项的值都小于X节点中的项，而它的右子树中所有项的值大于X中的项。
04
常见数据结构与算法分析
4.1线性数据结构4.1.1HashMap
·总述
HashMap是开发中最常用的数据结构之一，数据常驻于内存中，对于小的数据量来说，HashMap的增删改查的效率都非常高，复杂度接近于O(1)。
·数据结构和算法
oHashMap由一个hash函数和一个数组组成；
§数据量较小的时候，链表的查询效率相对来说也比较高，使用红黑树占用空间比链表要大；
§为什么选择8，请参考泊松分布；
o查找和删除的过程，同插入的过程类似；
oHashMap可以支持自动扩容，扩容机制需要看具体的实现；
图2HashMap的构建过程示意图
优点：动态可变长存储数据，快速的查询速度，查询复杂度接近O(1);
缺点：只支持小数据量的内存查询；
在内存中小数据量的数据保存和快速查找。
4.1.2BloomFilter（布隆过滤器）
布隆过滤器的具体结构和算法为：
布隆过滤器的插入过程如下：
图3布隆过滤器的构建过程示意图
判断某个key是否在集合时，用k个hash函数算出k个值，并查询数组中对应的比特位，如果所有的bit位都为1，认为在集合中
·优缺点
缺点：布隆过滤器的缺点是有误差。元素越多误差越高。可以通过提高hash函数的个数和扩大bit数组的长度来降低误差率；
·场景
使用场景：缓存击穿，判断有无。
4.1.3SkipList（跳表）
跳表可视为水平排列（Level）、垂直排列（Row）的位置（Position）的二维集合。每个Level是一个列表Si，每个Row包含存储连续列表中相同Entry的位置，跳表的各个位置可以通过以下方式进行遍历。
图4跳跃列表结构示意图
有顺序关系的多个Entry(K,V)集合M可以由跳表实现，跳表S由一系列列表{S0，S1，S2，......，Sh}组成，其中h代表的跳表的高度。每个列表Si按照Key顺序存储M项的子集，此外S中的列表满足如下要求：
Si中的Entry是从Si-1中的Entry集合中随机选择的，对于Si-1中的每一个Entry，以1/2的概率来决定是否需要拷贝到Si中，我们期望S1有大约n/2个Entry，S2中有大约n/4个Entry，Si中有n/2^i。跳表的高度h大约是logn。从一个列表到下一个列表的Entry数减半并不是跳表的强制要求；
插入的过程描述，以上图为例，插入Entry58：
下图为随机数为1的结果图：
图5插入一个元素的过程示意图
删除过程：同查找过程。
o查找包括两个循环，外层循环是从上层Level到底层Level，内层循环是在同一个Level，从左到右;
o跳表的高度大概率为O(logn)，所以外层循环的次数大概率为O(logn);
o在上层查找比对过的key，不会再下层再次查找比对，任意一个key被查找比对的概率为1/2，因此内存循环比对的期望次数是2也就是O(1);
空间复杂度
oLeveli期望的元素个数为n/2^i；
o跳表中所有的Entry（包含同一个Entry的Row中的元素）Σn/2^i=nΣ1/2^i，其中有级数公式得到Σ1/2^i<2；
o期望的列表空间为O(n)；
优点：快速查找，算法实现简单；
·使用场景
许多开源的软件都在使用跳表：
4.2简单非线性数据结构
4.2.1AVL
AVL树是带有平衡条件的二叉查找树，这个平衡条件必须要容易保持，而且它保证树的深度必须是O(logN)。在AVL树中任何节点的两个子树的高度最大差别为1。
AVL树本质上还是一棵二叉查找树，有以下特点：
针对旋转做详细分析如下：
把必须重新平衡的节点叫做a，由于任意节点最多有两个儿子，因此出现高度不平衡就需要a点的两棵子树的高度差2。可以看出，这种不平衡可能出现一下四种情况：
情形1和4是关于a的对称，而2和3是关于a点的对称。因此理论上解决两种情况。
第一种情况是插入发生在外侧的情况，该情况通过对树的一次单旋转而完成调整。第二种情况是插入发生在内侧的情况，这种情况通过稍微复杂些的双旋转来处理。
单旋转的简单示意图如下：
图6单旋转示意图
双旋转的简单示意图如下：
图7双旋转示意图
缺点：插入和删除都需要进行再平衡，浪费CPU资源；
少量数据的查找和保存；
4.2.2RedBlackTree
红黑树是一种自平衡的二叉查找树，是2-3-4树的一种等同，它可以在O(logN)内做查找，插入和删除。
在AVL的基础之上，红黑树又增加了如下特点：
图8红黑树结构示意图
那么将一个节点插入到红黑树中，需要执行哪些步骤呢？
在第二步中，被插入的节点被着为红色之后，他会违背哪些特性呢
定理：一棵含有n个节点的红黑树的高度至多为2log(N+1)，证明过程请查看参考资料。
优点：查询效率高，插入和删除的失衡的代销比AVL要小很多。
缺点：红黑树不追求完全平衡。
4.2.3B+Tree
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位，位于同一块磁盘块中的数据会被一次性读取出来。InnoDB存储引擎中有页（Page）的概念，页是引擎管理磁盘的基本单位。
首先，先了解一下一棵m阶B-Tree的特性：
B-Tree很适合作为搜索来使用，但是B-Tree有一个缺点就是针对范围查找支持的不太友好，所以才有了B+Tree；
那么B+Tree的特性在B-Tree的基础上又增加了如下几点：
将上述特点描述整理成下图（假设一个页（Page）只能写四个数据）：
图9B+Tree结构示意图
这样的数据结构可以进行两种运算，一种是针对主键的范围查找和分页查找，另外一种是从根节点开始，进行随机查找；
缺点：插入或者删除数据有可能会导致数据页分裂；即使主键是递增的也无法避免随机写，这点LSM-Tree很好的解决了；无法支持全文索引；
使用场景大多数数据库的引擎，例如MySql,MongoDB等。
4.2.4HashTree
HashTree是一种特殊的树状结构，根据质数分辨定理，树每层的个数为1、2、3、5、7、11、13、17、19、23、29.....
从2起的连续质数，连续10个质数接可以分辨大约6464693230个数，而按照目前CPU的计算水平，100次取余的整数除法操作几乎不算什么难事。
我们选择质数分辨算法来构建一颗哈希树。选择从2开始的连续质数来构建一个10层的哈希树。第一层节点为根节点，根节点先有2个节点，第二层的每个节点包含3个子节点；以此类推，即每层节点的数据都是连续的质数。对质数进行取余操作得到的数据决定了处理的路径。下面我们以随机插入10个数（44290413460316429973663825090889064005）为例，来图解HashTree的插入过程，如下：