Metoda zastępowania rozwiązywania nawrotów

Question

Po pierwsze przepraszam za zadawanie tak podstawowego pytania.

Ale mam trudności ze zrozumieniem metody zastępowania w rozwiązywaniu nawrotów. Podążam za wprowadzeniem do Algo.s -CLRS. Ponieważ nie jestem w stanie znaleźć wystarczającej ilości przykładów i niejednoznaczności, to jest to szczególnie ważne. W podręcznikach musimy udowodnić, że f (n) oznacza f (n + 1), ale w CLRS ten krok nie istnieje lub może być Nie dostaję tego przykładu. Proszę wyjaśnić krok po kroku, jak dowieść, że O (n^2) jest rozwiązaniem dla funkcji nawrotu T (n) = T (n-1) + n

Oto ogólne kroki metody zastępowania, które chcę zrozumieć . Jeśli mógłbyś rzucić nieco światła na silną indukcję matematyczną i podać linki do materiału na temat metody zastępowania, które będą pomocne również.

Answer 1

W metodzie zastępowania po prostu wymień dowolne wystąpienie T(k) przez T(k-1) + k i wykonaj to w sposób ciągły.

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 

Od sum of arithmetic progression można dostać, że T (n) jest O(n^2).

Należy zauważyć, że metoda podstawiania jest zwykle używana do uzyskania intuicji na temat złożoności, aby ją oficjalnie udowodnić - prawdopodobnie potrzebne będzie inne narzędzie - na przykład mathematical induction.

Formalny dowód pójdzie coś takiego:

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)