理解最长公共子序列算法的时间复杂度

Question

我不理解最长公共子序列算法的递归函数所具有的O(2^n)复杂性。

通常，我可以将这个表示法与算法的基本操作数(在本例中为比较)联系起来，但这一次在我的脑海中没有意义。

例如，有两个长度相同的5字符串。在最坏的情况下，递归函数计算251比较。而2^5甚至还没有接近这个值。

有人能解释这个函数的算法复杂性吗？

def lcs(xstr, ystr):
    global nComp
    if not xstr or not ystr:
        return ""
    x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]
    nComp += 1
    #print("comparing",x,"with",y)
    if x == y:
        return x + lcs(xs, ys)
    else:
        return max(lcs(xstr, ys), lcs(xs, ystr), key=len)

Answer 1

O(2^n)意味着对于足够大的n，运行时与(2^n)成正比。这并不意味着这个数字是坏的、高的、低的，或者对于一个小的n来说是特定的，它也没有给出计算绝对运行时间的方法。

为了理解其含义，您应该考虑n= 1000,2000,3000，甚至100万，200万，等等的运行时间。

在您的示例中，假设对于n=5，算法的最大迭代次数为251次，那么O(n)的预测是对于n=50，它将在2^(50)/2^(5)*251 = 2^45*251 = ~8.8E15迭代的范围内进行。