Relazione di ricorrenza: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Annullata la modifica 115519894 di 2.39.168.71 (discussione) testo mal scritto e fuori contesto
Etichetta: Annulla
Riga 79:
 
:<math>F_n = {\Phi^n \over \sqrt{5}} - {(1-\Phi)^n \over \sqrt{5}}</math>
:Tra le relazioni di ricorrenza linari non omogenee consideriamo il programma in pseudocodice C seguente: '''int A(int n)''' '''{''' '''if (n==0) return 1;'''
: '''return n+A(n-1);''' '''}''' Il calcolo del tempo asintotico per il programma che calcola A dando enne dall'utente si puo' fare col metodo detto '''della sostituzione''' che considera costanti arbitrarie generalmente positive '''c''' e '''d''', sia '''T(n)''' il tempo in funzione dell’input enne allora l’equazione definita per ricorrenza e’: '''T(n)=T(n-1) + a*n''' '''T(1)= d''' Per analogia con la somma dei primi interi ci aspettiamo un tempo quadratico '''T(n)''' dell’ordine di '''n^2''' e cosi’ in prima istanza proviamo una soluzione di forma '''c*n^2 + x(n)''' e sostituendo troviamo '''0=-2cn +c +a*n''' purche’ '''x(n)=x(n-1)''' . Abbiamo cioe’ sostiuito l’ordine piu’ grande che ci aspettiamo, per qualche motivo, nel nostro problema in modo che questo si cancelli. Procediamo adesso osservando che se '''c=a''' e la seconda equazione puo’ essere risolta solo da una costante ! Date queste osservazioni andiamo ad applicare '''il metodo''' che consiste nella plausibilità’ di avere '''f(2)(n) <= T(n)<=f(1)(n)''' ove '''f(1) ed f(2)''' sono nel nostro caso due parabole rivolte vero l’alto cioe’ due funzioni appunto quadratiche che per quanto detto sopra ,ci aspettiamo di trovare in forma ['''c(1)n^2+l(1)]''' ed ['''c(2)n^2+l(2)] senza termini lineari che complicherebbero il conto.''' Se adesso '''c(1)(n-1)^2+l(1)+an <= c(1)n^2+l(1)''' e cioe’ se semplicemente '''(a-2c(1))*n+ c(1) <=0 allora “ T(n)<=f(1)(n) per enne abbastanza grande” ed inoltre “T(n)=T(n-1) + a*n” non''' sono condizioni in contrasto tra loro '''.''' Ovviamente dato '''a>0''' e’ sempre possibile scegliere '''c(1)''' cosi’ grande rispetto ad esso in modo che da un certo enne in poi '''(a-2c(1))*n+ c(1) e’ una retta che sta’ sotto l’asse x.''' Non resta che dimostrare che la condizione iniziale '''non''' e’ in contrasto con la nostra sostituzione di una funzione incognita con una funzione a noi nota: '''d <=''' '''c(1)+l(1) sara’ sempre soddisfatta se l’ultima costante l(1) e’ abbastanza grande.''' In modo del tutto analogo si trova una plausibile parabola inferiore aspettandoci cosi’ un tempo quadratico ripetto al valore di enne che andremo ad inserire dalla tastiera. In questo caso per niente particolare, l’altro metodo detto '''dell’iterazione''' fornisce una soluzione che e’ del tutto simile alla somma dei primi numeri interi : '''T(n)=T(n-1) + a*n= T(n-2) + a*n+ a(n-1)= T(n-3) + a*n+ a(n-1)+a(n-2) =...=T(1)+ a*S(n)''' ma '''S(n)''' altro non e’ che la somma dei primi numeri interi che vadano decrescendo pero’ da enne fino a zero , gia’ calcolata da Cauchy che diede origine al calcolo differnziale in '''n*(n+1)/2 .''' '''Adesso pero’ otteniamo l’assurdo “ Se n=1 ed (a) e’ diveso da zero T(1) = T(1)+ a “ .''' '''Dobbiano cioe’ per forza in alcuni casi usare il metodo della sostituzione od accontentarci di sapere quale sia l’ordine massimo del tempo asintotico.'''
 
==Bibliografia==