[Algoritmi] Calcolo complessità
Ciao a tutti,
vi scrivo perché non riesco a capire bene come calcolare la complessità di un algoritmo in C.
Ho fatto diverse ricerche su internet e letto più e più volte le incomprensibili slide del professore ma non riesco a capire quali sono le "regole" che stanno dietro i singoli calcoli.
Cioè ho capito che le istruzioni semplici come printf, scanf e di assegnamento hanno costo unitario $1$.
I problemi arrivano quando devo calcolare il costo di cicli come while e for. Il testo mi suggerisce di sommare i costi delle condizioni con i costi "interni" al ciclo, ma mi sembra chiaro che non è così semplice (manca qualcosa),
Ad esempio, se ho il seguente (e semplicissimo) algoritmo:
$i=0;$
while $(i*i
Il testo suggerisce che avrò i seguenti cosi:
la prima istruzione ha costo $1$ ovviamente,
il numero di test del ciclo avrà costo $sqrt(n) + 1$
gli assegnamenti interni hanno invece costo $sqrt(n)$
Quindi il costo totale dell'algoritmo è $2*sqrt(n)+2$
Non capisco da dove esca fuori quella radice..
Se qualcuno può aiutarmi gliene sarei davvero grato ^^
Grazie mille anticipatamente
vi scrivo perché non riesco a capire bene come calcolare la complessità di un algoritmo in C.
Ho fatto diverse ricerche su internet e letto più e più volte le incomprensibili slide del professore ma non riesco a capire quali sono le "regole" che stanno dietro i singoli calcoli.
Cioè ho capito che le istruzioni semplici come printf, scanf e di assegnamento hanno costo unitario $1$.
I problemi arrivano quando devo calcolare il costo di cicli come while e for. Il testo mi suggerisce di sommare i costi delle condizioni con i costi "interni" al ciclo, ma mi sembra chiaro che non è così semplice (manca qualcosa),
Ad esempio, se ho il seguente (e semplicissimo) algoritmo:
$i=0;$
while $(i*i
Il testo suggerisce che avrò i seguenti cosi:
la prima istruzione ha costo $1$ ovviamente,
il numero di test del ciclo avrà costo $sqrt(n) + 1$
gli assegnamenti interni hanno invece costo $sqrt(n)$
Quindi il costo totale dell'algoritmo è $2*sqrt(n)+2$
Non capisco da dove esca fuori quella radice..
Se qualcuno può aiutarmi gliene sarei davvero grato ^^
Grazie mille anticipatamente
Risposte
Edit: credo (spero) di aver capito.
Riassumento in una sorta di tabella il metodo è il seguente?
Istruzioni semplici (printf,scanf,assegnamento): costo $1$
ciclo while: ricavo il costo della condizione (nel caso $i^2
So che questo schema è molto confusionario ma ho cercato di renderlo più comprensibile possibile.
Ditemi se e dove ho sbagliato
Grazie mille ^^
Riassumento in una sorta di tabella il metodo è il seguente?
Istruzioni semplici (printf,scanf,assegnamento): costo $1$
ciclo while: ricavo il costo della condizione (nel caso $i^2
So che questo schema è molto confusionario ma ho cercato di renderlo più comprensibile possibile.
Ditemi se e dove ho sbagliato
Grazie mille ^^
Up! Nessuno che sa aiutarmi?
L'unica regola è che devi contare quante volte il ciclo viene eseguito e moltiplicare tale valore per Il costo del ciclo e del test. Ma questo calcolo potrebbe in generale essere molto complicato.
Ah perfetto, capito!
Invece il calcolo della complessità asintotica sarebbe più semplice? Sapresti spiegarmelo in maniera molto "pratica" (il concetto generale l'ho capito, mi interessa solo applicare queste regole ad alcuni algoritmi parecchio complessi..)
Grazie mille!
Invece il calcolo della complessità asintotica sarebbe più semplice? Sapresti spiegarmelo in maniera molto "pratica" (il concetto generale l'ho capito, mi interessa solo applicare queste regole ad alcuni algoritmi parecchio complessi..)
Grazie mille!
Le difficoltà sono tendenzialmente le stesse..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo