Repository destinato alla condivisione di materiale e soluzioni per gli esercizi ed esami assegnati dal Prof. Monti Angelo in preparazione all'esame di Algoritmi 1
9
stars
1
forks
source link
Spiegazione del perché utilizziamo le sommatorie per valutare il costo computazionale #5
Ciao a tutti, il motivo per il quale sto scrivendo questa guida è che ho passato ore a cercare di capire come funzionasse il meccanismo della sommatoria per il calcolo della complessità di un algoritmo, e dopo averlo capito, voglio farti risparmiare le ore che ci potresti mettere a capirlo.
Il problema
Cerchiamo di comprendere il problema alla base. Prendiamo come esempio questo ciclo for:
def func1(n)
count = 0
for i in range(n):
count += i
è facile notare che ogni volta che i aumenta di 1, il nostro count aumenta di 1. Ora proviamo a riscrivere matematicamente la stessa cosa: $\sum\limits_{i=1}^n\text{count}$. Inizia a notare la somiglianza? Facciamo ora un passo avanti e cerchiamo di capire il meccanismo dietro: dietro a un ciclo for o a un ciclo while in cui il passo aumenta (ad esempio i) c'è una sommatoria implicita.
I cicli annidati
Una delle difficoltà maggiori che ho avuto è stata quando dovevo calcolare la complessità dei cicli annidati, perché in alcuni come l'es6 di: #3 non moltiplicavo la complessità del ciclo esterno per quello interno, mentre in altri si.
Quando si presentano davanti a noi uno o più cicli annidati, dobbiamo capire due cose:
L'esecuzione dei vari cicli dipende dalle stesse cose (ad esempio una i che viene incrementata e usata in entrambi i cicli) o no?
Se l'esecuzione dei vari cicli non dipende dalle stesse cose, quante volte eseguo questi cicli?
Prendiamo questo pseudocodice:
🚨giuro che la finisco🚨
Ciao a tutti, il motivo per il quale sto scrivendo questa guida è che ho passato ore a cercare di capire come funzionasse il meccanismo della sommatoria per il calcolo della complessità di un algoritmo, e dopo averlo capito, voglio farti risparmiare le ore che ci potresti mettere a capirlo.
Il problema
Cerchiamo di comprendere il problema alla base. Prendiamo come esempio questo ciclo for:
è facile notare che ogni volta che i aumenta di 1, il nostro count aumenta di 1. Ora proviamo a riscrivere matematicamente la stessa cosa: $\sum\limits_{i=1}^n\text{count}$. Inizia a notare la somiglianza? Facciamo ora un passo avanti e cerchiamo di capire il meccanismo dietro: dietro a un ciclo for o a un ciclo while in cui il passo aumenta (ad esempio i) c'è una sommatoria implicita.
I cicli annidati
Una delle difficoltà maggiori che ho avuto è stata quando dovevo calcolare la complessità dei cicli annidati, perché in alcuni come l'es6 di: #3 non moltiplicavo la complessità del ciclo esterno per quello interno, mentre in altri si. Quando si presentano davanti a noi uno o più cicli annidati, dobbiamo capire due cose: