Calcolare empiricamente l’ordine di crescita di un algoritmo

22 ottobre 2015

Programmazione

Come facciamo a calcolare empiricamente l’ordine di crescita di un algoritmo del quale non abbiamo il codice sorgente?!

Un metodo semplicissimo consiste nel raddoppiare ogni volta la taglia dell’input (N) e prendere il tempo di esecuzione dell’algoritmo (running time), successivamente calcoliamo il rapporto (ratio) tra ogni misurazione e la successiva, di questo rapporto ne calcoliamo il logaritmo in base due.

Seguendo la successione vedremo che questo valore andrà a stabilizzarsi, quindi abbiamo scoperto il valore dell’ordine di crescita del nostro algoritmo segreto 😉

Vediamo un esempio chiarificatore:

ordine crescita

 

come possiamo vedere in questo esempio abbiamo ogni volta raddoppiamo la taglia dell’input (N) del quale abbiamo calcolato il logaritmo in base due del rapporto (ratio) tra le varie misurazioni, il quale converge a 1.89 circa.

Quindi, in maniera molto semplice e veloce abbiamo calcolato l’ordine di crescita del nostro algoritmo “segreto”, che ha un valore di 1.89, quindi avremo N^1.89

 

Se ti è stato utile il mio articolo, spendi un secondo del tuo tempo e dammi un +1, Google ed io ne saremmo felici 🙂 Grazie mille 🙂

No comments yet.

Leave a Reply

*