1.算法定义

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

一个算法应该具有以下七个重要的特征：
①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；

②确切性(Definiteness)：算法的每一步骤必须有确切的定义；

③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输     入是指算法本身定出了初始条件；

④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没       有输出的算法是毫无意义的；

⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行       的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；

⑥高效性(High efficiency)：执行速度快，占用资源少；

⑦健壮性(Robustness)：对数据响应正确。
2. 时间复杂度

计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间,时间复杂度常用大O符号（大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。）表述，使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

大O，简而言之可以认为它的含义是“order of”（大约是）。
无穷大渐近

大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为 n 的问题所花费的时间（或者所需步骤的数目）可以被求得：T(n) = 4n^2 - 2n + 2。 当 n 增大时，n^2; 项将开始占主导地位，而其他各项可以被忽略——举例说明：当 n = 500，4n^2; 项是 2n 项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。

3.时间复杂度计算方法
1.一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
2.一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））。随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。
3.常见的时间复杂度

按数量级递增排列，常见的时间复杂度有：

常数阶O(1),  对数阶O(log2n),  线性阶O(n),  线性对数阶O(nlog2n),  平方阶O(n^2)， 立方阶O(n^3),…， k次方阶O(n^k), 指数阶O(2^n) 。
其中，
1.O(n)，O(n^2)， 立方阶O(n^3),…， k次方阶O(n^k) 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度。。。。

2.O(2^n)，指数阶时间复杂度，该种不实用

3.对数阶O(log2n),   线性对数阶O(nlog2n)，除了常数阶以外，该种效率最高
例：算法：
  for（i=1;i<=n;++i）
  {
     for(j=1;j<=n;++j)
     {
         c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n^2
          for(k=1;k<=n;++k)
               c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n^3
     }
  }
  则有 T（n）= n^2+n^3，根据上面括号里的同数量级，我们可以确定 n^3为T（n）的同数量级
  则有f（n）= n^3，然后根据T（n）/f（n）求极限可得到常数c
  则该算法的 时间复杂度：T（n）=O（n^3)

4.讨论
定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。
当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。
我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。
此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。
“大O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。
O(1)

Temp=i;i=j;j=temp;                    

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
     sum=0；                 （一次）
     for(i=1;i<=n;i++)       （n次 ）
        for(j=1;j<=n;j++) （n^2次 ）
         sum++；       （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.   
    for (i=1;i<n;i++)
    {
        y=y+1;         ①   
        for (j=0;j<=(2*n);j++)    
           x++;        ②      
    }         
解： 语句1的频度是n-1
          语句2的频度是(n-1)*(2n+1)=2n^2-n-1
          f(n)=2n^2-n-1+(n-1)=2n^2-2
          该程序的时间复杂度T(n)=O(n^2).         

O(n)      
                                                      
2.3.
    a=0;
    b=1;                      ①
    for (i=1;i<=n;i++) ②
    {  
       s=a+b;　　　　③
       b=a;　　　　　④  
       a=s;　　　　　⑤
    }
解：语句1的频度：2,        
           语句2的频度： n,        
          语句3的频度： n-1,        
          语句4的频度：n-1,    
          语句5的频度：n-1,                                  
          T(n)=2+n+3(n-1)=4n-1=O(n).
                                                                                                 
O(log2n )

2.4.
     i=1;       ①
    while (i<=n)
       i=i*2; ②
解： 语句1的频度是1,  
          设语句2的频度是f(n),   则：2^f(n)<=n;f(n)<=log2n    
          取最大值f(n)= log2n,
          T(n)=O(log2n )

O(n^3)

2.5.
    for(i=0;i<n;i++)
    {  
       for(j=0;j<i;j++)  
       {
          for(k=0;k<j;k++)
             x=x+2;  
       }
    }
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).


我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。

下面是一些常用的记法：
访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对 元素相乘并加到一起，所有元素的个数是n^2。

指数时间算法通常来源于需要求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。
5.常用排序

