[Java] Complessità asintotica
Salve a tutti, potreste aiutarmi con questo esercizio?
"Assumendo che l sia una lista con n elementi, indicare qual è la complessità asintotica di caso peggiore del seguente metodo in funzione del valore n. Giustificare la risposta.
public static int esercizio(LinkedList l){
int s=0;
int i=1;
while(i
s+=l.get(j);
i*=2;
}
return s;
}
"
A me viene al massimo lineare(O(n)), è corretto?
"Assumendo che l sia una lista con n elementi, indicare qual è la complessità asintotica di caso peggiore del seguente metodo in funzione del valore n. Giustificare la risposta.
public static int esercizio(LinkedList l){
int s=0;
int i=1;
while(i
s+=l.get(j);
i*=2;
}
return s;
}
"
A me viene al massimo lineare(O(n)), è corretto?
Risposte
Per scrivere del codice esiste il tag [ code ] (senza gli spazi intorno alla parola). Ti consiglio di inserire il codice in questo modo per mantenere la formattazione del codice. Sinceramente lo trovo un pessimo esercizio in quando la maggior parte della complessità è nascosta dalle chiamate ai metodi pubblici della lista. Ci sono inoltre alcune possibili ottimizzazioni che potrebbe fare internamente la classe per velocizzare i propri metodi (e diminuire la complessità algoritmica in casi come il tuo). Il metodo size() per esempio potrebbe richiedere l'iterazione su tutta la struttura per contare il numero dei nodi oppure semplicemente restituire un campo privato contenente la dimensione (aggiornata ad ogni nuovo inserimento e cancellazione di nodi). La funzione get(int i) potrebbe richiedere l'iterazione di tutti i nodi a partire dall'inizio (o la fine) oppure mantenere un nodo corrente e usarlo nei casi in cui si acceda sequenzialmente a tutti gli elementi come stai facendo nel tuo codice. Immagino che il tuo professore abbia dato per scontato che size() abbia complessità O(1) e che get(j) abbia complessità O(n).
Procedo nel modo seguente per calcolare la complessità (nota che è da un po' che non faccio queste cose..). Ad ogni iterazione del ciclo esterno i viene moltiplicato per due. Siccome parte da 1, assume il valore di tutte le potenze di 2 inferiori a n-1 (n la dimensione della lista). Il ciclo esterno viene quindi eseguito circa [tex]\lfloor log_2(n-1) \rfloor[/tex] volte. Il contatore j assume invece i valori i-1, i e i+1. Il ciclo viene eseguito 3 volte e il get interno itera su i-1, i e i+1 elementi rispettivamente. Il numero di iterazioni complessive sulla lista sono quindi:
[tex]\sum_{k=0}^{\left\lfloor log_2(n-1) \right\rfloor} 3 \, 2^{k} = 3 \, (2^{\left\lfloor log_2(n-1) \right\rfloor + 1} - 1)[/tex]
La complessità asintotica dovrebbe essere quindi lineare come avevi calcolato. Ovviamente a patto che siano soddisfatte le supposizione fatte sull'implementazione dei metodi della lista.
Procedo nel modo seguente per calcolare la complessità (nota che è da un po' che non faccio queste cose..). Ad ogni iterazione del ciclo esterno i viene moltiplicato per due. Siccome parte da 1, assume il valore di tutte le potenze di 2 inferiori a n-1 (n la dimensione della lista). Il ciclo esterno viene quindi eseguito circa [tex]\lfloor log_2(n-1) \rfloor[/tex] volte. Il contatore j assume invece i valori i-1, i e i+1. Il ciclo viene eseguito 3 volte e il get interno itera su i-1, i e i+1 elementi rispettivamente. Il numero di iterazioni complessive sulla lista sono quindi:
[tex]\sum_{k=0}^{\left\lfloor log_2(n-1) \right\rfloor} 3 \, 2^{k} = 3 \, (2^{\left\lfloor log_2(n-1) \right\rfloor + 1} - 1)[/tex]
La complessità asintotica dovrebbe essere quindi lineare come avevi calcolato. Ovviamente a patto che siano soddisfatte le supposizione fatte sull'implementazione dei metodi della lista.
Grazie per la risposta, mi scuso se ho postato male il codice ma era la prima volta che scrivevo qui . Sto frequentando un corso di "Fondamenti di Informatica" quindi molti dei problemi che hai evidenziato non so nemmeno cosa riguardino,essendo un corso molto basilare.Ti ringrazio per l'aiuto ma non ho ben capito i conti che hai proposto.L'operazione del ciclo for viene eseguita 3 volte per ogni i, però non capisco come calcolare gli i.
Ho un problema simile anche con un altro esercizio, lo posso postare qui? Help!!
Si.. 
Utilizzando la notazione asintotica, esprimere la complessità computazionale del caso peggiore in funzione della dimensione dell’input del seguente codice, in cui metodo2(int[] b) è un metodo la cui complessità asintotica del caso peggiore è O(log n), essendo n la dimensione dell’array b. Nell’analisi di complessità si assuma che la matrice passata come parametro sia quadrata.
Potete aiutarmi?
public static void metodo1(int[][]a){
int n=a.length;
for(int i=1; i<n-1; i++)
for(int k=i-1;k<=i+1;k++)
metodo2(a[k]);Potete aiutarmi?
Ma te sai dire qualcosa a riguardo di sto esercizio?
Si, il corpo del secondo ciclo for viene eseguito 3 volte per qualunque valore di i, l'operazione dominante dovrebbe essere il corpo di questo ciclo for che ha complessità log(n). Come nell'esercizio precedente, ho problemi ad impostare un calcolo che mi porti a determinare la complessità.
Ma quante volte viene eseguito il ciclo esterno? Mi sembra in questo caso abbastanza immediato il calcolo della complessità. Secondo me dovresti riguardarti meglio la teoria perché non sembri aver compreso bene i concetti.
il ciclio esterno viene eseguito n-2 volte. La teoria l'ho compresa credo, mi manca propio la pratica, anche nell'esercizio precedente ho capito tutto ma non capisco come hai impostato la sommatoria.
Vediamo se dimenticandoci del codice per un attimo, tutto diventa un po' più chiaro. Prova a risolvere il seguente problema:
Piero è un nuotatore professionista e si allena in piscina 5 giorni alla settimana. Supponendo che ad ogni allenamento faccia 100 vasche, quante vasche farà in M settimane? Quanto tempo starà in piscina supponendo che faccia ogni vasca in 25 secondi?
Il calcolo della complessità del tuo problema non è molto diverso dalla risoluzione di questo semplice problema.
Piero è un nuotatore professionista e si allena in piscina 5 giorni alla settimana. Supponendo che ad ogni allenamento faccia 100 vasche, quante vasche farà in M settimane? Quanto tempo starà in piscina supponendo che faccia ogni vasca in 25 secondi?
Il calcolo della complessità del tuo problema non è molto diverso dalla risoluzione di questo semplice problema.
Ok 
Allora le risposte alla tua domanda sono 500M vasche e 12500M secondi.
Forse non ho espresso bene il mio problema. Quando arrivo al momento di impostare una sommatoria come hai fatto te o come vedo sul libro mi perdo e non giungo mai a conclusione.
Per l'ultimo problema che ho postato ho ipotizzato questa soluzione
$ sum_(k = 1)^(k = n-1)3*log(k) $
Allora le risposte alla tua domanda sono 500M vasche e 12500M secondi.
Forse non ho espresso bene il mio problema. Quando arrivo al momento di impostare una sommatoria come hai fatto te o come vedo sul libro mi perdo e non giungo mai a conclusione.
Per l'ultimo problema che ho postato ho ipotizzato questa soluzione
$ sum_(k = 1)^(k = n-1)3*log(k) $
Aiuto, è abbastanza urgente.
Il codice che hai scritto è formato da 2 cicli uno interno all'altro. Detto questo, conta quante volte viene ripetuto il metodo2 al variare del parametro n.
E' propio quello che non riesco a fare. Corrego il risultato che avevo ipotizzato prima con questo
$ sum_(k = 1)^(k = n-2)3*log(n) $
dunque la complessità è al massimo O(n*log(n)). Qualcuno gentilmente conferma o corregge?
$ sum_(k = 1)^(k = n-2)3*log(n) $
dunque la complessità è al massimo O(n*log(n)). Qualcuno gentilmente conferma o corregge?
Procedo nel modo seguente per calcolare la complessità (nota che è da un po' che non faccio queste cose..). Ad ogni iterazione del ciclo esterno i viene moltiplicato per due. Siccome parte da 1, assume il valore di tutte le potenze di 2 inferiori a n-1 (n la dimensione della lista). Il ciclo esterno viene quindi eseguito circa \lfloor log_2(n-1) \rfloor volte. Il contatore j assume invece i valori i-1, i e i+1. Il ciclo viene eseguito 3 volte e il get interno itera su i-1, i e i+1 elementi rispettivamente. Il numero di iterazioni complessive sulla lista sono quindi:
\sum_{k=0}^{\left\lfloor log_2(n-1) \right\rfloor} 3 \, 2^{k} = 3 \, (2^{\left\lfloor log_2(n-1) \right\rfloor + 1} - 1)
La complessità asintotica dovrebbe essere quindi lineare come avevi calcolato. Ovviamente a patto che siano soddisfatte le supposizione fatte sull'implementazione dei metodi della lista.
Riguardando il tuo svolgimento mi è venuto un dubbio. Non capisco perchè hai messo 2^k. Sapendo che il ciclo esterno viene eseguito log2(n-1) volte, e il ciclo for per ogni i viene eseguito 3 volte, la complessità non sarebbe O(log(n))?Cioè nella tua formula avrei eliminato appunto il 2^k, è corretto?
No, perché il get all'interno del ciclo interno itera su j elementi. j prende i valori {i-1, i, i+1}, mentre i è uguale a 2^k. Per cui alla fine ottieni (2^k - 1) + 2^k + (2^k + 1) = 3*2^k.
Grazie per la risposta, sei stato chiarissimo. Ho ipotizzato nei post precedenti una soluzione per il secondo dubbio che avevo sull'altro esercizio, puoi controllare se è giusto o meno per favore?
Qualcuno risponde? Help!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo