12

我不明白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)
4

2 回答 2

11

要正确理解它，请仔细查看图表，并在阅读图表时遵循自上而下的递归方法。

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")删除"A"from the "AEC"inlcs("CD", "AEC")和 of "B"from the "BCD"in的结果lcs("BCD", "EC")。结果，这些对将在执行时被多次调用，这增加了程序的时间复杂度。

  • 您可以很容易地看到，每一对都会为其下一级生成两个结果，直到遇到任何空字符串或x==y. 因此，如果字符串的长度为 n，m （考虑 xstrn和 ystr的长度m ，我们正在考虑最坏的情况）。然后，我们将在订单结束时得到数字结果：2 n+m。（怎么样？想想）

因为，n+m是一个整数，让我们说N。因此，算法的时间复杂度：O(2 N ) ，对于较大的N值无效。

因此，我们更喜欢动态编程方法而不是递归方法。它可以将时间复杂度降低到：O(nm) => O(n 2 )，当 n == m 时。

即使是现在，如果您很难理解逻辑，我建议您为and制作一个tree-like （不是我在此处显示的图表）表示。我希望你能理解。xstr = "ABC"ystr = "EF"

有任何疑问，欢迎评论。

于 2016-01-09T09:48:30.883 回答
2

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

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

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

于 2016-01-08T23:59:33.830 回答