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:
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