检查链表中的子列表的方法的时间复杂度

Question

我需要写一个方法public int subList (CharList list)它获取一个列表并返回这个列表存在的次数。

例如:

我的列表是a b c d a b g e

参数列表如果a b，它将返回2。

我的列表是b b b b

参数列表是b b，它将返回3。

方法应该尽可能高效

目前我的问题是我不知道他们说尽可能高效是什么意思，如果我循环遍历列表n次，每次我找到相同的字符，我循环遍历列表并回到我所在的位置，它将是O(n^2)?有没有更好的方法让它小于等于O(n) ?

Answer 1

这是在字符串中有效搜索字符串，复杂度为0 (n)

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

当你找到第一个出现点时你可以继续在剩下的列表中寻找下一个出现点所以找到所有

Answer 2

为什么是O(n^2) ?它是O(n)，因为您只需要通过list迭代一次。

Answer 3

让我们使用char[]来简化解释。

简单方法如下:

public int countSublists (char[] list, char[] sublist)
    int count = 0;
    for (i = 0; i < list.length; i++) {
        for (j = 0; j <= sublist.length; j++) {
            if (j = sublist.length) {
               count++;
            } else if (i + j > list.length || list[i + j] != sublist[j]) {
               break;
            }
        }
    }
    return count;
}

这具有最坏情况 O(N*M)的复杂度，其中N是list的长度，M是sublist的长度。O(N)的最佳情况复杂度…当list中没有sublist的第一个字符的实例

还有其他各种算法可以提供更好的性能…降到(我认为)O(N/M)的最佳情况。一般的想法是，当存在不匹配时，使用list[i + j]中的字符值，以允许您跳过某些字符。

你可以从维基百科的字符串搜索算法页面找到各种高级搜索算法的详细信息…其中还包括各自算法复杂度的摘要。

但需要注意的是，高级搜索算法都涉及一些预计算步骤，其复杂性是M的某个函数。如果N足够小，预计算的成本可能超过搜索时间的节省。(另一方面，如果您在不同的列表中重复计算相同的子列表，并且您可以重用预计算表，那么您可以摊销预计算成本…)