我不理解递归函数用于“最长公共子序列”算法的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)
Here, xstr = "ABCD"
ystr = "BAEC"
lcs("ABCD", "BAEC") // Here x != y
/ \
lcs("BCD", "BAEC") <-- x==y --> lcs("ABCD", "AEC") x==y
| |
| |
lcs("CD", "AEC") <-- x!=y --> lcs("BCD", "EC")
/ \ / \
/ \ / \
/ \ / \
lcs("D","AEC") lcs("CD", "EC") lcs("BCD", "C")
/ \ / \ / \
lcs("", "AEC") lcs("D","EC") lcs("CD", "C") lcs("BCD","")
| \ / \ | / |
Return lcs("", "EC") lcs("D" ,"C") lcs("D", "") lcs("CD","") Return
/ \ / \ / \ / \
Return lcs("","C") lcs("D","") lcs("","") Return lcs("D","") Return
/ \ / \ / / \
Return lcs("","") Return lcs("", "") Return
| |
Return Return
注意：通常使用树形结构来表示递归调用的正确方式，但在这里我使用了图形方法来压缩树形结构，以便读者可以轻松理解递归调用。当然，这也更容易让我进行表达。
由于上图中有一些冗余对，例如lcs("CD", "EC")是从lcs("CD", "AEC")中删除"A"和"BCD"是从lcs("BCD", "EC")中删除"B"得到的结果。因此，在执行过程中会多次调用这些对，这增加了程序的时间复杂度。
正如您可以轻松看出每个对都会生成两个结果，直到遇到任何空字符串或x==y为止。因此，如果字符串的长度分别为n，m (考虑xstr的长度为n，ystr的长度为m，我们考虑最坏情况)。那么，最终我们将有2n+m个结果。（如何思考？）
既然n+m是一个整数，假设为N。因此，算法的时间复杂度为：O(2N)，对于较大的N值来说并不高效。
因此，我们更喜欢使用动态规划方法而不是递归方法。它可以将时间复杂度降低到：O(n.m) => O(n2)，当n == m时。
即使现在您还很难理解逻辑，我建议您为xstr="ABC"和ystr="EF"制作一个树形结构表示（不是我展示的图形）。我希望您能理解它。
如有疑问，请随时发表评论。
O(2^n) 表示运行时间对于足够大的 n 与 (2^n) 成比例。它并不意味着这个数字是坏的、高的、低的或特定的小 n，也不能给出计算绝对运行时间的方法。O(n) 的预测是当 n=50 时，需要 2^(50)/2^(5)*251 = 2^45*251 = ~8.8E15 次迭代。