递归和大O [英] Recursion and Big O
问题描述
我一直在研究涉及递归和big-O表示法的最新计算机科学作业.我相信我理解得很好(虽然肯定不是很完美！)，但是尤其有一个问题给了我最多的问题.奇怪的是，从外观上看，它看起来是作业中最简单的一个.
I've been working through a recent Computer Science homework involving recursion and big-O notation. I believe I understand this pretty well (certainly not perfectly, though!) But there is one question in particular that is giving me the most problems. The odd thing is that by looking it, it looks to be the most simple one on the homework.
使用big-Oh表示法为以后的复发提供最佳的生长率吗?
Provide the best rate of growth using the big-Oh notation for the solution to the following recurrence?
T(1)= 2
T(n)= 2T(n-1)+1对于n> 1
T(n) = 2T(n - 1) + 1 for n>1
有以下选择:
- O(n log n)
- O(n ^ 2)
- O(2 ^ n)
- O(n ^ n)
我知道大O可以作为上限，用来描述该程序或进程将要进行的最多计算量或最长运行时间.我觉得这个特定的递归应该是O(n)，因为对于n的每个值，递归最多只发生一次.由于n不可用，因此它比O(nlogn)更好，或者更糟糕，是其他三个选项.
I understand that big O works as an upper bound, to describe the most amount of calculations, or the highest running time, that program or process will take. I feel like this particular recursion should be O(n), since, at most, the recursion only occurs once for each value of n. Since n isn't available, it's either better than that, O(nlogn), or worse, being the other three options.
所以，我的问题是:为什么不是O(n)?
So, my question is: Why isn't this O(n)?
推荐答案
有两种解决递归的方法:替换，递归树和主定理.大师定理在这种情况下不起作用，因为它不适合大师定理形式.
There's a couple of different ways to solve recurrences: substitution, recurrence tree and master theorem. Master theorem won't work in the case, because it doesn't fit the master theorem form.
您可以使用其他两种方法，但是解决此问题的最简单方法是迭代解决.
You could use the other two methods, but the easiest way for this problem is to solve it iteratively.
T(n)= 2T(n-1)+ 1
T(n)= 4T(n-2)+ 2 +1
T(n)= 8T(n-3)+ 4 + 2 + 1
T(n)= ...
T(n) = 2T(n-1) + 1
T(n) = 4T(n-2) + 2 + 1
T(n) = 8T(n-3) + 4 + 2 + 1
T(n) = ...
看到图案了吗?
T(n)= 2 n-1 ⋅T(1)+ 2 n-2 + 2 n-3 +. .. + 1
T(n)= 2 n-1 ⋅2+ 2 n-2 + 2 n-3 + ... + 1
T(n)= 2 n + 2 n-2 + 2 n-3 + ... + 1
T(n) = 2n-1⋅T(1) + 2n-2 + 2n-3 + ... + 1
T(n) = 2n-1⋅2 + 2n-2 + 2n-3 + ... + 1
T(n) = 2n + 2n-2 + 2n-3 + ... + 1
因此，最严格的界限是Θ(2 n ).
Therefore, the tightest bound is Θ(2n).
这篇关于递归和大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
