Leicht: Lösen Sie T(n) = T(n-1) +n mit der Iterationsmethode.

Question

Kann mir bitte jemand damit helfen?

Verwenden Sie die Iterationsmethode, um es zu lösen. T(n) = T(n-1) +n

Eine Erklärung der Schritte wäre sehr willkommen.

Answer 1

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

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

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

und so weiter können Sie den Wert von T(n-1) und T(n-2) in T(n) einsetzen, um eine allgemeine Vorstellung vom Muster zu bekommen.

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)

Für den Basisschritt:

n - k = 1, also können wir T(1) erhalten

\=> k = n - 1
ersetzen in (1)

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

Was Sie erkennen können, ist von der Ordnung n2 => O(n2).

Answer 2

Erweitern Sie es!

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

und so weiter, bis

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

vorausgesetzt, dass T(1) = 1

Answer 3

Another solution:

T(n) = T(n-1) + n
     = T(n-2) + n-1 + n
     = T(n-3) + n-2 + n-1 + n
     // wir können nun verallgemeinern auf k
     = T(n-k) + n-k+1 + n-k+2 + ... + n-1 + n
     // da n-k = 1 ist, also T(1) = 1
     = 1 + 2 + ... + n    //Hier 
     = n(n-1)/2
     = n^2/2 - n/2
     // wir nehmen den dominanten Term, der n^2*1/2 ist, deshalb 1/2 = big O
     = big O(n^2)

Answer 4

In Pseudocode mit Iteration:

function T(n) {
    int result = 0;

    für (i von 1 bis n) {
       result = result + i;
    }

    return result;
}

Answer 5

Einfache Methode:

T (n) = T (n - 1) + (n )-----------(1)
 //jetzt T(n-1)=t(n)

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

jetzt setze (2) in (1) ein, du erhältst
d.h. T(n)=[T(n-2)+n-1]+(n)
T(n)=T(n-2)+2n-1 //vereinfacht--------------(3)

 jetzt, 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)
  jetzt setze (4) in (2) ein, du erhältst
   d.h. T(n)=[T(n-4)+2n-5]+(2n-1)
  T(n)=T(n-4)+4n-6 //vereinfacht
    ............
 T(n)=T(n-k)+kn-6
  **Basierend auf der allgemeinen Form T(n)=T(n-k)+k, **
  jetzt, nehmen wir an n-k=1 wir wissen T(1)=1
            k=n-1

    T(n)=T(n-(n-1))+(n-1)n-6
    T(n)=T(1)+n^2-n-10
   Gemäß der Komplexität ist 6 konstant

         Also, Letztendlich O(n^2)