我写了一个代码来填充kmp的前缀表。这是algorithm的小变化我无法说服自己这个算法/实现运行在O（n）时间内我很难找出第二个递归调用对总运行时间的影响有什么帮助吗？
public void fillFailTable(int[] failTable,String p){
failTable[failTable.length-1] = preLength(failTable,p);
}
private int preLength(int[] failTable,String s){
if(s.length() == 1){
return 0;
}
int n = s.length();
int k = preLength(failTable,s.substring(0,n-1));
failTable[n-2] = k;
if(s.charAt(k) == s.charAt(n-1)){
return k+1;
}else{
return preLength(failTable,s.substring(n-1-k));
}
}
最佳答案
这真的很有趣（我还在想为什么还没有比我聪明的人回答这个问题）。请带着一点盐来理解这个解释，因为我不能百分之百地肯定这个解释是正确的（尽管我可以百分之百地告诉你这个方法在O（N）中运行，因为这是他们几年前在大学里告诉我的，但是他们没有费心解释，所以我不得不自己想出来）。
好的，让我们从一个非常基本的例子开始，s.length=2有两件事要事先提：
在每个例子中，我们只需要担心最坏的情况，因为我们对big oh感兴趣，这意味着我们进入了第二个prelength（）方法。
我们可以观察到，在寻找大oh时，此代码中的“k”（以及prelength（）返回的值）将始终为0，您将在下面的图像中注意到这一点，这一点非常重要。
s.长度==2
我们首先进入第一个preLength（）方法（让我们调用它*），该方法现在用s.length=1调用，并立即用0返回既然我们只考虑最坏的情况（意思是s.charAt（k）！=s.charat（n-1））我们输入第二个prelength（），其中还有一个长度为1的字符串（因为n=2和k=0）。这个也会立即返回0到我们的*这将结束我们的方法调用。总共有3个方法调用。我们的*和两个preLength（）这是一张图片：
s.长度==3
现在让我们看一个起始s.length=3的示例。正如您可以注意到的，我们立即调用一个s.length=2的preLength（），并且，从前面的示例中，我们知道这一个需要3个方法调用现在我们需要记住，当方法prelength（2）这次返回时，它将返回到我们的本地prelength（3），后者现在将再次调用prelength（2）（else中的那个），后者将再次需要3次方法调用。所以我们总共需要2*3+1个方法调用这给了我们7分。同样，这里有一个图像（圆是对preLength的调用，其字符串的长度如圆所示）：
结论
现在您可以看到所有这些方法调用都是对称的，这是因为我们的k始终等于0，这意味着第二个prelengt（）将使用与第一个相同大小的字符串来调用，并且当我们知道需要s.length = m的字符串有多少时，我们可以看到需要m-1的字符串有多少，因为f(m) = 2*f(m-1)+1的位置是这个函数告诉我们需要多少个方法调用来计算一个字符串f(m)的表这是因为正如我之前所说，方法调用是对称的（这是因为在最坏的情况下，k=0总是，preLenght（）总是返回0，因此2*需要添加1个方法调用，这是我们调用的第一个方法调用）。
因此，基本上，随着我们输入的每次递增（大小m），计算时间增长2倍加上1（2*m+1），据我所知，这意味着在最坏的情况下，这种方法是O（n）。
正如我所说的，请把这个和一粒盐放在一起，但我希望这是有意义的：）