由于我之前一直强调数据结构以及算法学习的重要性，所以就有一些读者经常问我，数据结构与算法应该要学习到哪个程度呢？，说实话，这个问题我不知道要怎么回答你，主要取决于你想学习到哪些程度，不过针对这个问题，我稍微总结一下我学过的算法知识点，以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的，并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构，当然，我也会整理一些看过不错的文章给大家。大家也可以留言区补充。
一、算法最最基础
1、时间复杂度
2、空间复杂度
一般最先接触的就是时间复杂度和空间复杂度的学习了，这两个概念以及如何计算，是必须学的，也是必须最先学的，主要有最大复杂度、平均复杂度等，直接通过博客搜索学习即可。
文章推荐：
算法分析神器—时间复杂度
二、基础数据结构
1、线性表

列表（必学）
链表（必学）
跳跃表（知道原理，应用，最后自己实现一遍）
并查集（建议结合刷题学习）

不用说，链表、列表必须，不过重点是链表。
三分钟基础数据结构：如何轻松手写链表？
以后有面试官问你「跳跃表」，你就把这篇文章扔给他
2、栈与队列

栈（必学）
队列（必学）
优先队列、堆（必学）
多级反馈队列（原理与应用）

特别是优先队列，再刷题的时候，还是经常用到的，队列与栈，是最基本的数据结构，必学。可以通过博客来学习。相关文章：
三分钟基础知识：什么是栈？
二叉堆是什么鬼？
【算法与数据结构】堆排序是什么鬼？
3、哈希表（必学）

碰撞解决方法：开放定址法、链地址法、再次哈希法、建立公共溢出区（必学）
布隆过滤器（原理与应用）

哈希表相关的，推荐通过博客来学习，推荐文章：
Hash冲突之开放地址法
4、树

二叉树：各种遍历（递归与非递归）（必学）
哈夫曼树与编码（原理与应用）
AVL树（必学）
B 树与 B+ 树（原理与应用）
前缀树（原理与应用）
红黑树（原理与应用）
线段树（原理与应用）

树相关是知识还是挺多的，建议看书，可以看《算法第四版》。相关文章：
高频面试题：什么是B树？为啥文件索引要用B树而不用二叉查找树？
【漫画】以后在有面试官问你AVL树，你就把这篇文章扔给他。
腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？
【面试被虐】游戏中的敏感词过滤是如何实现的？
5、数组

树状数组
矩阵（必学）

树状数组其实我也没学过，，，，
三、各种常见算法
1、十大排序算法

简单排序：插入排序、选择排序、冒泡排序（必学）
分治排序：快速排序、归并排序（必学，快速排序还要关注中轴的选取方式）
分配排序：桶排序、基数排序
树状排序：堆排序（必学）
其他：计数排序（必学）、希尔排序

对于十大算法的学习，假如你不大懂的话，那么我还是挺推荐你去看书的，因为看了书，你可能不仅仅知道这个算法怎么写，还能知道他是怎么来的。推荐书籍是《算法第四版》，这本书讲的很详细，而且配了很多图演示，还是挺好懂的。
推荐文章：
必学十大经典排序算法，看这篇就够了(附完整代码/动图/优质文章)(修订版)
2、图论算法

图的表示：邻接矩阵和邻接表
遍历算法：深度搜索和广度搜索(必学)
最短路径算法：Floyd，Dijkstra（必学）
最小生成树算法：Prim，Kruskal（必学）
实际常用算法：关键路径、拓扑排序（原理与应用）
二分图匹配：配对、匈牙利算法（原理与应用）
拓展：中心性算法、社区发现算法（原理与应用）

图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。
漫画：什么是 “图”？（修订版）
漫画：深度优先遍历 和 广度优先遍历
漫画：图的 “最短路径” 问题
漫画：Dijkstra 算法的优化
漫画：图的 “多源” 最短路径

更多算法的学习，欢迎关注我的公众号『帅地玩编程』

3、搜索与回溯算法

