简化递归关系c(n)= c(n/2)+ n ^ 2 [英] Simplifying Recurrence Relation c(n) = c(n/2) + n^2

问题描述

对于简化这种递归关系，我真的感到困惑:c(n)= c(n/2)+ n ^ 2.

I'm really confused on simplifying this recurrence relation: c(n) = c(n/2) + n^2.

所以我首先得到:

c(n/2)= c(n/4)+ n ^ 2 所以 c(n)= c(n/4)+ n ^ 2 + n ^ 2 c(n)= c(n/4)+ 2n ^ 2

c(n/2) = c(n/4) + n^2 so c(n) = c(n/4) + n^2 + n^2 c(n) = c(n/4) + 2n^2

c(n/4)= c(n/8)+ n ^ 2 所以 c(n)= c(n/8)+ 3n ^ 2

c(n/4) = c(n/8) + n^2 so c(n) = c(n/8) + 3n^2

我确实注意到了一种模式:

I do sort of notice a pattern though:

2升至"n ^ 2"前面的任何系数的幂，得出n结束的分母.

2 raised to the power of whatever coefficient is in front of "n^2" gives the denominator of what n is over.

我不确定这是否有帮助.

I'm not sure if that would help.

我只是不明白如何简化这种递归关系，然后找到它的theta表示法.

I just don't understand how I would simplify this recurrence relation and then find the theta notation of it.

实际上，我只是再次进行了计算，得到了c(n)= c(n/n)+ n ^ 2 * lgn.

Actually I just worked it out again and I got c(n) = c(n/n) + n^2*lgn.

我认为这是正确的，但我不确定.另外，我将如何找到其theta表示法?仅仅是theta(n ^ 2lgn)吗?

I think that is correct, but I'm not sure. Also, how would I find the theta notation of that? Is it just theta(n^2lgn)?

推荐答案

让我们回答有关形式重复的更通用的问题: r(n) = r(d(n)) + f(n).功能有一些限制，需要进一步讨论，例如如果x是d的固定点，则f(x)应该为0，否则没有任何解决方案.在您的特定情况下，可以满足此条件.

Let's answer a more generic question for recurrences of the form: r(n) = r(d(n)) + f(n). There are some restrictions for the functions, that need further discussion, e.g. if x is a fix point of d, then f(x) should be 0, otherwise there isn't any solution. In your specific case this condition is satisfied.

重新排列方程式，我们得到r(n) - r(d(n)) = f(n)，并且我们得出直觉，r(n)和r(d(n))都是一些项的总和，但是r(n)比r(d(n))多一个项，这就是为什么f(n)作为区别.另一方面，r(n)和r(d(n))必须具有相同的形式"，因此前面提到的总和中的项数必须是无限的.

Rearranging the equation we get that r(n) - r(d(n)) = f(n), and we get the intuition that r(n) and r(d(n)) are both a sum of some terms, but r(n) has one more term than r(d(n)), that's why the f(n) as the difference. On the other hand, r(n) and r(d(n)) have to have the same 'form', so the number of terms in the previously mentioned sum has to be infinite.

因此，我们正在寻找一种伸缩式总和，其中r(d(n))的术语会抵消r(n)的所有术语，除了一个术语:

Thus we are looking for a telescopic sum, in which the terms for r(d(n)) cancel out all but one terms for r(n):

  r(n)    = f(n) + a_0(n) + a_1(n) + ...
- r(d(n)) =      - a_0(n) - a_1(n) - ...

后面的意思是

  r(d(n)) =        a_0(n) + a_1(n) + ...

只需将d(n)替换为n的等式，就可以得到:

And just by substituting d(n) into the place of n into the equation for r(n), we get:

  r(d(n)) = f(d(n)) + a_0(d(n)) + a_1(d(n)) + ...

因此，通过选择a_0(n) = f(d(n))，a_1(n) = a_0(d(n)) = f(d(d(n)))等:a_k(n) = f(d(d(...d(n)...)))(彼此之间分别包含k+1个d)，我们将获得正确的解决方案.

So by choosing a_0(n) = f(d(n)), a_1(n) = a_0(d(n)) = f(d(d(n))), and so on: a_k(n) = f(d(d(...d(n)...))) (with k+1 pieces of d in each other), we get a correct solution.

因此，通常，解决方案的形式为r(n) = sum{i=0..infinity}(f(d[i](n)))，其中d[i](n)表示函数d(d(...d(n)...))，其中i的迭代次数为i.

Thus in general, the solution is of the form r(n) = sum{i=0..infinity}(f(d[i](n))), where d[i](n) denotes the function d(d(...d(n)...)) with i number of iterations of the d function.

对于您的情况，为d(n)=n/2和f(n)=n^2，因此您可以通过使用几何级数的恒等式获得封闭形式的解决方案.最终结果是r(n)=4/3*n^2.

For your case, d(n)=n/2 and f(n)=n^2, hence you can get the solution in closed form by using identities for geometric series. The final result is r(n)=4/3*n^2.

这篇关于简化递归关系c(n)= c(n/2)+ n ^ 2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！