有人可以帮助解决这种复发关系吗? [英] Can someone help solve this recurrence relation?
问题描述
T(n) = 2T(n/2) + 0(1)
T(n) = T(sqrt(n)) + 0(1)
在第一个中，我对n，logn等使用替代方法；都给了我错误的答案.
递归树:我不知道我是否可以申请，因为根将是一个常数.
有人可以帮忙吗?
让我们看一下第一个.首先，您需要了解T(基本情况).您提到这是一个常数，但是在执行问题时，务必将其写下来很重要.通常，它类似于T(1)=1.我将使用它，但是您可以将其推广为任何东西.
接下来，找出您重复的次数(即递归树的高度). n是您的问题大小，所以我们可以将n除以2多少次?从数学上讲，n/(2^i) = 1时我是什么?找出原因，稍等片刻.
接下来，进行一些替换，直到您开始注意到一个模式.
T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)
好的，模式是我们将T()乘以2束，然后将n除以2束.多少次? i次.
T(n) = (2^i)*T(n/(2^i)) + ...
对于最后的大θ项，我们使用了一个可爱的技巧.在上面有几个替换项的地方看，而忽略T()部分.我们想要θ项的总和.请注意，它们加起来为(1 + 2 + 4 + ... + 2^i) * θ(1).您可以找到1 + 2 + 4 + ... + 2^i的封闭表格吗?我给你那个； (2^i - 1).记住这是一个好习惯，但是这是您想出的方法. /p>
无论如何，总而言之
T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)
如果您较早地解决了i，那么您就会知道i = log_2(n).插上电源，做一些代数运算，然后您就会开始学习
T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1.所以T(n) = n + (n - 1)*θ(1).这是常数的n倍，再加上常数，再加上n.我们删除低阶项和常数，所以它是θ(n).
Prasoon Saurav使用主方法是正确的，但是重要的是要知道递归关系在说什么.要问的问题是，我每个步骤要做多少工作，输入大小为n的步骤数是多少?
T(n) = 2T(n/2) + 0(1)
T(n) = T(sqrt(n)) + 0(1)
In the first one I use substitution method for n, logn, etc; all gave me wrong answers.
Recurrence trees: I don't know if I can apply as the root will be a constant.
Can some one help?
Let's look at the first one. First of all, you need to know T(base case). You mentioned that it's a constant, but when you do the problem it's important that you write it down. Usually it's something like T(1) = 1. I'll use that, but you can generalize to whatever it is.
Next, find out how many times you recur (that is, the height of the recursion tree). n is your problem size, so how many times can we repeatedly divide n by 2? Mathematically speaking, what's i when n/(2^i) = 1? Figure it out, hold onto it for later.
Next, do a few substitutions, until you start to notice a pattern.
T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)
Ok, the pattern is that we multiply T() by 2 a bunch of times, and divide n by 2 a bunch of times. How many times? i times.
T(n) = (2^i)*T(n/(2^i)) + ...
For the big-θ terms at the end, we use a cute trick. Look above where we have a few substitutions, and ignore the T() part. We want the sum of the θ terms. Notice that they add up to (1 + 2 + 4 + ... + 2^i) * θ(1). Can you find a closed form for 1 + 2 + 4 + ... + 2^i? I'll give you that one; it's (2^i - 1). It's a good one to just memorize, but here's how you'd figure it out.
Anyway, all in all we get
T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)
If you solved for i earlier, then you know that i = log_2(n). Plug that in, do some algebra, and you get down to
T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. So T(n) = n + (n - 1)*θ(1). Which is n times a constant, plus a constant, plus n. We drop lower order terms and constants, so it's θ(n).
Prasoon Saurav is right about using the master method, but it's important that you know what the recurrence relation is saying. The things to ask are, how much work do I do at each step, and what is the number of steps for an input of size n?
这篇关于有人可以帮助解决这种复发关系吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
