了解最长公共子序列算法的时间复杂度
Understanding the time complexity of the Longest Common Subsequence Algorithm
我不明白最长公共子序列算法的递归函数具有 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)
O(2^n)
表示 运行 时间 与 (2^n)
成比例 对于 足够大 n
。这并不意味着这个数字是坏的、高的、低的,或者任何特定于 small n
的东西,它也没有给出计算绝对 run-time.
要感受其中的含义,您应该考虑 n = 1000、2000、3000 甚至 100 万、200 万等的 run-times
在您的示例中,假设对于 n=5,算法最多进行 251 次迭代,那么 O(n)
预测是对于 n=50,它将在 范围内 2^(50)/2^(5)*251
= 2^45*251
= ~8.8E15
次迭代。
要正确理解它,请仔细查看图表并在阅读图表时遵循递归 top-to-down 方法。
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")
中的"AEC"
中删除"A"
的结果=] 和 lcs("BCD", "EC")
中 "BCD"
的 "B"
。结果,这些对将在执行时被调用不止一次,这增加了程序的时间复杂度。
您可以很容易地看到,每一对都会为其下一个级别生成两个结果,直到它遇到任何 空 字符串或 x==y
。因此,如果字符串的长度为n,m (考虑到xstr的长度为n
,ystr的长度为m
,我们考虑的是最坏的情况).然后,我们将在订单末尾有数字结果:2n+m。 (怎么?想)
因为,n+m 是一个整数,比方说 N。因此,算法的时间复杂度:O(2N),对于N[的较大值效率不高=59=].
因此,我们更喜欢 Dynamic-Programming 方法而不是递归方法。可以降低时间复杂度为:O(n.m) => O(n2) , 当 n == m.
即使是现在,如果您很难理解其中的逻辑,我建议您制作一个 tree-like
(不是我在这里展示的图表) xstr = "ABC"
和 ystr = "EF"
的表示。希望大家理解。
如有任何疑问,欢迎评论。
我不明白最长公共子序列算法的递归函数具有 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)
O(2^n)
表示 运行 时间 与 (2^n)
成比例 对于 足够大 n
。这并不意味着这个数字是坏的、高的、低的,或者任何特定于 small n
的东西,它也没有给出计算绝对 run-time.
要感受其中的含义,您应该考虑 n = 1000、2000、3000 甚至 100 万、200 万等的 run-times
在您的示例中,假设对于 n=5,算法最多进行 251 次迭代,那么 O(n)
预测是对于 n=50,它将在 范围内 2^(50)/2^(5)*251
= 2^45*251
= ~8.8E15
次迭代。
要正确理解它,请仔细查看图表并在阅读图表时遵循递归 top-to-down 方法。
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")
中的"AEC"
中删除"A"
的结果=] 和lcs("BCD", "EC")
中"BCD"
的"B"
。结果,这些对将在执行时被调用不止一次,这增加了程序的时间复杂度。您可以很容易地看到,每一对都会为其下一个级别生成两个结果,直到它遇到任何 空 字符串或
x==y
。因此,如果字符串的长度为n,m (考虑到xstr的长度为n
,ystr的长度为m
,我们考虑的是最坏的情况).然后,我们将在订单末尾有数字结果:2n+m。 (怎么?想)
因为,n+m 是一个整数,比方说 N。因此,算法的时间复杂度:O(2N),对于N[的较大值效率不高=59=].
因此,我们更喜欢 Dynamic-Programming 方法而不是递归方法。可以降低时间复杂度为:O(n.m) => O(n2) , 当 n == m.
即使是现在,如果您很难理解其中的逻辑,我建议您制作一个 tree-like
(不是我在这里展示的图表) xstr = "ABC"
和 ystr = "EF"
的表示。希望大家理解。
如有任何疑问,欢迎评论。