贪心算法（必学）
启发式搜索算法：A*寻路算法（了解）
地图着色算法、N 皇后问题、最优加工顺序
旅行商问题

这方便的只是都是一些算法相关的，我觉得如果可以，都学一下。像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。
4、动态规划

树形DP：01背包问题
线性DP：最长公共子序列、最长公共子串
区间DP：矩阵最大值（和以及积）
数位DP：数字游戏
状态压缩DP：旅行商

我觉得动态规划是最难的一个算法思想了，记得当初第一次接触动态规划的时候，是看01背包问题的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做题下不了手，但是看的懂答案。一气之下，再leetcdoe专题连续刷了几十道，才掌握了动态规划的套路，也有了自己的一套模板。不过说实话，动态规划，是考的真他妈多，学习算法、刷题，一定要掌握。这里建议先了解动态规划是什么，之后 leetcode 专题刷，反正就一般上面这几种题型。后面有时间，我也写一下我学到的套路，有点类似于我之前写的递归那样，算是一种经验。也就是我做题时的模板，不过感觉得写七八个小时，，，，，有时间就写。之前写的递归文章：为什么你学不会递归？告别递归，谈谈我的一些经验
5、字符匹配算法

正则表达式
模式匹配：KMP、Boyer-Moore

我写过两篇字符串匹配的文章，感觉还不错，看了这两篇文章，我觉得你就差不多懂 kmp 和 Boyer-Moore 了。
字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？

更多算法的学习，欢迎关注我的公众号『苦逼的码农』

6、流相关算法

最大流：最短增广路、Dinic 算法
最大流最小割：最大收益问题、方格取数问题
最小费用最大流：最小费用路、消遣

这方面的一些算法，我也只了解过一些，感兴趣的可以学习下。
总结
对于上面设计到的算法，我都提供了感觉还不错的文章，建议大家收藏，然后可以利用零碎的时间进行阅读，有些人可能会觉得上面的算法太多，说实话，我觉得不多，特别是对于在校生的，上面涉及到的算法可以不用很懂，但至少得了解。至于书籍的话，如果你连基本数据结构都还不懂的，建议看《数据结构与算法》相关书籍，例如《大话数据结构》、《数据结构与算法分析》。如果你有一定的基础，例如知道链表，栈，队列，那么可以看《算法第四版》，不过这本书是用 Java 实现的，不过我觉得你只要学过 C，那么可以看的懂。
这些算法的学习，虽然你觉得学了没有什么用，但还是那些话，它对你的影响是潜意识的，它可以给你打下很深厚的基础内功，如果你想走的更远，那么我推荐学习，标注必学的，那么我觉得，你是真的需要抽时间来学习下，标注原理与应用的，代表你可以不知道怎么用代码实现，但是必得知道它的实现原理以及应用，更多算法的学习，可以持续关注我的微信公众号勒。
作为一个非常注重计算机基础以及算法学习的程序员，一路自学走来，看过挺多不错的优质书籍，在这里推荐给大家，全都是自己看过滴。
最后，很多人问我都是怎么学习的，那我干脆就把我看过的优质书籍贡献出来：
计算机基础入门推荐：《程序是怎样跑起来的》、《网络是怎样连接的》、《计算机是怎样工作的》
进一步认识计算机网络：《计算机网络:自顶向下》、《图解http》
数据结构+算法入门：《数据结构与算法分析：C语言描述版》，《大话数据结构》、《阿哈算法》
算法进阶：《算法第四版》、《编程之美》、《编程珠玑》
由于我是Java技术栈的，顺便推荐基本Java的书籍，从左到由的顺序看到
Java：《Java核心技术卷1》、《编程思想》、《深入理解Java虚拟机》、《Java编程艺术》
数据库：《mysql必知必会》、《MySQL技术内幕：InnoDB存储引擎》
就先介绍这么多，这些都是最基础最核心滴，希望对那些不知道看什书的同学有所帮助

对了，我介绍的这些书籍，我顺便帮你整理好了，你可以在我的原创微信公众号『帅地玩编程』回复『书籍』获取哦

