Metodo di sostituzione per la risoluzione di recidive

Question

Prima di tutto mi dispiace per aver posto una domanda così fondamentale.

Ma ho difficoltà a comprendere il metodo di sostituzione per risolvere le ricorrenze. Sto seguendo Introduzione a Algo.s -CLRS. Poiché non sono in grado di trovare esempi sufficienti e l'ambiguità è la preoccupazione principale. Soprattutto la fase di induzione. Nei libri di testo dobbiamo dimostrare che f (n) implica f (n + 1) ma in CLRS questo passo è mancante o potrebbe essere Non sto ottenendo l'esempio. Spiegare passo dopo passo come provare che O (n^2) è la soluzione per la funzione di ricorrenza T (n) = T (n-1) + n

I passaggi generali del metodo di sostituzione che voglio capire . Se potessi fare un po 'di luce su una forte induzione matematica e fornire collegamenti al materiale sul metodo di sostituzione, sarà anche utile.

Answer 1

In sostituzione, è sufficiente sostituire qualsiasi occorrenza di T(k) entro il T(k-1) + k e farlo in modo iterativo.

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

Da sum of arithmetic progression, è possibile ottenere che T (n) è in O(n^2).

Si noti che il metodo di sostituzione viene in genere utilizzato per ottenere un'intuizione su quale sia la complessità, per dimostrarlo formalmente - sarà probabilmente necessario uno strumento diverso, ad esempio mathematical induction.

La prova convenzionale andrà qualcosa di simile:

Claim: T(n) <= n^2 
Base: T(1) = 1 <= 1^2 
Hypothesis: the claim is true for each `k < n` for some `n`. 
T(n) = T(n-1) + n <= (hypothesis) (n-1)^2 + n = n^2-2n + 1 < n^2 (for n > 1)