algorithm - 每次运行分成两个递归算法的时间复杂度 moSTLy

Question

动态编程 |集合 33(查找一个字符串是否与另外两个字符串交错)

http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/

我在这个网站上发现了一个问题，它说“递归解决方案的最坏情况时间复杂度是 O(2^n)”。因此，我试着画了一个关于这道题最坏情况的树状图。我假设当a和b的长度和值相同时，会导致最坏的情况。它将分成两部分，直到 a/b 的长度为 0(使用子字符串)。

                    aa,aa,aaaa
                   /          \
                  /            \ 
           a,aa,aaa             aa,a,aaa
          /        \           /        \
         /          \         /          \
     -,aa,aa     a,a,aa     a,a,aa     aa,-,aa
    /           /    |        |   \           \
   /           /     |        |    \           \
-,a,a       -,a,a  a,-,a   -,a,a  a,-,a      a,-,a

在这种情况下，它有13个节点，这确实是最坏的情况，但是如何逐步计算呢？如果 c 的长度增加 2，它将得到 49 个节点。如果增加到一个很大的数，就很难画出树状图。

有人可以详细解释一下吗？

Answer 1

运行时间的递归是

T(n) = 2T(n-1)

如果您绘制递归树，您会看到您有一个 height = n 的二叉树。

因为它是一棵二叉树，它将有 2^n 个叶子，因此最坏的情况是 O(2^n)。