另外，帅地把公众号的精华文章整理成了一本电子书，共 630页！目录如下



现在免费送给大家，在我的公众号帅地玩编程回复程序员内功修炼即可获取。
有收获？希望老铁们来个三连击，给更多的人看到这篇文章
1、老铁们，关注我的原创微信公众号「帅地玩编程」，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux），保存让你看完有所收获，不信你打我。
2、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。
作者info

作者：帅地，一位热爱写作的小伙

原创公众号：『帅地玩编程』，已写了150多篇文章，专注于写 算法、计算机基础知识等提升你内功的文章，期待你的关注。

转载说明：务必注明来源（注明：来源于公众号：苦逼的码农， 作者：帅地）

   程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结

 



作者：July--结构之法算法之道blog之博主。

时间：2010年10月-2018年5月，一直在不断更新中..

出处：http://blog.csdn.net/v_JULY_v 。

说明：本博客中部分文章经过不断修改、优化，已集结出版成书《编程之法：面试和算法心得》。

 

前言

    开博4年有余，回首这4年，自己的研究兴趣从最初的编程、面试、数据结构、算法，转移到最近的数据挖掘、机器学习之上，而自己在本blog上也着实花费了巨大的时间和精力，写的东西可能也够几本书的内容了。然不管怎样，希望我能真真正正的为读者提供实实在在的价值与帮助。

    下面，敬请观赏。有任何问题，欢迎随时不吝指正(同时，若你也能帮助回复blog内留言的任何朋友的问题，欢迎你随时不吝分享&回复，我们一起讨论，互帮互助，谢谢)。

 

无私分享，造福天下

    以下是本blog内的微软面试100题系列，经典算法研究系列，程序员编程艺术系列，红黑树系列，及数据挖掘十大算法等5大经典原创系列作品与一些重要文章的集锦：
一、微软面试100题系列

横空出世，席卷Csdn--评微软等数据结构+算法面试100题 （微软面试100题系列原题+答案索引）
	
微软100题   （微软面试完整第1-100题）
	
微软面试100题2010年版全部答案集锦（含下载地址）
	
全新整理：微软、谷歌、百度等公司经典面试100题[第101-160题] 
	
全新整理：微软、Google等公司的面试题及解答[第161-170题]  
	
十道海量数据处理面试题与十个方法大总结  （十道海量数据处理面试题）
	
海量数据处理面试题集锦与Bit-map详解  （十七道海量数据处理面试题）
	
教你如何迅速秒杀掉：99%的海量数据处理面试题   （海量数据处理PDF）
	
九月腾讯，创新工场，淘宝等公司最新面试三十题（第171-200题） （2011年度九月最新面试三十题）
	
十月上旬百度，阿里巴巴，迅雷搜狗最新面试七十题（第201-270题） （2011年度十月上旬七十题）
	
十月下旬腾讯，网易游戏，百度最新校园招聘笔试题集锦(第271-330题)  （2011年度十月下旬校招）
	
九月十月百度人搜，阿里巴巴，腾讯华为笔试面试八十题(第331-410题)  （2012年度笔试面试八十题）
	
九月百度，迅雷，华为，阿里巴巴，最新校招笔试面试十(第411-470题)   （2013年度校招笔试面试十题）
    上述微软面试100题系列(共计11篇文章，300多道面试题)的PDF文档近期已经制作出来，其下载地址为：http://download.csdn.net/detail/v_july_v/4583815。

二、十五个经典算法研究与总结、目录+索引

一、A*搜索算法
	
一（续）、A*，Dijkstra，BFS算法性能比较及A*算法的应用
	
二、Dijkstra 算法初探          （Dijkstra算法系列4篇文章）
	
二（续）、彻底理解Dijkstra算法
	
二（再续）、Dijkstra 算法+fibonacci堆的逐步c实现
	
二（三续）、Dijkstra 算法+Heap堆的完整c实现源码
	
三、dynamic programming
	
四、BFS和DFS优先搜索算法 
	
五、教你透彻了解红黑树     （红黑树系列6篇文章之其中两篇）
	
五（续）、红黑树算法的实现与剖析
	
六、教你初步了解KMP算法 
	
六（续）、从KMP算法一步一步谈到BM算法
	
六（三续）、从头到尾彻底理解KMP   （KMP的PDF）
	
七、遗传算法 透析GA本质
	
八、再谈启发式搜索算法
	
九、图像特征提取与匹配之SIFT算法      (sift算法系列五篇文章)
	
九（续）、sift算法的编译与实现
	
九（再续）、教你一步一步用c语言实现sift算法、上
	
九（再续）、教你一步一步用c语言实现sift算法、下
	
九（三续）：SIFT算法的应用--目标识别之Bag-of-words模型
	
九（四续）、SIFT + KD_BBF算法 （此文第3部分）
	
十、从头到尾彻底理解傅里叶变换算法、上
	
十、从头到尾彻底理解傅里叶变换算法、下
	
十一、从头到尾彻底解析Hash表算法
	
十一（续）、倒排索引关键词Hash不重复编码实践
	
十二、快速排序算法      （快速排序算法3篇文章）
	
十二（续）、快速排序算法的深入分析
	
十二（再续）：快速排序算法之所有版本的c/c++实现
	
十三、通过浙大上机复试试题学SPFA 算法
	
十四、快速选择SELECT算法的深入分析与实现
	
十五、多项式乘法与快速傅里叶变换
    最新的十五个经典算法研究的PDF文档0积分下载地址如下(1个月5000+人次下载)：http://download.csdn.net/detail/v_july_v/4478027。

   「此外原来的十三个经典算法研究[带目录+标签]的PDF文档，Csdn下载地址：http://download.csdn.net/source/3427838；新浪爱问共享下载地址：http://ishare.iask.sina.com.cn/f/16968707.html 」。

三、程序员编程艺术第一~四十章集锦与总结

第一章、左旋转字符串
	
第二章、字符串是否包含问题
	
第三章、寻找最小的k个数
	
第三章续、Top K算法问题的实现
	
第三章再续：快速选择SELECT算法的深入分析与实现
	
三之三续、求数组中给定下标区间内的第K小（大）元素
	
第四章、现场编写类似strstr/strcpy/strpbrk的函数
	
第五章、寻找满足条件的两个或多个数
	
第六章、求解500万以内的亲和数
	
第七章、求连续子数组的最大和
	
第八章、从头至尾漫谈虚函数
	
第九章、闲话链表追赶问题
	
第十章、如何给10^7个数据量的磁盘文件排序
	
第十一章、最长公共子序列（LCS）问题
	
第十二~十五章：数的判断，中签概率，IP访问次数，回文问题（初稿）
	

	
第十六~第二十章：全排列/跳台阶/奇偶调序，及一致性hash算法
	
	

	
第二十一~二十二章：出现次数超过一半的数字，最短摘要的生成
	
	

	
第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践
	
	

	
第二十五章：Jon Bentley：90%无法正确实现二分查找
	
	
第二十六章：基于给定的文档生成倒排索引的编码与实践
	
第二十七章：不改变正负数之间相对顺序重新排列数组
	
第二十八~二十九章：最大连续乘积子串、字符串编辑距离
	
第三十~三十一章：字符串转换成整数，字符串匹配问题
	
第三十二~三十三章：最小操作数，木块砌墙问题
	
第三十四~三十五章：格子取数问题，完美洗牌算法
	
第三十六~三十七章、搜索智能提示suggestion，附近地点搜索
	
第三十八章：Hero在线编程判题、出题系统的演进与优化
	
第三十九~四十章：最近公共祖先LCA问题、打印螺旋矩阵
	
第四十一章~四十二章：荷兰国旗、矩阵相乘Strassen算法
	
