[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.

[apatriarca]

Questo forum supporta l'inserimento di formule usando TeX. Utilizza questa funzionalità in modo da rendere più chiare le tue formule. I codici andrebbero poi formattati un po' meglio per essere resi più leggibili (anche se lo sono già più di altri codici che ho visto).

Non mi è chiaro il significato di Tf e Rf/Rg. Inoltre l'ultima funzione fa uso di una funzione g, ma tale funzione non è stata definita. In ogni caso, qual'è il problema? Trovare l'equazione di ricorrenza per la complessità oppure calcolare la complessità asintotica data l'equazione di ricorrenza? Per questo secondo problema esistono una miriade di discussioni ed esempi in questa sessione del forum. Per l'altra è in realtà spesso sufficiente fare uso di un numero abbastanza limitato di regole (la parte difficile è normalmente l'altra..).

[relish]

Rf e Rg sono i risultati di f e i risultati di g. Come scritti nella soluzione all'esercizio.
Per quanto riguarda la formattazione non la so fare, per questo ho inserito le funzioni in quel modo, comunque essendo solo poche righe si capisce bene cosa fa la funzione.

Come dice il testo dell'esercizio che ho messo in fondo al messaggio, chiede di scrivere le relazioni di ricorrenza per il risultato delle funzioni, e per ogni comando ripetitivo il numero di iterazioni e la loro complessità.
Quindi non la complessità della funzione, che già so calcolare, ma quella dei comandi ripetitivi, di cui non ho trovato nessun messaggio nel forum.
Se c'è e non l'ho visto, mi faresti un favore a linkarmelo, perchè ho cercato veramente ovunque prima di postare questo messaggio.

Per l'ultima funzione non l'avevo visto che chiamava l'altra, avevo modificato e probabilmente ho cambiato esercizio, ora la metto.

[hamming_burst]

"relish":
Quindi non la complessità della funzione, che già so calcolare, ma quella dei comandi ripetitivi, di cui non ho trovato nessun messaggio nel forum.
Se c'è e non l'ho visto, mi faresti un favore a linkarmelo, perchè ho cercato veramente ovunque prima di postare questo messaggio

ok non vuoi calcolare la ricorrenza, ma le varie funzioni libere (costanti), degli esempi di analisi di questo tipo (sono alg iterativi, ma i principi sono validi):
- complessita-computazionale-t70026.html
- algoritmi-t88666.html

esercizi (e le soluzioni) presi dalla sezione dispense.

dopo questo, prova a svolgere gli esercizi che hai proposto nel thread sopra e proporli qui, noi ti aiuteremo dove ti blocchi.

[relish]

Ti ringrazio, ma tutti calcolano la complessità della funzione, non del risultato.
Ho però ricevuto un'altra risposta, senza poi riuscire a contattare più quella persona purtroppo.
Quindi scrivo qua il mio dubbio.
La formula per il metodo divide et impera dice che dopo aver trovato la relazione di ricorrenza del tipo:
T(n)= d
T(n)= bn^k + aT(n/b)

Ho varie soluzioni dipendenti dai 3 valori a, b e k:
"a" è il numero di ricorrenze del programma...significa che è il numero di volte in cui viene richiamata la funzione?nel primo caso per b e per cout?
"b" è il numero di sottoinsiemi in cui viene divisa la soluzione...ad ogni chiamata di funzione?in questo caso viene divisa in 2 chiamandola con n/2?

[apatriarca]

Ma non c'è alcuna differenza tra il risolvere una ricorrenza che rappresenti il tempo di esecuzione, oppure lo spazio utilizzato o che rappresenta il valore della funzione. I metodi sono sempre gli stessi.

[hamming_burst]

"relish":ma tutti calcolano la complessità della funzione, non del risultato.

bho allora non capisco cosa tu chieda.

Se è come dice apatriarca allora rileggiti a cosa servono le complessità.

[relish]

No lo so, però mi sapete spiegare quelle due cose su "a" e "b"?sono le uniche che non ho capito, "a" in particolare, "b" credo di aver capito cos'è..sul libro non c'è scritto, sui post neanche, sugli esercizi idem

[apatriarca]

Ma l'hai scritto tu stesso cosa sono.. $a$ è il numero di volte in cui la funzione viene richiamata sul sottoproblema, mentre $b$ è il numero di "blocchi" in cui viene suddiviso l'input. Non mi è chiaro a quale problema tu stia facendo riferimento però, per cui mi viene difficile dirti i valori di $a$ e $b$ nel tuo caso.

[relish]

"apatriarca":$a$ è il numero di volte in cui la funzione viene richiamata sul sottoproblema,

Oh questo volevo sapere, solo la conferma di "a". Quindi nel primo esempio viene chiamata per calcolare "b" in int b=.... e per la funzione "cout", giusto?Per questo vale 2

[apatriarca]

Non ho capito a cosa ti riferisci, ma immagino che sia così come dici..