Méthode de substitution pour résoudre les récurrences

Question

Tout d'abord désolé de poser une question aussi simple.

Mais j'ai des difficultés à comprendre la méthode de substitution pour résoudre les récurrences. Je suis Introduction à Algo.s -CLRS. Comme je ne suis pas capable de trouver assez d'exemples et l'ambiguïté est la principale préoccupation.Surtout l'étape d'induction.Dans les manuels, nous devons prouver f (n) implique f (n + 1) mais dans CLRS cette étape est manquante ou peut être Je ne reçois pas l'exemple. S'il vous plaît expliquer étape par étape comment prouver que O (n^2) est la solution pour la fonction de récurrence T (n) = T (n-1) + n

Ses étapes générales de la méthode de substitution que je veux comprendre . Si vous pouviez faire la lumière sur une forte induction mathématique et fournir des liens vers du matériel sur la méthode de substitution, cela vous sera également utile.

Answer 1

Dans le procédé de substitution, il suffit de remplacer toute occurrence de T(k) par T(k-1) + k, et de le faire de manière itérative.

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 

De sum of arithmetic progression, vous pouvez obtenir que T (n) est en O(n^2). Notez que la méthode de substitution est généralement utilisée pour avoir une idée de la complexité, pour le prouver formellement - vous aurez probablement besoin d'un outil différent - comme mathematical induction.

La preuve formelle sera quelque chose comme ça:

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)