12

O(2^n)Longest Common Subsequence アルゴリズムの再帰関数の複雑さがわかりません。

通常、この表記法はアルゴリズムの基本操作 (この場合は比較) の数と関連付けることができますが、今回は意味がありません。

たとえば、同じ長さの 2 つの文字列があるとし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

注: 再帰呼び出しの適切な表現方法は通常、ツリー アプローチを使用して行われますが、ここではツリーを圧縮するためだけにグラフ アプローチを使用して、再帰呼び出しを簡単に理解できるようにしました。そしてもちろん、私が表現するのは簡単です。

  • 上の図では、 inからとinからlcs("CD", "EC")を削除した結果のような冗長なペアがいくつかあります。その結果、これらのペアは実行中に複数回呼び出され、プログラムの時間の複雑さが増します。"A""AEC"lcs("CD", "AEC")"B""BCD"lcs("BCD", "EC")

  • 空の文字列またはx==y. したがって、文字列の長さが n の場合、m (xstr の長さと ystr の長さをn考慮m して、最悪のシナリオを考えています)です。次に、順序の最後に2 n+mという数の結果があります。（どう？と思う）

n+mは整数なので、Nとしましょう。したがって、アルゴリズムの時間計算量はO(2 N )であり、これはNの値が大きい場合には効率的ではありません。

したがって、再帰的アプローチよりも動的プログラミングアプローチを優先します。n == m の場合、時間の複雑さをO(nm) => O(n 2 )に減らすことができます。

今でも、ロジックを理解するのに苦労している場合は、tree-like (ここに示したグラフではなく)xstr = "ABC"との表現を作成することをお勧めしますystr = "EF"。ご理解いただければ幸いです。

ご不明な点がございましたら、コメントをお待ちしております。

于 2016-01-09T09:48:30.883 に答える
2

O(2^n)は、実行時間が十分に大きい場合に比例することを意味します。数値が悪い、高い、低い、または小さなに固有のものであることを意味するものではなく、絶対実行時間を計算する方法を提供するものでもありません。(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 に答える