Complessità in spazio e tempo liste in c

[gabama]

Per definire la complessità in spazio e tempo di una lista in c si deve controllare i record attivazione che apre per la prima e le operazioni che esegue per la seconda?

[YuYevon]

Beh i concetti di complessità di spazio e di tempo (e anche di complessità di tempo asintotica, che però è un'altra cosa) si definiscono sugli algoritmi e non sulle strutture dati, quindi a rigore non ha senso chiedersi "quale sia la complessità di spazio e di tempo di una lista in C" (o qualunque cosa sia).

Per essere più precisi, se hai implementato un algoritmo che esegue delle operazioni su una lista e se non vi sono altre strutture dati (array, altre liste e roba varia), allora la complessità di spazio di questo algoritmo è data dal numero dei nodi della lista in questione.

Per quanto riguarda la complessità di tempo, dipende dalle operazioni che esegue l'algoritmo che hai scritto.

[gabama]

ti ringrazio YuYevon,sei stato molto gentile,quindi per riassumere se si ha ad esempio n elementi nella lista la complessità e O (n) ,mentre per le operazioni intendi cosa fa la funzione che opera sulla lista,nel senso le volte che si scorre la lista?
Ciao e grazie ancora

[YuYevon]

Originariamente inviato da gabama
quindi per riassumere se si ha ad esempio n elementi nella lista la complessità e O (n)

Se hai solo quella struttura dati sì, altrimenti devi considerare il size anche delle altre, sempre se questo influisce sensibilmente sulla complessità di spazio relativa alla sola lista: supponiamo cioè che la tua lista mediamente abbia 30 nodi; se usi anche un array di 4-5 elementi, questo aumenta sì lo spazio occupato (ovviamente), ma non in maniera "asintotica", cioè se prima la complessità di spazio era S(N) = O(N), continuerà ad essere O(N) visto che l'aggiunta di 4 elementi, in questo caso, non cambia molto. Se invece hai (sempre per esempio) un'altra lista di size M all'incirca simile a quello della lista precedente, è più corretto scrivere che S(N) = O(N + M), sebbene poi sia pur sempre una complessità lineare.

mentre per le operazioni intendi cosa fa la funzione che opera sulla lista,nel senso le volte che si scorre la lista?

Sì, devi valutare il tempo impiegato da ciascuna operazione che compi sulla lista. Cosa fai di preciso? Inserimenti? Ricerche? Eliminazioni? Ordinamenti? Nel caso di inserimenti ed eliminazioni, i nodi interessati sono sempre quelli in fondo alla lista (o in testa) oppure si trovano in un punto particolare?

Insomma devi valutare un po' tutte queste cose. Non posso dirti nulla di più preciso, non conoscendo l'algoritmo.