Quote Originariamente inviata da Lodin Visualizza il messaggio
è corretto dire che:
l'operazione dominante di quest'algoritmo è l'operazione di assegnazione che viene eseguita 3 volte per ogni incremento di i fino ad arrivare ad i=n/2 quindi la complessità di tempo è data da: O(3*n/2) ?



codice:
void inversione_array ( int array[], int n)
{
    int i=0, tmp=0;


    for(i=0;i<n/2;i++)
    {
        tmp=array[i];
        array[i]=array[n-1-i];
        array[n-1-i]=tmp;
    }


    return;
}
e per quanto riguarda la complessità di spazio?
allora per quanto riguarda il tempo , O(3*n/2) non si dice , si scrive O(n) , poichè 3*n/2 è una funzione che cresce al più come una funzione lineare ( la notazione asintotica ignora le costanti per cui ad esempio ache 2*n diventa--> 0(n) usando l'asintotica : http://www.dsi.unifi.it/~costa/lucid...Asintotica.pdf forse può tornarti utile.
Lo spazio , dipende dalla dimensione dell'array , ma deduco che l'array abbia dimensione n , quindi è ovviamente lineare , le costanti ( che nel caso della memoria sono le singole variabili )vengono trascurate . Conculendo anche per lo spazio possiamo dire che questo algoritmo occupa O(n) memoria . Ora però il calcolo della complessità di memoria non viene fatto quasi mai, poichè viviamo in un tempo dove la memoria occupata non è più un grande problema , quindi a meno che l'algoritmo non debba elaborare grandi quantità di dati ( sto parlando di roba nell'ordine di TB ) l'analisi della memora non viene fatta.
Comunque sia per il calcolo del tempo d'esecuzione che per il calcolo della memoria si fa un'analisi ammortizzata , ecco perchè viene usata la notazione asintotica