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

2 行目は最初の行からどのように派生しますか? 私には意味がありません。

誰かが私がこれを理解するのを手伝ってくれるなら、大きな助けになるでしょう. ありがとう =)

4

2 に答える 2

1

最後から2番目の行で：

 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-02T03:41:21.467 に答える
0 
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-02T03:50:55.727 に答える