復發關係：T（n）= T（n - 1）+ n - 1

我想了解如何解決復發關係。我理解到我們必須簡化的地步。復發關係：T（n）= T（n - 1）+ n - 1

T(N) = T(N-1) + N-1    Initial condition: T(1)=O(1)=1 
T(N) = T(N-1) + N-1 
T(N-1) = T(N-2) + N-2 
T(N-2) = T(N-3) + N-3 
…… 
T(2) = T(1) + 1 


**Summing up right and left sides** 

T(N) + T(N-1) + T(N-2) + T(N-3) + …. T(3) + T(2) = 

= T(N-1) + T(N-2) + T(N-3) + …. T(3) + T(2) + T(1) + 

(N-1) + (N-2) + (N-3) + …. +3 + 2 + 1 


** Canceling like terms and simplifying ** 

T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2 

T(N) = 1 + N*(N - 1)/2

我真的不明白最後一部分。我明白取消類似的術語，但不知道如何下簡化工作：

T(N) = T(1) + (N-1) + (N-2) + (N-3) + …. +3 + 2 + 1 
T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2

如何在第二行從第一個衍生？對我沒有任何意義。

如果有人能幫助我理解這一點，那將是一個很大的幫助。謝謝=）

來源

2012-06-02 Harry Tiron

的可能的複製[如何解決：T（N）= T（N - 1）+ n]（http://stackoverflow.com/questions/2752977/how-to-solve-tn-tn-1-n） –

在你的第二個到最後一行：

S = (N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1

你可以說：

2S = S + S 
    = (N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1 
     1 + 2 + 3 + ... + (N-3) + (N-2) + (N-1) 
    = N + N + N + ... + N + N + N 
     |__________________ N-1 times ________________|

你從N - 1計數到1，所以有N - 1條款中序列。但整個序列只是N這樣你就可以說：

2S = N * (N - 1) 
S = (N * (N - 1))/2

所以在您的最後一個大塊：

T(N) = T(1) + (N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1 
    = T(1) + (N * (N - 1))/2

來源

2012-06-02 03:41:21 Blender

你好，謝謝你的回答。 '2S = S + S'從哪裏來？ –

'2S = S + S'？ '2 = 1 + 1'。這只是一個真實的陳述。證明事物並不像閱讀證明一樣直觀，所以這就是你必須查看和接受的例子之一。這是一種簡化事物的技巧。 – Blender

T(N) = T(1) + (N-1) + (N-2) + (N-3) + …. +3 + 2 + 1 
    = T(1) + (N-1) + (N-2) + (N-3) + ..... + (N-(N-3)) + (N-(N-2)) + (N-(N-1)) 
    = T(1) + [N+N+N+..... n-1 times] - [1+2+3+......+(N-3)+(N-2)+(N-1)] 
    = T(1) + N*(N-1) - (N*(N-1))/2 
    = T(1) + N*(N-1)/2

來源

2012-06-02 03:50:55 Eight

你好，謝謝你的回答。我有種得到它。不明白爲什麼我們除以2？：S –

@HarryTiron除以2實際上是n *（n + 1）/ 2的一部分，它是n個自然數之和，這裏我們必須找到（n-1）個自然數之和，即1 + 2 + 3 + ... +（N-1）。所以和是（n-1）*（n-1 + 1）/ 2。看到這個維基百科頁面http://en.wikipedia.org/wiki/Sum_of_natural_numbers – Eight

復發關係：T（n）= T（n - 1）+ n - 1

回答

相關問題