[ALGORITMO] Complessità asintotica nell'inserimento ordinato

[Kaamos]

Ci si picchia sul caso migliore che e' praticamente inutile!

Originariamente inviato da Who am I
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.

Ha parlato di lista semplice (quindi deduco lista concatenata semplice), e se parla d'inserimento ordinato suppongo ci sia una relazione d'ordine totale sull'insieme su cui si lavora, non ho capito cosa e' ambiguo.

Originariamente inviato da LeaderGL
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!

E' un inserimento non un ordinamento, quindi puo' essere O(1) nel caso migliore...
Se la lista e' vuota che confronti possiamo fare? Hai specificato nel tuo ultimo post quello che intendevo io.

EDIT: doppio post, pardon

[LeaderGL]

Originariamente inviato da Kaamos
Ci si picchia sul caso migliore che e' praticamente inutile!

si, però è simpatico

Originariamente inviato da Kaamos E' un inserimento non un ordinamento, quindi puo' essere O(1) nel caso migliore...
Se la lista e' vuota che confronti possiamo fare? Hai specificato nel tuo ultimo post quello che intendevo io.

In realtà ha detto "inserimento ordinato", quindi non è semplicemente un inserimento (in quel caso sarebbe sempre O(1)). Mentre un inserimento ordinato è come un "ordinamento", con l'eccezione che il caso migliore (che può verificarsi nelle condizioni che ho scritto 2 post più su) ha una complessità di O(1).
Ma concordo che non si verificherà mai. Per valutare gli algoritmi si usa il caso peggiore (raramente quello medio).

[Kaamos]

Originariamente inviato da LeaderGL
si, però è simpatico



In realtà ha detto "inserimento ordinato", quindi non è semplicemente un inserimento (in quel caso sarebbe sempre O(1)). Mentre un inserimento ordinato è come un "ordinamento", con l'eccezione che il caso migliore (che può verificarsi nelle condizioni che ho scritto 2 post più su) ha una complessità di O(1).
Ma concordo che non si verificherà mai. Per valutare gli algoritmi si usa il caso peggiore (raramente quello medio).

Qualsiasi inserimento in strutture dati "lineari" (array/vettori, liste concatenate...) che mi viene in mente ha un caso migliore in O(1), che sia un inserimento ordinato o meno e' indifferente.

Comunque ci siamo capiti.