[Algoritmi] Dubbio metodo di sostituzione su ricorrenze

[ZfreS]

Avrei qualche dubbio sul metodo di sostituzione per risolvere le ricorrenze. Si prende come esempio la ricorrenza così definita: $T(n)=2T(floor(n/2))+n$. Da ciò che ho capito il metodo di sostituzione consiste nell'indovinare quale possa essere in questo caso il limite superiore, e dimostrarlo per induzione. Supponiamo che il lim. sup. sia $O(nlogn)$, dunque $T(n)=O(nlogn)$. Bisogna dimostrare, che presi un $c_1>0$ e un $n_0>0$ è vero che: $T(n)<=c_1nlogn$ $AA>=n_0$. Il libro scrive così: $T(n)<=2(cfloor(n/2))log(floor(n/2)+n<=cnlog(n/2)+n=cnlogn-cnlog2+n=cnlogn-cn+n<=cnlogn$ e questo per $c>=1$. Fin qui è tutto chiaro. Poi il testo dice che avendo una funzione simile, si può "riutilizzare" una soluzione già vista per un caso simile chiaramente dimostrandolo. Si prende come caso la ricorrenza: $T(n)= 2T(floor(n/2)+17)+n$. Qui bisogna dimostrare che $T(n)<=cnlogn$. Solo che in questo caso c'è un termine additivo +17. Come bisognrebbe procedere in questo caso. Un'altro dubbio è questo: dove si è usato il metodo di induzione. Nell'esempio prima ho fatto uso di passaggi algebrici.

[apatriarca]

Il ragionamento induttivo non è stato in effetti del tutto specificato nella dimostrazione che ti è stata data. Vuoi dimostrare che
\[ \exists k > 0 \; \exists n_0 \; \forall n > n_0. \; T(n) = 2\,T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + n \leq k\,n \log n \]
Il caso base da trovare sarebbe \(n = n_0 + 1,\) ma raramente si esplicita in questo tipo di dimostrazioni. Quello che si fa di solito è scrivere la relazione che deve rispettare la funzione per un valore generico di \(k,\) risolvere per tale parametro e quindi trovare un \(n_0\) opportuno. In questo caso scriviamo quindi:
\[ T(n) = 2\,T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + n \leq 2\,k \left\lfloor \frac{n}{2} \right\rfloor \log \left\lfloor \frac{n}{2} \right\rfloor + n \leq k\,n \log n + (1 - k)\,n \leq k\,n \log n \quad \forall k > 1 \]
Se prendiamo a questo punto ad esempio \(k = 2\) e \(T(1) = 1\) abbiamo che \(T(2) = 2 + 2 = 4 = 2\,(2 \log 2) \). In un certo senso stiamo usando il metodo induttivo scambiando l'ordine dei passaggi. Supponiamo che il primo passaggio sia verificato, troviamo le condizioni per cui vale il secondo passaggio e mostriamo che esiste un valore base. Di fatto il valore base esiste comunque sempre perché con il secondo passaggio hai dimostrato che la tua relazione di ricorrenza cresce più lentamente della funzione \(n \log n\).