1

我写了一个代码来填充 KMP 的前缀表。这是这个算法的一个小变种。我无法说服自己这个算法/​​实现在 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));
        }
    }
4

1 回答 1

0

这实际上很有趣（我仍然想知道为什么没有比我更聪明的人回答这个问题）。请用一粒盐来解释这个解释，因为我不是 100% 确定这甚至接近正确（尽管我可以 100% 告诉你这个方法在 O(n) 中运行，因为这是他们在大学几年前，但他们并没有费心解释它，d'uh，所以我不得不自己想出它）。

好的，让我们从一个非常基本的 s.length = 2 示例开始。事先要提两件事：

  • 在每个示例中，我们只担心最坏的情况，因为我们对 Big Oh 感兴趣，这意味着我们进入第二个 preLength() 方法。
  • 我们可以观察到，在查找 Big Oh 时，此代码中的“k”（以及 preLength() 返回的值）将始终为 0，您会在下图中注意到这一点，这非常重要。

s.length == 2

我们首先进入第一个 preLength() 方法（我们称之为 *），现在调用 s.length = 1 并立即返回 0。现在因为我们只考虑最坏的情况（意思是 s.charAt( k) != s.charAt(n-1)) 我们输入第二个 preLength() 以及长度 = 1 的字符串（因为 n=2 和 k=0）。这个也立即返回一个 0 给我们的 *. 这结束了我们的方法调用。我们总共有 3 个方法调用。我们的 * 和两个 preLength()。这是一张图片：

在此处输入图像描述

s.length == 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() 将使用与第一个相同大小的字符串被调用——我们可以看到如何当我们知道需要多少它们时，我们将需要它们中的许多，因为函数在哪里告诉我们需要多少次方法调用来计算大小字符串的表。这是有效的，因为正如我之前所说的方法调用是对称的（这是因为在最坏的情况下 k=0 总是并且 preLenght() 总是返回 0，因此 2* 并且我们需要添加 1 个方法调用，这是我们曾经调用的第一个） .s.length = mm-1f(m) = 2*f(m-1)+1f(m)m

所以基本上随着我们输入的每次增量（大小m）计算时间增长 2 倍加上 1 (2*m+1)，据我了解，这意味着这种方法在最坏的情况下是 O(n)。

正如我所说的，请务必加一点盐，但我希望这是有道理的:)

于 2012-08-05T21:52:47.147 回答