ho un dubbio sulla coplessità asintotica riguardante la lista semplice nella operazione di inserimento ordinato. Da quello che ho capito dovrebbe essere O(1) se l' inserimento si fa in testa oppure O(n) se bisogna fare di volta in volta i confronti.
Un altro dubbio è sulla ricerca... io penso sia sempre O(1) e O(n), ho fatto un ragionamento giusto?
L'inserimento in una lista collegata ordinata è in O(n) nel caso peggiore (e direi anche in quello medio), mentre nel caso migliore come dici si è in O(1) ma è poco significativo, non entra nemmeno in gioco l'ordinamento.Originariamente inviato da 5t4rdu5t
ho un dubbio sulla coplessità asintotica riguardante la lista semplice nella operazione di inserimento ordinato. Da quello che ho capito dovrebbe essere O(1) se l' inserimento si fa in testa oppure O(n) se bisogna fare di volta in volta i confronti.
Un altro dubbio è sulla ricerca... io penso sia sempre O(1) e O(n), ho fatto un ragionamento giusto?
Anche ricerca è in O(1) nel caso migliore e O(n) negli altri, però specifica di quale caso stai parlando altrimenti non è molto preciso dire "io penso sia sempre O(1) e O(n)"; quando non si specifica ci si riferisce solitamente al caso peggiore.
O(n) é solo il caso peggiore, che poi possa essere frequente un numero vicino a questo é un'altro discorso.
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares
allora devo specificare in qst modo?Originariamente inviato da Kaamos
L'inserimento in una lista collegata ordinata è in O(n) nel caso peggiore (e direi anche in quello medio), mentre nel caso migliore come dici si è in O(1) ma è poco significativo, non entra nemmeno in gioco l'ordinamento.
l' inserimento nel caso migliore è O(1) perchè se tratta dell inserimento in testa indipendentemente dal numero di nodi della lista, O(n) perchè bisogna scorrere tutta la lista quindi caso peggiore e caso medio(anche se caso medio non l' ho capito tanto bene)
penso sia lo stesso ragionamento per l' inserimento...Originariamente inviato da Kaamos
Anche ricerca è in O(1) nel caso migliore e O(n) negli altri, però specifica di quale caso stai parlando altrimenti non è molto preciso dire "io penso sia sempre O(1) e O(n)"; quando non si specifica ci si riferisce solitamente al caso peggiore.
scusate ma come può un algoritmo di inserimento ORDINATO avere un caso migliore di O(1) ed uno peggiore di O(n) ??
Per avere O(1) significa che inserisci "dove capita"...e di conseguenza non hai la certezza di un inserimento ORDINATO.
Administrator of NAMDesign.Net
Non mi è chiaro cosa intendi per "inserimento ordinato".
Non basta questo termine per far capire cosa hai in mente tu.
Se intendi l' inserimento in un vettore ordinato, la complessità è O(log N) nel caso peggiore e O(1) nel caso migliore.
Però bisogna che ti spieghi meglio.
Non può essere O(1) perchè altrimenti significherebbe che la complessità degli algoritmi di ordinamento può essere O(1) e non è così.
Deve essere come minimo O(n), perchè i confronti li devi fare!
Administrator of NAMDesign.Net
A mio avviso se l'insieme è ordinato non è possibile che sia O(n) nel caso peggiore che è quello che si
prende in riferimento per i confronti asintotici. DI fatti concordo con l'obzione di specificare cosa si intende per insieme ordinato . Perchè se parliamo di un vettore allora un inserimento in un insieme ordinato può essere fatto con tecnica di divide et impera e quindi ad ogni iterata ne scarto sempre una metà .
Bisogna specificare varie cose:
1) struttura dati
2) tipo di ordinamento
però in linea generale per effettuare un inserimento ordinato (e quindi inserire dei numeri in un vettore,lista,albero,heap,etc) si può arrivare ad affermare che nel caso migliore l'inserimento ha una complessità di O(1).
Il caso migliore si verifica quando gli elementi da inserire sono già ordinati dal più grande al più piccolo. Perchè l'unico confronto da fare è "elemento_da_inserire <= primo_elemento", la risposta sarà SI e quindi si fa un unico confronto e si inserisce l'elemento in testa.
Tutto il resto (caso medio e caso peggiore) dipendono dall'algoritmo utilizzato. Il miglior algoritmo per effettuare un ordinamento (e quindi anche un inserimento ordinato) ha come caso medio e come caso peggiore O(n log n). Non si scende al di sotto.
Administrator of NAMDesign.Net
Quando possibile (e in questo caso lo e') sarebbe meglio utilizzare la notazione theta anziche' O grande.
Direi che anche il caso medio e' in O(n) se non c'e' nessuna particolare probabilita' da considerare, visto che il numero di operazioni resta lineare al numero di elementi.Originariamente inviato da Scara95
O(n) é solo il caso peggiore, che poi possa essere frequente un numero vicino a questo é un'altro discorso.
Direi di si, comunque se stai studiando all'universita' o altrove e non hai ancora trattato il caso medio puoi tranquillamente non specificarlo per il momento.Originariamente inviato da 5t4rdu5t
allora devo specificare in qst modo?
l' inserimento nel caso migliore è O(1) perchè se tratta dell inserimento in testa indipendentemente dal numero di nodi della lista, O(n) perchè bisogna scorrere tutta la lista quindi caso peggiore e caso medio(anche se caso medio non l' ho capito tanto bene)
penso sia lo stesso ragionamento per l' inserimento...
Per l'inserimento la complessita' e' la stessa della ricerca semplicemente perche' fai le stesse operazioni della ricerca piu' l'inserimento, che puoi fare in tempo costante.
Pur volendo mantenere la struttura ordinata, nel caso migliore (lista vuota, minore del primo elemento o altro, dipende dai test effettuati nell'algoritmo) l'inserimento e' indipendente dal numero di elementi presenti nella struttura dati, per questo lo classificherei come O(1).Originariamente inviato da LeaderGL
scusate ma come può un algoritmo di inserimento ORDINATO avere un caso migliore di O(1) ed uno peggiore di O(n) ??
Per avere O(1) significa che inserisci "dove capita"...e di conseguenza non hai la certezza di un inserimento ORDINATO.
Inserire in tempo costante non significa necessariamente inserire a casaccio.
Permessi di invio
Rispondi quotando