[ALGORITIMI] Calcolo Numero Iterazioni e Complessità

[relish]

Ciao a tutti, nell'esame di Algoritmi e strutture dati mi viene chiesto di calcolare il numero di iterazioni e la complessità della singola iterazione di ogni comando ripetitivo all'interno di un algoritmo ricorsivo.

Per spiegarmi meglio vi scrivo degli esempi di esercizio e la soluzione data.

PRIMO:

int f(int x) {
if (x <= 0) return 1;
int b = 3 + 2*f(x/2);
cout << b + f(x/2);
return b + b; }

Con soluzione in relazione di ricorrenza:
Rf(0)= d
Rf(n)= c+ 4Rf(n/2)
Rf(n) è O(n^2)

SECONDO:

int g(int x) {
if (x<=0) return 1;
int a = 0;
for (int i=0; i <= x; i++)
a += i;
int b = 2*g(x/2);
cout << a + g(x/2);
return 1 + 2*b; }

Con soluzione:
Rg(n)= 1
Rg(n)= 1 +4 Rg(n/2)
Rg(n) è O(n^2)

TERZO:

int f(int x) {
int a = g(x);
return a + g(a);
}

Con soluzione:
Rf(n)= è O(n^4)

In cui la funzione g è:

int g(int x) {
if (x<=0) return 1;
int a = 0;
for (int i=0; i <= x; i++)
a += i;
int b = 2*g(x/2);
cout << a + g(x/2);
return 1 + 2*b; }

Con soluzione:
Rg(n)= 1
Rg(n)= 1 +4 Rg(n/2)
Rg(n) è O(n^2)

Poi ce ne sono altri, ma non vorrei riempirvi di esercizi..Se qualcuno riuscisse, partendo dagli esercizi, a spiegarmi il procedimento sarebbe fantastico!

Il Testo dell'esercizio è:
Indicare per esteso le relazioni di ricorrenza per il tempo e per il risultato delle funzioni e, per ogni comando ripetitivo, il numero di iterazioni e la complessità della singola iterazione.

[Kaamos]

Se non proponi le tue soluzioni, o almeno le tue idee, nessuno ti risolverà tutti i compiti...

Ci sono svariati metodi per calcolare la complessità di algoritmi ricorsivi, quali conosci? Sostituzione, iterazione, albero della ricorsione, teorema fondamentale delle ricorrenze... se non conosci alcuna di queste tecniche, documentati a riguardo.

[relish]

Non voglio calcolare la complessità della funzione, ma la complessità del RISULTATO, quindi della singola iterazione della funzione, come è scritto nel testo dell'esercizio alla fine del messaggio.
Ed è una cosa che non trovo sul libro e quindi non ho capito cosa fa, cosa usa per calcolarla.
Sembra divide et impera e relazioni di ricorrenza, ma sul risultato, non sulla funzione!!
se la sapevo fare mi arrangiavo da sola

[Kaamos]

Originariamente inviato da relish
Non voglio calcolare la complessità della funzione, ma la complessità del RISULTATO, quindi della singola iterazione della funzione, come è scritto nel testo dell'esercizio alla fine del messaggio.

"complessità del risultato" non significa nulla finché si parla di complessità temporale, cioé trovare quanto tempo ci mette (più o meno) un algoritmo a svolgere il suo compito.

Tu hai scritto:

Originariamente inviato da relish
mi viene chiesto di calcolare il numero di iterazioni e la complessità della singola iterazione di ogni comando ripetitivo all'interno di un algoritmo ricorsivo.

E questo significa esattamente valutare la complessità di un algoritmo ricorsivo, che è dato dalla complessità della singola iterazione moltiplicata per il numero di iterazioni; questo si può fare in diversi modi, come ho scritto nel messaggio precedente.

Non hai chiesto aiuto solo per la complessità della singola iterazione, se poi hai cambiato idea, diccelo.

Originariamente inviato da relish
Ed è una cosa che non trovo sul libro e quindi non ho capito cosa fa, cosa usa per calcolarla.

Che libro utilizzi? In ogni buon libro sull'argomento ci sono capitoli dedicati alla valutazione della complessità degli algoritmi ricorsivi, e c'è anche materiale online disponibile su dispense universitaria ottenibile con Google.

Originariamente inviato da relish
Sembra divide et impera e relazioni di ricorrenza, ma sul risultato, non sulla funzione!!

Dimmi cosa significa "complessità sul risultato e non sulla funzione" perché non capisco di che parli.

Originariamente inviato da relish
se la sapevo fare mi arrangiavo da sola

Non vorrei rubare il ruolo ai moderatori ma il forum non funziona così, prima ci si documenta sulle basi dell'argomento e poi si chiede aiuto sui singoli problemi, e di materiale sull'argomento ce n'è a bizzeffe, sia online che su carta.

[relish]

Non puoi fare l'acido e citare ogni mia frase se non sai rispondere alla domanda, non è mica colpa mia.
In fondo al mio messaggio c'è il testo dell'esercizio, è inutile che tu citi la mia interpretazione, visto che non capivo come farlo (per questo ho postato il messaggio, ma evidentemente non sono l'unica a non aver capito che chiede).
Lei vuole la complessità del risultato della funzione.
Nel primo esempio chiede la complessità di b+b. Come altro lo dovrei scrivere per farlo capire?
Mi è stato fortunatamente spiegato come si fa.
Conosci il metodo divide et impera?sai che ci sono delle variabili da trovare?Sono "a" e "b", come scritte su tutti i libri.

Sai spiegarmi "a", con un esempio pratico sull'esercizio, cosa rappresenta?
Devo sapere solo questo.
"documentati" è inutile dirmelo, visto che ho già scritto che so calcolare la complessità, ma non ho capito una singola cosa che nessuno mi spiega.

Anzi guarda per evitare un'altra risposta che non mi serve a nulla, ti metto la formula del divide et impera che studio io, così non ci si sbaglia:

T(n)= d per n<=0
T(n)= cn^k + aT(n/b) per n>0

[MItaly]

Appurato che il problema è stato risolto e la discussione sta degenerando, il thread termina qui. Invito comunque entrambi ad evitare inutili polemiche di questo genere in futuro.