Ricorrenze

da **gattomatto** » 10/10/2004, 09:32

<blockquote id="quote">quote:<hr height="1" noshade id="quote">Originally posted by Luca77

Scusate, ma continuo a non capire: se T e' una successione, e n=5, che senso ha calcolare T(5/4)?
<hr height="1" noshade id="quote"></blockquote id="quote">

provo ad avanzare una ipotesi in attesa di conferma o di smentita da parte degli esperti.

se "an" è una successione con "n" appartenente ad "N", nulla ci vieta di definire la successione "bn" che si ottiene sostituendo al posto di "n" una qualunque funzione "f(n)".

Un esempio potrebbe essere il seguente:

an=x^n/n! (con x appartenente ad R)

f(n)=SQRT(n)=n^(1/2)

bn=x^f(n)/GAMMA(f(n)+1)

dove con GAMMA(x) ho indicato la nota funzione analitica interpolatrice del fattoriale.

In tal caso se T(n) è la successione "an" allora T(f(n)) sarebbe la successione "bn".

Ho capito bene oppure ho preso una cantonata?

da **Luca77** » 10/10/2004, 09:45

Affinche' T(f(n)) sia ancora una successione e' necessario che f(n) sia naturale per ogni n; n/4 non e' naturale per ogni n.

Luca.

da **gattomatto** » 10/10/2004, 09:55

<blockquote id="quote">quote:<hr height="1" noshade id="quote">Originally posted by Luca77

Affinche' T(f(n)) sia ancora una successione e' necessario che f(n) sia naturale per ogni n; n/4 non e' naturale per ogni n.
<hr height="1" noshade id="quote"></blockquote id="quote">

Si, su questo siamo d'accordo. Tra l'altro io non sono un esperto e forse sto parlando a sproposito. Tuttavia io mi chiedo:

La "bn" che ho definito precedentemente non è ancora una successione? Io credo di si dato che continua ad essere una applicazione tra N e un qualche altro corpo numerico (nel caso in esame sostituisco un numero naturale e la successione mi ritorna un numero reale).

A questo punto, come la vedo io, potrebbe essere solo un problema di definizione. Se "an" e "bn" sono due successioni tali che la seconda deriva dalla prima per la sostituzione di "n" con "f(n)" (se f(n)=n allora bn=an) non potrebbe darsi che si intenda T(n)=an e T(f(n))=bn?

Ripeto che potrei aver frainteso completamente tutta la vicenda. In tal caso mi scuso e taccio.

Ciao

da **Luca77** » 10/10/2004, 10:03

Non capisco, se Rael non spiega meglio il suo problema: per come l'ha formulato nel primo post, T non puo' essere una successione.

Luca.

da **Rael** » 10/10/2004, 12:19

Maverick pare che abbia colto il punto del problema, e anche l'ipotesi di gattomatto, è del tutto plausibile

infatti nulla mi vieta di definire una relazione di ricorrenza come segue :

T(n) = 2*T(sqrt(n)) + Log(n)

Es.

Sia T(n) = 4*T(n/2) + h(n)

pongo n = 2^m tale che T(f(n)) = T(g(m-1))
e definisco una seconda relazione di ricorrenza B(m) = B(g(m)) + ...

nel mio caso :

T(n) = 4*T(2^(m-1)) + h(2^m)
=> B(m) = 4*B(m-1) + h(2^m)

poi procedo a trovare la soluzione, non vedo cosa ci sia di strano negli indici fratti.

da **Luca77** » 10/10/2004, 12:39

Ascolta, non mi pare difficile: se T agisce su numeri naturali, cosa significa T(n/4)?

La tua relazione di ricorrenza la puoi definire, ma la soluzione non e' una successione.

Luca.

da **Maverick** » 10/10/2004, 12:48

aspettate aspettate, c'è stato un fraintendimento generale. il problema postato da rael non è una successione vera e propria, ma il calcolo della complessità di un algoritmo che in generale non ha bisogno di essere "troppo preciso". si può arrotondare all'intero precedente o successivo se fa comodo, e di solito è anche uguale se si sggiungono o tolgono costanti.

rael, non è che la soluzione è sempre O(nlogn)?
le l'array fosse scomposto in 2T(n/2) funzionerebbe, così non sono sicuro ma vale la pena provare...

da **Luca77** » 10/10/2004, 12:56

Ok, se T non e' una successione, allora chiedo scusa per tutti i miei interventi.

Luca.

da **Maverick** » 10/10/2004, 13:03

baboomba come ti è stato detto sul forum non si fanno gare, quando qualcuno ha un problema ognuno cerca di apportare il suo contributo se può e come può. mi sembra che cmq vada lodato l'impegno di tutti a prescindere... e cmq luca77 col quale ce l'hai tanto non è proprio l'ultimo arrivato...

da **karl** » 10/10/2004, 15:28

E se Rael avesse subito precisato che non si trattava di
successioni, facendolo invece credere col suo riferimento
alla successione di Fibonacci?
karl

Ricorrenze

Chi c’è in linea