...
    程序员编程艺术第1~37章带标签的最新PDF下载地址为（3天3000人下载）：http://download.csdn.net/detail/v_july_v/6694053。

   编程艺术github优化版阅读地址：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/Readme.md。

   重大消息：经过反复修改、优化，编程艺术系列最终成书出版，并改名为《编程之法：面试和算法心得》，目前京东、当当、亚马逊等各大网店均已有现货销售。京东抢购地址：http://item.jd.com/11786791.html。

四、红黑树、B树、R树、Trie树

教你初步了解红黑树  （红黑树系列）
	
红黑树算法的实现与剖析
	
红黑树的C实现完整源码
	
一步一图一代码，R-B Tree
	
红黑树插入和删除结点的全程演示
	
红黑树的C++完整实现源码
	
从2-3-4树谈到Red-Black Tree（红黑树）
	
从B树、B+树、B*树谈到R 树   （B树的PDF）
	
B树的C 实现
	
从Trie树（字典树）谈到后缀树  （其余树结构）
	
从LSM-Tree、COLA-Tree谈到StackOverflow、OSQA
五、数学·数据挖掘·机器学习·深度学习系列


	
5.1 AI数学基础
	
	
数据挖掘中所需的概率论与数理统计知识、上
	
一文通透优化算法：从随机梯度、随机梯度下降法到牛顿法、共轭梯度
	
5.2 AI经典模型
	
数据挖掘领域十大经典算法初探
	
从K近邻算法、距离度量谈到KD树、SIFT+BBF算法 
	
从决策树学习谈到贝叶斯分类算法、EM、HMM
	
支持向量机通俗导论（理解SVM的三层境界）   PDF下载    LaTeX版本1    LaTeX版本2
	
最大熵模型中的数学推导
	
如何通俗理解EM算法
	
Adaboost 的原理与推导    LaTeX版本下载
	
从拉普拉斯矩阵说到谱聚类
	
从贝叶斯方法谈到贝叶斯网络    LaTeX版本下载
	
通俗理解LDA主题模型    LaTeX版本下载
	
CNN笔记：通俗理解卷积神经网络
	
图解CNN：通过100张图一步步理解CNN
	
一文读懂目标检测：R-CNN、Fast R-CNN、Faster R-CNN、YOLO、SSD
	
通俗理解kaggle比赛大杀器xgboost
	
如何从RNN起步，一步一步通俗理解LSTM
	
如何通俗理解word2vec
	
..
	
5.3 AI工程实践
	
一文读懂特征工程
	
教你从头到尾利用DL学梵高作画：GTX 1070 cuda 8.0 tensorflow gpu版
	
没GPU也能玩梵高作画：Ubuntu tensorflow CPU版
	
基于torch学汪峰写歌词、聊天机器人、图像着色/生成、看图说话、字幕生成
	
教你从头到尾利用DQN自动玩flappy bird（全程命令提示，GPU+CPU版）
	
手把手教你搭建caffe及手写数字识别（Ubuntu下且附mac、纯通俗教程）
	
如何从零起步学习AI（附学习路线）
	
GAN之父在NIPS 2016上做的报告：两个竞争网络的对抗（含译文下载）
	
Kaggle—So Easy!百行代码实现排名Top 5%的图像分类比赛
	
BAT机器学习面试1000题系列（第1~500题）
六、其它重要文章节选


	
6.1、经典数据结构 & 算法系列：
	
	

	
精通八大排序算法系列：一之续、快速排序算法的深入分析

	
几个最短路径算法Floyd、Dijkstra、Bellman-Ford、SPFA的比较
	

	
6.2、数据处理/网站架构系列：
	
	

	
从Hadhoop框架与MapReduce模式中谈海量数据处理

	
MapReduce技术的初步了解与学习

	
海量数据处理之Bloom Filter详解

	
从上百幅架构图中学大型网站建设经验（上）
	
	
Chrome源码剖析、上--多线程模型、进程通信、进程模型
	
Nginx源码剖析之内存池，与内存管理
6.4、推荐 & 搜索算法系列：
	
细数二十世纪最伟大的10大算法     
	
