使用替换方法解决递归问题

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，在 Big-O 表示法中，O(2^n).

我的一些见解可能会帮助您处理其他递归关系：递归发生 n 次，每次迭代乘以 2。听起来像 2^n!

使用替换方法解决递归问题

Solving recurrences using substitution method

algorithm

recurrence