如何解決：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

回答

相關問題