当今世界最为经典的十大算法--投票进行时    （本blog将评选出当今世界最为经典的十大算法）
	
推荐引擎算法学习导论
	
搜索引擎技术之概要预览
6.5、其它：
	
程序员如何快速准备面试中的算法
	
重启开源，分享无限--诚邀你加入微软面试187题的解题中
	
敏捷软件开发模型Scrum通俗讲义
	
由快速排序引申而来--如何学习算法
Machine Learning读书会,面试算法讲座,创业活动,算法班(14年10月)   （含所有线下讲座PPT 集锦）
	
三五杆枪，可干革命，三五个人，可以创业
	
结构之法算法之道blog博文集锦第6、第7期CHM文件 第8期  第9期下载（第9期截止到2014年12月9日）
	
....
 

后记

    世上本无路，走的人多了，也就成了路。世上本无免费的午餐，分享的人多了，也就造就了开源的辉煌。

    如果你发现了本blog中的任何一个错误，漏洞，bug，和问题，请一定不吝指正，thanks。此外，你可以永久通过搜索引擎搜索本博客名称的前4个字，即：“结构之法” 这4个关键字，进入本博客。

    最后，感谢CSDN，感谢所有一直以来关注本blog的所有朋友。谢谢大家，谢谢。

 

转发送书

    欢迎大家转发下条微博：http://weibo.com/1580904460/zqzTgyAW3，我会不定期抽奖，经典IT图书大赠送（同时，下面个人最喜欢的三篇文章已收录到今2015年10月14日上市销售的我的新书《编程之法：面试和算法心得》中：http://item.jd.com/11786791.html）：





2015年，July团队正式创业，上半年推出在线教育网站：https://www.julyedu.com/category/index（面试、算法、机器学习在线课程）。July、二零一五年九月十五日。

另，我的新书《编程之法：面试和算法心得》终于在2015年10月14日上架开卖了！京东抢购地址：http://item.jd.com/11786791.html。目前，京东、当当、亚马逊等各大网店均已有现货销售。

大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
本文的逻辑顺序为

1、最基本的朴素算法

2、优化的KMP算法

3、应算法需要定义的next值

4、手动写出较短串的next值的方法

5、最难理解的、足足有5行的代码的求next值的算法

所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：


这个算法简单，不多说，附上代码
#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s[i]==p[j]){i++;j++;}
        else{
            i = i-j+2;
            j = 1;
        }
    }
    if(j>pLen) return i-pLen;
    return 0;
}
void main(){
    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
}

三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。

一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。

朴素算法中，P的第j位失配，默认的把P串后移一位。

但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：


这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
相比朴素算法：

朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)

KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S[i]与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）


比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的




假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”




那么可以推出，P1…Pk-1与Si…Si+j-2




显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：




为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。


最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。


四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：



这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch[i]==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}



还是先由一般再推优化：

直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）

根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。

不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：

if(P1…Pj-1 == P2…Pj)    => next[j+1]=j

else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1

else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2

…

…

…

else if(P1P2 == Pj-1Pj) => next[j+1]=3

else if(P1 == Pj-1) => next[j+1]=2

else if(P1 != Pj-1) => next[j+1]=1

每次前去尾1个，后掐头1个，直至得到next[j+1]


再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。

但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，

①next[j+1]的可能的最大值是多少（即从哪开始验证）

②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）

看一下的分析：


1、next[j+1]的最大值为next[j]+1。

因为：

假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。

如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1

2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]

这里不好解释，直接看下面的流程分析及图解
开——始——划——重——点！

从头走一遍流程

①求next[j+1]，设值为m

②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1

③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则

④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1

⑤第二第三步联合得到:

P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合

⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 =  Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：

1、要求next[k+1] 其中k+1=17



2、已知next[16]=8，则元素有以下关系：



3、如果P8=P16，则明显next[17]=8+1=9

4、如果不相等，又若next[8]=4，则有以下关系



又加上2的条件知



主要是为了证明：



5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推

6、若next[4]=2，则有以下关系



7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！