如何解决：T（N）= T（N - 1）+ N

我有以下的制定：如何解决：T（N）= T（N - 1）+ N

T(n) = T(n - 1) + n = O(n^2)

现在，当我工作了这一点，我发现这个界是非常松散。我做错了什么，或者只是这样吗？

来源

2010-05-02 Tony The Lion

想想这样：
在递归的每个“迭代”中，你都要做O（n）的工作。
每次迭代都有n-1个工作要做，直到n = base case。（我假设基本情况是O（n）工作）
因此，假设基本情况是一个常数独立于n，那么递归就有O（n）次迭代。
如果你有n次迭代的O（n）工作，O（n）* O（n）= O（n^2）。
你的分析是正确的。如果你想了解更多关于解决递归问题的信息，请查看递归树。与其他方法相比，它们非常直观。

来源

2010-05-02 09:57:41 Rubys

我的想法太深入了数学，忘记了我们正在处理递归的事实。也许这就是为什么我不明白这一点。对于上述我得到T（n）<= 2n是否正确？ – 2010-05-02 10:06:55

不太明白你在问什么，上面有很多 – Rubys 2010-05-02 11:05:05

@Tony：不，那是不正确的。对于小n，T（n）可以大于2n。 – 2010-05-02 16:28:55

您还需要一个基本的情况为您的重复关系。

T(1) = c 
T(n) = T(n-1) + n

要解决这个问题，你可以先猜一个解决方案，然后用归纳法证明它是有效的。

T(n) = (n + 1) * n/2 + c - 1

首先是基本情况。当n = 1时，根据需要给出c。

对于其他N：

T(n) 
= (n + 1) * n/2 + c - 1 
= ((n - 1) + 2) * n/2 + c - 1 
= ((n - 1) * n/2) + (2 * n/2) + c - 1 
= (n * (n - 1)/2) + c - 1) + (2 * n/2) 
= T(n - 1) + n

所以解决方案的工作。

为了让猜测首先，请注意您的复发关系产生triangular numbers当C = 1：

T(1) = 1: 

* 

T(2) = 3: 

* 
** 

T(3) = 6: 

* 
** 
*** 

T(4) = 10: 

* 
** 
*** 
**** 

etc..

直观的三角形是大约一半的正方形，并在大O符号的常数可以忽略，所以O（n^2）是预期的结果。

来源

2010-05-02 09:38:59

你能告诉我你是如何得到你的答案中的第三个方程吗？你应用了什么数学技巧？ – 2010-05-02 09:46:07

@Tony：这是一个“猜测”。事实上，这是因为我知道三角形数字的公式 - 我没有真正猜到，我已经知道了。 “猜测”正确的答案并证明它是正确的，而不是从第一原则推导出来往往更容易。这是解决复发关系的标准技术。 – 2010-05-02 09:48:15

@Tony：受过教育的猜测的技术术语是“ansatz”。请参阅：http：//en.wikipedia.org/wiki/Ansatz。有一些关于使用猜测来解决维基百科中重复关系的信息：http：//en.wikipedia.org/wiki/Recurrence_relation。其他可能的解决再现关系的方法也列在那里。 – 2010-05-02 10:01:27

看起来正确，但取决于基本情况T（1）。假设你将执行n个步骤来使T（n）到T（0），并且每次n项在0到n之间的任何一个平均n/2，所以n * n/2 =（n^2）/ 2 = O（n^2）。

来源

2010-05-02 09:40:24 shuttle87

这个解决方案非常简单。你必须展开递归：

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... = 
= T(0) + 1 + 2 + ... + (n-1) + n

在这里你有等差数列和总和1/2*n*(n-1)。从技术上讲，你在这里错过了边界条件，但是对于任何恒定的边界条件，你会发现递归是O(n^2)。

来源

2015-12-13 08:33:53

如何解决：T（N）= T（N - 1）+ N

回答

相关问题