Algoritmo di ordinamento: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Elenco degli algoritmi di ordinamento:
corretto counting sort |
mNessun oggetto della modifica |
||
Riga 46:
Si vuole dimostrare che in un algoritmo '''confronti e scambi''' la complessità è <math>\mathsf \Omega( n\log n)</math>. Data in input una sequenza <math>e_1, e_2, ... e_n</math> di n elementi, l'azione dell'algoritmo si può rappresentare come un albero binario, per ogni sequenza di ingresso ci sarà un cammino all'interno dell'albero, questo perché si ha una permutazione delle sequenze, infatti il numero di permutazioni possibili su n elementi sono <math>n!</math> combinazioni che corrispondono al numero di nodi dell'albero.
Date due permutazioni distinte esse identificano diversi cammini all'interno dell'albero. <math>n!</math> è il numero di foglie nell'albero di decisione dove n è il numero di elementi da ordinare. Date <math>n!</math> foglie
<math>h(T) \leq \lceil \log_2 n! \rceil</math>
| |||