3

我刚刚写了一个问题的答案：

最长公共子序列：为什么这是错误的？

这个函数应该找到两个字符串之间最长的子字符串，但是当我试图找出最坏情况的运行时间和导致这种情况的输入时，我意识到我不知道。将代码视为 C 伪代码。

// assume the shorter string is passed in as A
int lcs(char * A, char * B)
{
  int length_a = strlen(A);
  int length_b = strlen(B);

  // This holds the length of the longest common substring found so far
  int longest_length_found = 0;

  // for each character in one string (doesn't matter which), look for 
  //   incrementally larger strings in the other
  // once a longer substring can no longer be found, stop
  for (int a_index = 0; a_index < length_a - longest_length_found; a_index++) {
    for (int b_index = 0; b_index < length_b - longest_length_found; b_index++) {

      // check the next letter until a mismatch is found or one of the strings ends.
      for (int offset = 0; 
           A[a_index+offset] != '\0' && 
             B[b_index+offset] != '\0' && 
             A[a_index+offset] == B[b_index+offset]; 
           offset++) {          
        longest_length_found = longest_length_found > offset ? longest_length_found : offset;
      }
    }
  }
  return longest_found_length;
}

到目前为止，这是我的想法：

下面，我将假设 A 和 B 的大小大致相同，不必说 A B A，我只会说 n^3。如果这非常糟糕，我可以更新问题。

如果没有代码中的一些优化，我相信运行时是 N^3 运行时的 A B A。

但是，如果字符串不同并且从未找到过长的子字符串，那么最里面的 for 循环将退出为一个常量，从而为我们留下 A*B，对吗？

如果字符串完全相同，则该算法需要线性时间，因为每个字符串只有一次同时通过。

如果字符串相似但不相同，那么最长长度找到的将成为 A 或 B 中较小的一个的重要部分，这将划分 N ^ 3 中的一个因素，留下 N ^ 2，对吗？ 我只是想了解当它们非常相似但不相同时会发生什么。

大声思考，如果在第一个字母上，您找到一个长度约为 A 长度一半的子字符串。这意味着您将运行第一个循环的 A/2 次迭代，B-(A/2) 次迭代第二个循环，然后在第三个循环中最多 A/2 次迭代（假设字符串非常相似）而没有找到更长的子字符串。假设字符串长度大致相等，即 N/2 * N/2 * N/2 = O(N^3)。

可能显示此行为的示例字符串：

A A A B A A A B A A A B A A A B

A A A A B A A A A B A A A A B A

我是关闭还是我错过了什么或误用了什么？

我很确定我可以使用 trie/前缀树做得更好，但同样，我真的很想了解这个特定代码的行为。

4

2 回答 2

1

我认为roliu在评论中所说的是金钱。我认为你的算法是O(N 3 )，最好的情况是O(N 2 )。

我真正想指出的是这种算法的过度放纵。您会看到，对于每个字符串中每个可能的起始偏移量，您都会测试每个后续匹配字符以计算匹配数。但考虑这样的事情：

A = "01111111"
B = "11111110"

几乎您会发现的第一件事是从A[1]and开始的最大匹配子字符串B[0]，然后您将测试该精确重叠的部分，从 开始A[2]，B[1]依此类推......这里重要的是相对偏移量。通过实现这一点，您可以完全放弃算法的N 3部分。然后就变成了将其中一个阵列移到另一个阵列之下的问题。

A         01111111
B  11111110
B   11111110
B    11111110
B        ... -->
B                11111110

为了使代码不那么复杂，您可以只测试系统的一半，然后交换数组并测试另一半：

// Shift B under A
A  01111111
B  11111110
B      ... -->
B         11111110

// Shift A under B
B  11111110
A  01111111
A      ... -->
A         01111111

如果你这样做，那么你就会有类似O((A+B-2) * min(A,B) / 2)的东西，或者更方便的是O(N 2 )

int lcs_half(char * A, char * B)
{
    int maxlen = 0, len = 0;
    int offset, i;
    for( offset = 0; B[offset]; offset++ )
    {
        len = 0;
        for( i = 0; A[i] && B[i+offset]; i++ )
        {
            if( A[i] == B[i+offset] ) {
                len++;
                if( len > maxlen ) maxlen = len;
            }
            else len = 0;
        }
    }
    return maxlen;
}

int lcs(char * A, char * B)
{
    int run1 = lcs_half(A,B);
    int run2 = lcs_half(B,A);
    return run1 > run2 ? run1 : run2;
}
于 2013-05-20T03:26:21.437 回答
1

因此，在我们在评论中讨论它之后，我们同意问题是找到代码的最坏情况运行时。我们可以声称它至少Omega(n^3)有以下证明：

Let的
A = aaaa...aabb...bbbb意思是|A| = n它由n/2 a's和n/2 b's组成。
B = aaaa....哪里|B| = n。

现在我们考虑n/2最外层循环的第一次迭代（即字符串的第一个n/2起始索引）。A修复最外层循环的第一次迭代的i一些迭代。n/2第二个循环的上限至少 n-n/2 = n/2是因为两个字符串的 LCS 有 length n/2。对于第二个循环的每次迭代，我们匹配一个长度字符串n/2 - i（你可以通过矛盾来证明这一点）。因此，在n/2最外层循环的第一次迭代之后，我们得到了该行：

longest_length_found = longest_length_found > offset ? longest_length_found : offset;

已运行：

n/2*(n/2) + n/2*(n/2-1) + n/2*(n/2-2) + ... + n/2*(2) + n/2*(1) = n/2*Omega(n^2) = Omega(n^3)

具体来说，对于最外层循环的第一次迭代，我们在 string 中有一个n/2 a' 字符串A，并且在 中有n/2起始点B。对于中的每个起始点，B我们将匹配一个完整的公共子串长度n/2（这意味着我们将达到该行n/2时间）。就是这样n/2*(n/2)。对于最外层循环的下一次迭代，我们在 string 中有一个n/2-1 a's 字符串A，并且n/2在B. n/2-1在这种情况下，我们为每个起始索引匹配一个公共的长度子字符串=> n/2(n/2-1)。相同的论点可以归纳为i = n/2.

无论如何，我们知道算法在输入上的运行时间比n/2最外层循环的第一次迭代的运行时间长，所以它也是Omega(n^3).

于 2013-05-20T04:02:49.860 回答