PDA

Visualizza la versione completa : [ALGORITMO] ComplessitÓ asintotica nell'inserimento ordinato


5t4rdu5t
02-05-2012, 19:26
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?

Kaamos
03-05-2012, 01:50
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?

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.

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.

Scara95
03-05-2012, 07:09
O(n) Ú solo il caso peggiore, che poi possa essere frequente un numero vicino a questo Ú un'altro discorso.

5t4rdu5t
03-05-2012, 09:27
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.


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)


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.

penso sia lo stesso ragionamento per l' inserimento...

LeaderGL
03-05-2012, 11:19
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.

Who am I
03-05-2012, 11:28
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.

LeaderGL
03-05-2012, 11:34
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!

kerbero1984
03-05-2012, 11:38
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Ó .

LeaderGL
03-05-2012, 11:45
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.

Kaamos
03-05-2012, 11:46
Quando possibile (e in questo caso lo e') sarebbe meglio utilizzare la notazione theta anziche' O grande.


Originariamente inviato da Scara95
O(n) Ú solo il caso peggiore, che poi possa essere frequente un numero vicino a questo Ú un'altro discorso.

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 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...

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.

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.


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.

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).

Inserire in tempo costante non significa necessariamente inserire a casaccio.

Loading