# Domanda su Algoritmi di ordinamento

**URL:** <https://forum.olinfo.it/t/domanda-su-algoritmi-di-ordinamento/7813>\
**Category:** Algoritmi\
**Created:** [8 Novembre 2022, 9:04pm UTC](https://forum.olinfo.it/t/domanda-su-algoritmi-di-ordinamento/7813 "2022-11-08T21:04:40Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![ololol](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/o/35a633/32.png) [@ololol](https://forum.olinfo.it/u/ololol)\
**Post date:** [8 Novembre 2022, 9:04pm UTC](https://forum.olinfo.it/t/domanda-su-algoritmi-di-ordinamento/7813/1 "2022-11-08T21:04:40Z")

</div>

1. Dimostrare che un qualunque algoritmo di ordinamento che proceda per confronti  
su n elementi ha un costo computazionale di Omega (n log n).

Salve ragazzi sto preparando l’esame di algoritmi primo anno di informatica mi sono imbattuto in questa osservazione(grazie ai soliti algoritmi come quick sort merge sort heap sort ecc…) che ho notato essere vera ma non riesco a capire e dimostrare in maniera chiara e coincisa il perchè potete aiutarmi ?

---

<div class="post-metadata">

**Author:** ![Glauco](https://forum.olinfo.it/user_avatar/forum.olinfo.it/glauco/32/2371_2.png) [@Glauco](https://forum.olinfo.it/u/Glauco)\
**Post date:** [9 Novembre 2022, 2:19pm UTC](https://forum.olinfo.it/t/domanda-su-algoritmi-di-ordinamento/7813/2 "2022-11-09T14:19:41Z")

</div>

> **[Algoritmo di ordinamento | Ordinamento per confronti-scambi e digitale](https://it.wikipedia.org/wiki/Algoritmo_di_ordinamento#Ordinamento_per_confronti-scambi_e_digitale)**
>
> A seconda del tipo di operazione che viene effettuata, si hanno due differenti tipi di ordinamento: l'ordinamento che effettua confronti e scambi (
>   
>     
>       
> a
> ≤
> b
> :
> e
> x
> c
> h
> (
> a
> ,
> b
> )
>       
>     
> {\\displaystyle a\\leq b:exch(a,b)}
>   
> ) e l'algoritmo digitale che accede all'informazione tramite un gruppo di bit alla volta.

Qui la dimostrazione è spiegata bene, ma forse non è quello che cerchi

---

<div class="post-metadata">

**Author:** ![Argon18](https://forum.olinfo.it/user_avatar/forum.olinfo.it/argon18/32/2611_2.png) [@Argon18](https://forum.olinfo.it/u/Argon18)\
**Post date:** [12 Novembre 2022, 11:26pm UTC](https://forum.olinfo.it/t/domanda-su-algoritmi-di-ordinamento/7813/3 "2022-11-12T23:26:35Z")

</div>

Puoi considerare l’operazione di sortare un array come trovare una permutazione sortata tra tutte quelle che puo’ assumere  
Assumendo che gli elementi siano tutti distinti ci sono n! permutazioni  
Naturalmente pero’ non e’ necessario controllare tutte le n! permutazioni ma puoi fare una cosa analoga alla ricerca binaria  
Compiendo una comparazione tra 2 elementi in modo ottimale si riesce al massimo a tagliare a meta’ lo spazio di ricerca  
La comparazione successiva ottimale puo’ eliminare successivamente meta’ dello spazio di ricerca restante  
Questa funzione ha complessita’ O(log2(n!)) = O(log2(n) + log2(n-1) + … log2(1)) = O(n\*log2(n))