动态编程 |集合 33(查找一个字符串是否与另外两个字符串交错)
我在这个网站上发现了一个问题,它说“递归解决方案的最坏情况时间复杂度是 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 个节点。如果增加到一个很大的数,就很难画出树状图。
有人可以详细解释一下吗?
最佳答案
运行时间的递归是
T(n) = 2T(n-1)
如果您绘制递归树,您会看到您有一个 height = n
的二叉树。
因为它是一棵二叉树,它将有 2^n
个叶子,因此最坏的情况是 O(2^n)
。
关于algorithm - 每次运行分成两个递归算法的时间复杂度 moSTLy,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33976238/