[C] Complessità di tempo e spazio di un algoritmo

[Lodin]

è 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) ?

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?

[xeno92]

è 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) ?

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

[Lodin]

capisco...
grazie mille sei stato molto chiaro!
In ogni caso (te lo chiedo per vedere se ho capito davvero) se utilizziamo una notazione non asintotica e che quindi considera anche le costanti, è corretto dire che la complessità dell'algoritmo sopra scritto è 3*n/2?

Inoltre, come hai scritto la notazione asintotica ignora le costanti, ma allora un'algoritmo che ha complessità n^2 e un'altro che ha complessità n, avranno la stessa complessità O(n)? non è strano?

[M.A.W. 1968]

Fino a quando non prenderai in mano un serio testo di algoritmica e/o metodi matematici per la complessità computazionale, limitati alla regoletta empirica: data una generica espressione in forma chiusa, tipicamente polinomiale e in funzione della quantità di dati elaborati, che esprime il totale delle operazioni svolte, per il momento ti basti sapere che il passaggio alla notazione asintotica avviene banalmente considerando una e una sola volta il termine col massimo esponente, a meno di qualsivoglia coefficiente.

Dunque si avrà, ad esempio, da 4n² + 12n + 255 -> O(n²), e via esemplificando. Riguardo alla complessità in spazio, vi sono comunque numerosi casi nei quali è indispensabile considerarla e saperla calcolare correttamente, al di fuori del contesto scolastico.


A proposito: algoritmo è un termine maschile, dunque in italiano si scrive "un algoritmo": non occorre alcun apostrofo dopo l'articolo.

[Lodin]

Capisco, grazie mille per il chiarimento!
Leggerò il pdf linkato da xeno sperando di capire almeno le basi


P. S per quanto riguarda l'errore ortografico, non so come sia successo... Stanchezza o il correttore che ha corretto erroneamente (sono al cell) xD

[xeno92]

guarda lodin stai attento a cosa si intende per costante... prendiamo ad esempio n^2 , in questo caso 2 non può essere considerato una costante poichè sta all'esponente , e la funzione non è lineare ma è una parabola, invece N^(2*n) in questo caso il due invece è una costante poichè non influisce sul tipo di funzione , infatti che ci sia il 2 o che non ci sia la funzione rimane sempre di tipo esponenziale. Comunque leggi bene il documento che ti ho postato e studia bene su altre fonti la notazione asintotica... BUONO STUDIO