Knuth-Morris-Pratt(KMP)算法时间复杂度分析

KMP与FINITE-AUTOMATION-MATCHER

   KMP算法是大学《数据结构》教材中的一个经典算法，但是大部分教材对该算法的讲解只是停留在应用的层面上；我认为，如果只是从应用的角度去看这个算法确实有些暴殄天物了，因为这个算法蕴含的思想是非常深刻的，比如KMP与有限状态自动机的联系。数据结构是大学计算机专业学生低年级的课程，在这个时期大多数同学不会接触到《编译原理》、《形式语言与自动机》这样的逻辑课程，甚至还没接触过《离散数学》。
  我在这里就不详细介绍自动机的一些概念了，有兴趣的读者可以去任意一本《编译原理》中去查阅。
在初学KMP算法的时候，最令我费解的是对next数组的计算，因为KMP算法是基于模式串自身匹配来计算next数组的这让我困惑，再加上数据结构中大部分是用汉字去描述这个算法，更是云雾缭绕。在学完自动机后回过头来重新审视KMP，发现KMP也是基于有限状态机的一种匹配算法，只不过它将状态转移函数换了个样子(即next数组)，并且next数组的含义应该是匹配的状态，而不仅仅是外在的模式串的移动，这是有根本却别的，只有把“像”抽象成为“意”这样的科学才能称为理论。

KMP时间复杂度分析

KMP伪代码如下：

 KMP-MATHCER(T,P)
 n = T.length
 m = P.length
 Π = COMPUTE-PREFIX-FUNCTION(P)
 q = 0
 for(i=1 to n)
 while q>0 and P[q+1]≠T[i]
 q = Π[q]
 if P[q+1] == T[i]
 q = q+1
 if q == m
 print "pattern occurs!"
 q = Π[q]

计算转移函数伪代码如下：

COMPUTE-PREFIX-FUNCTION(P)
m = P.length
let Π[1...m]be a new array
Π[1] = 0
k  = 0
for q = 2 to m
while k>0 and P[k+1]≠P[q]
k = Π[k]
if P[k+1] == P[q]
 k = k+1
 Π[q] = k
 return Π

大家都知道KMP算法是线性时间算法，但是大家看上面写的第二个伪代码，for中带while，怎么能是线性时间呢？学过算法分析与设计的同学都知道，一个算法的时间复杂度是和基本运算有关的，这个算法在循环体内的基本运算应该是while体内的赋值运算；此处的赋值运算是对k进行下降操作，而for循环体内的唯一对k的上升操作是k的自增运算，由于k<=m&&k>=0，所以下降操作是O(m)的，所以该算法是线性时间。

总结

对算法时间复杂度的把握应该从基础着手，不可臆断，就像KMP算法的分析，如果我们只是记住双重循环就是平方阶那么在这个算法的分析当中就大错特错了。