用代换法求解递归

Question

因此，我目前正在选修算法课程，我有一个问题，解决了递归，并获得了运行时间。我想知道是否有人能用外行的术语向我解释如何用替代方法来解决这个问题。

书中的问题:算法B通过递归地解决大小n，−1的两个子问题，然后在恒定时间内组合这些解来解决n个大小的问题。

这导致我想出了以下的重复：T(n)=2T(n-1)+O(1)。然后我想出了O(1)=1。它给了我以下信息：T(n)=2T(n-1)+1

下面是我解决这个问题的尝试

T(n)=2T(n-1)+1
=2(2T(n-2)+1)+1=4T(n-2)+3
=4(2T(n-3)+1)+3=8T(n-3)+7
=8(2T(n-4)+1)+7=16T(n-4)+15
=16(2T(n-5)+1)+15=32T(n-5)+31
=32T(2T(n-6)+1)+31=64T(n-6)+63

如果我做的对，我如何继续获得运行时间？有人能用外行人的术语来解释如何使用替代方法吗？

Answer 1

您已经接近了，但是您可以设置回替换格式，这样就更有意义了：

T(n)
=2^1T(n-1)+(2^1-1)
=2^2T(n-2)+(2^2-1)
=2^3T(n-3)+(2^3-1)
=2^4T(n-4)+(2^4-1)
=2^5T(n-5)+(2^5-1)
=2^6T(n-6)+(2^6-1)
...

当n接近0时，您可以在这里看到一个模式。它变成了类似于2^n + 2^n - 1的东西，在大O表示法中变成了O(2^n)。

我的一些洞察力可能会帮助您处理其他的递归关系:重复发生n次数，每次迭代乘以2。听起来有点像2^n！