algorithm - 簡単: 反復法で T(n)=T(n-1)+n を解く

Question

誰かがこれで私を助けてくれますか?

反復法を使用してそれを解決します。 T(n) = T(n-1) +n

手順の説明をいただければ幸いです。

Answer 1

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

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

T(n-2) = T(n-3) + n-2

など、T（n）のT（n-1）とT（n-2）の値を代入して、パターンの一般的な考え方を得ることができます。

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

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

T(n) = T(n-k) + kn - k(k-1)/2    ...(1)

基本ケースの場合：

n - k = 1 so we can get T(1)

=> k = n-1
（1）の代用

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

あなたが見ることができるのは次数n2 ⁼ > O（n ²）です。

Answer 2

広げて！

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

など、まで

T(n) = 1 + 2 + ... + n = n(n+1)/2   [= O(n^2)]

ただし、T(1) = 1

Answer 3

反復を使用する擬似コードの場合：

function T(n) {
    int result = 0;

    for (i in 1 ... n) {
       result = result + i;
    }

    return result;
}    

Answer 4

簡単な方法:

T (n) = T (n - 1) + (n )-----------(1)
 //now submit T(n-1)=t(n)

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

now submit (2) in (1) you will get
i.e T(n)=[T(n-2)+n-1]+(n)
T(n)=T(n-2)+2n-1 //simplified--------------(3)

 now, T(n-2)=t(n)
T(n-2)=T((n-2)-2)+[2(n-2)-1]
  T(n-2)=T(n-4)+2n-5---------------(4)
  now submit (4) in (2) you will get
   i.e T(n)=[T(n-4)+2n-5]+(2n-1)
  T(n)=T(n-4)+4n-6 //simplified
    ............
 T(n)=T(n-k)+kn-6
  **Based on General form T(n)=T(n-k)+k, **
  now, assume n-k=1 we know T(1)=1
            k=n-1

    T(n)=T(n-(n-1))+(n-1)n-6
    T(n)=T(1)+n^2-n-10
   According to the complexity 6 is constant

         So , Finally O(n^2)