Costo computazionale asintotico di un algoritmo
Ciao a tutti, vi propongo questo quesito:
Il fatto è che non capisco cosa si intenda per "dimensione dei dati", ovvero se è riferito alla loro dimensione "fisica" oppure se intende raddoppiare i dati in ingresso, quindi 2n.
Nell'ultimo caso, ovvero il raddoppio dell'input, il costo dell'algoritmo sarebbe sempre $ O(n^3) $ ? visto che è dipendente da n, il raddoppio dei dati non cambierebbe il costo asintotico, o no? oppure diventa $ O(2n^3) $? boh!
grazie in anticipo!
Se un algoritmo ha costo $ O(n^3) $ , raddoppiando la dimensione dei dati, di quanto aumenta il costo?
Il fatto è che non capisco cosa si intenda per "dimensione dei dati", ovvero se è riferito alla loro dimensione "fisica" oppure se intende raddoppiare i dati in ingresso, quindi 2n.
Nell'ultimo caso, ovvero il raddoppio dell'input, il costo dell'algoritmo sarebbe sempre $ O(n^3) $ ? visto che è dipendente da n, il raddoppio dei dati non cambierebbe il costo asintotico, o no? oppure diventa $ O(2n^3) $? boh!
grazie in anticipo!
Risposte
Se non ci sono specifiche migliori (sul problema), quello che hai affermato corrisponde al vero.
Cioè $n$ indica i dati numerabili in input all'algoritmo (non al problema).
Per costo asintotico, la limitazione non cambia rimane sempre $O(n^3)$, quello che cambia sono le constanti (nascoste).
ma se conosci la teoria, se $g(n)$ è la funzione corrispondente all'algoritmo, $g(n) in O(n^3)$ e da definizione: $EEc>0, AAn>=m | g(n) <= cn^3$ in questo caso mettiamo che $c=1$.
Se i dati raddoppiano: viene $g(2n) in O(8n^3)$ in questo caso $c=8$
In parole povere, se i dati raddoppiano, l'algoritmo sarà "più lento" di un fattore lineare $8$.
Se hai dubbi chiedi pure
Cioè $n$ indica i dati numerabili in input all'algoritmo (non al problema).
Per costo asintotico, la limitazione non cambia rimane sempre $O(n^3)$, quello che cambia sono le constanti (nascoste).
ma se conosci la teoria, se $g(n)$ è la funzione corrispondente all'algoritmo, $g(n) in O(n^3)$ e da definizione: $EEc>0, AAn>=m | g(n) <= cn^3$ in questo caso mettiamo che $c=1$.
Se i dati raddoppiano: viene $g(2n) in O(8n^3)$ in questo caso $c=8$
In parole povere, se i dati raddoppiano, l'algoritmo sarà "più lento" di un fattore lineare $8$.
Se hai dubbi chiedi pure
Grazie mille ham_burst! chiaro e preciso!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo