[Serie] Complessità algoritmo / relazioni di ricorrenza
Ciao!
Il mio libro di testo mi dice che il risultato di
$C_N = C_(N/2) + N$
è $2N$
dove la relazione si riferisce ad un programma ricorsivo che dimezza il suo input ed esamina ogni elemento di esso di volta in volta.
ma come si arriva a questo risultato? Non ricordo più i criteri per la convergenza delle serie e successioni... ho provato a cercarli, ma non trovo i miei appunti di due anni fa...
con un'altra relazione, quella del divide et impera, in cui cioè il programma esegue una scansione lineare prima o dopo aver suddiviso l'input a metà:
$C_N = 2*C_(N/2) + N$
mi dice che il risultato è $NlogN$
ma secondo quale procedimento?
mi potreste schiarire le idee? io proprio non ricordo...
vi ringrazio
Il mio libro di testo mi dice che il risultato di
$C_N = C_(N/2) + N$
è $2N$
dove la relazione si riferisce ad un programma ricorsivo che dimezza il suo input ed esamina ogni elemento di esso di volta in volta.
ma come si arriva a questo risultato? Non ricordo più i criteri per la convergenza delle serie e successioni... ho provato a cercarli, ma non trovo i miei appunti di due anni fa...
con un'altra relazione, quella del divide et impera, in cui cioè il programma esegue una scansione lineare prima o dopo aver suddiviso l'input a metà:
$C_N = 2*C_(N/2) + N$
mi dice che il risultato è $NlogN$
ma secondo quale procedimento?
mi potreste schiarire le idee? io proprio non ricordo...
vi ringrazio
Risposte
Ricordo dall'esame di algoritmi che queste equazioni di risolvono con il teorema fondamentale delle ricorrenze che dice:
siano f(n) funzione, $alpha>=1$,$beta>1$ e $n_0>=0$
allora l'equazione di ricorrenza
$T(n)=O(1)$ se $n<=n_0$
$T(n)=alpha T([n/beta])+f(n)$ altrimenti
ha le seguenti soluzioni per ogni n:
1. $T(n)=O(f(n))$ se esiste una costante $gamma<1$ tale che $alpha f([n/beta])=gamma f(n)$
2. $T(n)=O(f(n)log_(beta)n)$ se $alpha f([n/beta])=f(n)$
3. $T(n)=O(n^(log_(beta)alpha))$ se esiste una costante $gamma'>1$ tale che $alpha f([n/beta])=gamma' f(n)$
Poi ricordo che in certi casi questo teorema non funziona, mi pare quando l'equazione contiene due o più funzioni ma non mi ricordo come si fa in quel caso.
Ps. il tuo libro non dà le soluzioni come andamento asintotico. questo può voler dire o che la mia risposta non centra niente o che usa un metodo più raffinato che però non ti so dire. Non mi sono mai posto il problema di differenziare un algoritmo N da uno 2N.
ciao
siano f(n) funzione, $alpha>=1$,$beta>1$ e $n_0>=0$
allora l'equazione di ricorrenza
$T(n)=O(1)$ se $n<=n_0$
$T(n)=alpha T([n/beta])+f(n)$ altrimenti
ha le seguenti soluzioni per ogni n:
1. $T(n)=O(f(n))$ se esiste una costante $gamma<1$ tale che $alpha f([n/beta])=gamma f(n)$
2. $T(n)=O(f(n)log_(beta)n)$ se $alpha f([n/beta])=f(n)$
3. $T(n)=O(n^(log_(beta)alpha))$ se esiste una costante $gamma'>1$ tale che $alpha f([n/beta])=gamma' f(n)$
Poi ricordo che in certi casi questo teorema non funziona, mi pare quando l'equazione contiene due o più funzioni ma non mi ricordo come si fa in quel caso.
Ps. il tuo libro non dà le soluzioni come andamento asintotico. questo può voler dire o che la mia risposta non centra niente o che usa un metodo più raffinato che però non ti so dire. Non mi sono mai posto il problema di differenziare un algoritmo N da uno 2N.
ciao
sinceramente io nemmeno, perchè per grandi valori di N, non ha senso considerare per forza 2N...
il problema è che il mio libro non fornisce alcuna spiegazione e nessun passaggio matematico... il che mi inquieta perchè non capisco come faccia a dar per scontate queste cose...
il teorema fondamentale l'avevo trovato su wikipedia, ma dato che non fa alcun accenno a questo, il mio libro, pensavo che supponesse di risolverlo per via algebrica...
ma boh... rimango ancora sconcertato
il problema è che il mio libro non fornisce alcuna spiegazione e nessun passaggio matematico... il che mi inquieta perchè non capisco come faccia a dar per scontate queste cose...
il teorema fondamentale l'avevo trovato su wikipedia, ma dato che non fa alcun accenno a questo, il mio libro, pensavo che supponesse di risolverlo per via algebrica...
ma boh... rimango ancora sconcertato
beh nel primo caso (rispetto al teorema di cui ti ho parlato) potresti anche avventurarti nella selva oscura di un procedimento algebrico ma negli altri due (come puoi vedere dalla forma delle soluzioni) temo che non sia possibile.
Anzi sono abbastanza propenso a pensare che il tuo libro abbia utilizzato questo teorema e poi (solo nel primo caso) abbia precisato la costante perchè si vede quasi ad occhio.
Anzi sono abbastanza propenso a pensare che il tuo libro abbia utilizzato questo teorema e poi (solo nel primo caso) abbia precisato la costante perchè si vede quasi ad occhio.
però almeno un riferimento a quella formula potrebbe farlo...
cioè che ci voleva all'autore dire: "il risultato deriva dall'applicazione di quella formula"
per questo, pensavo fosse derivato da argomentazioni prettamente algebriche...
ora vedo un pò...
cioè che ci voleva all'autore dire: "il risultato deriva dall'applicazione di quella formula"
per questo, pensavo fosse derivato da argomentazioni prettamente algebriche...
ora vedo un pò...
beh se ti fai problemi per questo augurati di non avere mai a che fare con un libro di hilbert che ti salta tranquillamente 20 passaggi passando da una formula di 3 righi ad una di 2 centimetri sottolineando quanto sia ovvio quel passaggio
Ricordati che i matematici (soprattutto gli analisti) sono pigri!!!
ehehm...siamo pigri...
Ricordati che i matematici (soprattutto gli analisti) sono pigri!!!
ehehm...siamo pigri...
"Megan00b":
beh se ti fai problemi per questo augurati di non avere mai a che fare con un libro di hilbert che ti salta tranquillamente 20 passaggi passando da una formula di 3 righi ad una di 2 centimetri sottolineando quanto sia ovvio quel passaggio
Ricordati che i matematici (soprattutto gli analisti) sono pigri!!!
ehehm...siamo pigri...
vi capisco benissimo
ma se voi siete pigri nelle formule, noi ingegneri siamo prigri quando si tratta di andare a cercare altrove i passaggi non scritti da voi
abbiamo messo su proprio un bel circolo vizioso
ciao,
io mi sono chiarito un po le idee con questo documento http://www.dsi.unifi.it/~costa/lucidi_f ... totica.pdf
è tutto abbastanza semplice se ho capito bene
ad esempio nel primo esercizio direi che è =n essendo il tempo di divisione e ricombinazione piu grande del tempo destinato alla risoluzione ricorsiva
non capisco perchè il tuo libro indica 2n, visto che sia 2n che n hanno lo stesso ordine di grandezza theta n in questo caso
per quel che riguarda il secondo è giusto perchè i tempi si equivalgono
fammi sapere cosa ne pensi perchè anche io non è che sia un esperto
io mi sono chiarito un po le idee con questo documento http://www.dsi.unifi.it/~costa/lucidi_f ... totica.pdf
è tutto abbastanza semplice se ho capito bene
ad esempio nel primo esercizio direi che è =n essendo il tempo di divisione e ricombinazione piu grande del tempo destinato alla risoluzione ricorsiva
non capisco perchè il tuo libro indica 2n, visto che sia 2n che n hanno lo stesso ordine di grandezza theta n in questo caso
per quel che riguarda il secondo è giusto perchè i tempi si equivalgono
fammi sapere cosa ne pensi perchè anche io non è che sia un esperto
il pdf è di sicuro interessante... e schiarisce un pò le idee...
ottimo
la storia del perchè esca il 2N ancora non è chiara nemmeno a me... non credo sia un errore del libro però...
ottimo
la storia del perchè esca il 2N ancora non è chiara nemmeno a me... non credo sia un errore del libro però...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo