Pages: [1] 2   Go Down
Print
Author Topic: Equazione di ricorrenza  (Read 2477 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
the doctor 46
Matricola
*
Offline Offline

Posts: 31


« on: 15-11-2010, 18:13:09 »

Salve , qual'è il procedimento di queste due equazioni di ricorrenza ?

T(n)=T(n-1) + 1/n


T(n)=T(n-1) + log n



Grazie.
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 15-11-2010, 19:10:20 »

Mh....le ho appena iniziate, credo che entrambe si possano risolvere con il Telescoping..
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #2 on: 15-12-2010, 10:32:14 »

credo che entrambe si possano risolvere con il Telescoping..
esatto... la prima viene O(log n) l'altra O(n*log n)
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #3 on: 15-12-2010, 10:42:01 »

Come si risolve invece questa equazone?

T(n)=2T(n-1)+2(n-1)
Logged

alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #4 on: 15-12-2010, 10:59:35 »

direi sempre con il telescoping..
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #5 on: 15-12-2010, 11:01:11 »

guardandola bene quel 2 a moltiplicare non mi piace.....mmm aspe' che ci studio un po scusa ma non faccio esercizi da tempo...

si fara' con il telescoping ma prima occorre effettuare qualche sostituzione
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #6 on: 15-12-2010, 11:05:48 »

sostituisci S(n)=T(n)/2 e viene

S(n)=S(n-1) + n -1

questa si risolve con il telescoping e viene n^2 (ignora il -1) quindi T(n)=2*S(n) e resta di ordine n^2

non ne sono sicuro al 100% spererei in una conferma del prof. ma credo che si risolva cosi'
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #7 on: 15-12-2010, 11:13:57 »

purtroppo nell'elenco delle risposte non c'e O(n^2) Sad
Logged

cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #8 on: 15-12-2010, 12:15:18 »

beh quali sono le soluzioni? se c' un O più grande va bene quello!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #9 on: 15-12-2010, 12:32:08 »

non ho capito..
Logged

cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #10 on: 15-12-2010, 12:36:28 »

O diciamo che è il nostro limite superiore. Se sappiamo che la nostra ricorrenza è O(n^2) possiamo banalmente dire che sarà anche O di tutti gli ordini superiori ad n^2. Attenzione parliamo della notazione O non \Theta.
Non sto confermando l'ipotesi del n^2 che mi sembra comunque corretta. Però voglio dire che le 4 risposte non devono ingannarci.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #11 on: 15-12-2010, 12:38:04 »

Usando il metodo di sostituzione si vede che O(n^2) non è una soluzione.
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #12 on: 15-12-2010, 12:39:42 »

pandemia me lo spieghi il ragionamento svolto che fai?
Logged

Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #13 on: 15-12-2010, 12:41:05 »

ho semplicemente fatto due calcoli applicando il metodo di sostituzione con soluzione O(n^2) su un pezzetto di carta e non è accettata. Prova tu stesso, con più calma.
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #14 on: 15-12-2010, 12:43:32 »

ma con che metodo posso trovare la soluzione?
Logged

Pages: [1] 2   Go Up
Print
Jump to: