Domanda complessità algoritmo di ordinamento

[Darèios89]

Sia A un array di n elementi. Supponiamo che gli elementi siano tutti ordinati tranne i log n elementi che sono fuori posto. Qual è la complessità de migliore algoritmo che riordina l'array?

Secondo me siccome non abbiamo informazioni sull' input, si deve considerare il caso dell' ordinamento per confronti che impiega tempo pari a [tex]\theta(n\log(n))[/tex] , mi rimangono logn elementi da ordinare quindi mi verrebbe da dire:

[tex]\theta(n\log(\log(n)))[/tex]

[apatriarca]

Molti degli algoritmi di ordinamento non sono in grado di sfruttare il fatto che un array sia quasi ordinato. Se infatti osservi la complessità dei più famosi algoritmi con complessità \( O(n \log n) \), questi hanno tutti complessità nel caso migliore uguale a \( O(n \log n) \) e non \( O(n) \). La tua analisi non è quindi valida. In questi casi, in effetti, algoritmi come l'insertion sort potrebbero essere avvantaggiati.

[Darèios89]

Quindi dici che utilizzando l' insertion sort posso avere complessità pare a [tex]\theta(n)[/tex] che è la complessità migliore?

[hamming_burst]

@Darèios89: ma stai ancora qua sugli algoritmi
scherzo...

ma se un algoritmo è quasi ordinato si potrebbe fare un analisi del genere. Se abbiamo che il numero di elementi è $n$, ci sono $k,\ k Si può scandire il vettore e salvare in un array temporaneo $temp[]$ i $k$ elementi non in ordine, costo $O(n)$.
Ordiniamo $temp[]$ in $O(klog(k))$ con un qualche algoritmo.
Facciamo un marge dei due vettori ordinati con costo $O(n)$.

Non so se ne vale lo sforzo comunque...

[Darèios89]

Ciao ham!!!!!!!!!!! Come stai!!!!!
Si sono ancora qui non ti libererai mai...
No in realtà alcuni ragazzi devono fare l' esame dopodomani e mi incuriosivano alcune domande, quindi cercavo le risposte.
Per l' ennesima volta fiasco, ma pazienza...XD
Grazie ad entrambi!

[apatriarca]

Quello che stavo dicendo è che non tutti gli algoritmi di ordinamento sono in grado di sfruttare l'ordinamento parziale dell'array. L'insertion sort è un esempio di algoritmo che è in grado di sfruttare l'ordinamento parziale (se l'array è già ordinato l'insertion sort visita infatti tutti gli elementi una sola volta senza fare scambi), mentre algoritmi come quick sort, merge sort, heap sort.. non ne sono in grado. Se vuoi sfruttare l'ordinamento parziale devi quindi fare riferimento a qualcuno di questi algoritmi. L'insertion sort è il più semplice, ma ci sono anche algoritmi più complessi come lo smooth sort e il timsort.

Edit: L'analisi dell'insertion sort che avevo fatto era sbagliata e credo che la sua complessità in questo caso debba essere \(O( n \log n ) \) nel caso peggiore e \( O(n) \) nel caso migliore (quello medio non ci provo neanche a calcolarlo). Credo che la complessità nel caso peggiore sia \( O( n \log n) \) per ogni algoritmo di ordinamento con confronti (ma forse smooth sort e tim sort - o altri - si comportano meglio dell'insertion sort in questo caso).