Informatica 2 Liceo Scientifico Scienze Applicate/BubbleSort: differenze tra le versioni

 

L'efficienza di un algortimo viene espressa con l'ordine di complessita', generalmente esso dipende dal numero n di elementi del vettore, se le perazioni da fare per completare l'algoritmo fossero proporzionali al numero di elementi del vettore l'odine di complessità sarebbe indicato come <math> O(n)</math> e si legge O grande di n. Nel caso del bubblesort le cose vanno peggio di O(n) e i calcoli da farsi sono proporzionalia a <math>n^2</math> secondo un fattore di proporzionalita' di 0.5 si ha allora <math>O(\frac{n^{2}}{2}) </math>. Per il quicksort l'ordine di complessita' e' del <math>O(n\log_{2}n) </math> , meglio del bubblesort ma peggio di un andamento solamente proporzionale ad n . Vediamo in un grafico l'andamento delle istruzioni da effettuare in 3 casi diversi di complessita'<br />

 

{{Avanzamento|100%|4 dicembre 2014}}