让我们使用递归关系来解决这个问题!第一个函数的运行时可以递归地描述为
T(0) = 1
T(n + 1) = 2T(n) + 1
也就是说,基本情况需要一个时间单位才能完成,否则我们会对问题的较小实例进行两次递归调用,并进行一些设置和清理工作。展开这个递归中的一些项,我们得到
- T(0) = 1
- T(1) = 2T(0) + 1 = 2 + 1 = 3
- T(2) = 2T(1) + 1 = 2 × 3 + 1 = 7
- T(3) = 2T(2) + 1 = 2 × 7 + 1 = 15
This series 1, 3, 7, 15, ... might look familiar, since it's 21 - 1, 22 - 1, 23 - 1, etc. More generally, we can prove that
T(n) = 2n+1 - 1
We can do this by induction. As our base case, T(0) = 1 = 21 - 1, so the claim holds for n = 0. Now assume that for some n that T(n) = 2n+1 - 1. Then we have that
T(n + 1) = 2T(n) + 1 = 2(2n+1 - 1) + 1 = 2n+2 - 2 + 1 = 2n+2 - 1
And we're done! Since this recurrence works out to 2n+1 - 1 = 2(2n) - 1, we have that the runtime is Θ(2n).
第二个函数的运行时可以递归地描述为
T(0) = 1
T(n + 1) = T(n) + 1
展开一些术语:
- T(0) = 1
- T(1) = T(0) + 1 = 1 + 1 = 2
- T(2) = T(1) + 1 = 2 + 1 = 3
- T(3) = T(2) + 1 = 3 + 1 = 4
这给出了 1, 2, 3, 4, ...,所以更一般地说,我们可能会猜测
T(n) = n + 1
我们可以再次归纳证明这一点。作为基本情况,如果 n = 0,则 T(0) = 1 = 0 + 1。对于归纳步骤,假设对于某些 n,T(n) = n + 1。然后
T(n + 1) = T(n) + 1 = n + 1 + 1 = n + 2
我们就完成了!由于运行时间为 n + 1,因此运行时间为 θ(n)。
希望这可以帮助!