Differenza tra grafici e analisi asintotica per confrontare i tempi di esecuzione di un algoritmo

Question

La domanda dice più o meno quello che sto chiedendo.

Ho un algoritmo e stavo vagando quale è l'approccio migliore per ottenere un tempo di esecuzione "Big-Oh" - attraverso un grafico e tracciando il numero di input rispetto al tempo di esecuzione o attraverso l'analisi asintotica?

Per il mio grafico Attualmente sto usando:

private int startTime = System.currentTimeMillis(); //At start of algorithm 
private int endTime = System.currentTimeMillis(); //At the end of algorithm 
int runningTime = endTime - startTime; 

Qual è la differenza tra i due metodi di 'misurazione' il tempo di esecuzione di un alogrithm?

Answer 1

Il problema con "empirico" (traccia il tempo di esecuzione rispetto alle dimensioni di input), è funziona solo per il test case fornito.

L'analisi "teorica" ​​offre tutte le insidie ​​dell'algoritmo, è possibile analizzare il caso migliore/caso medio/... utilizzando la matematica, ed è garantito che sia corretto.

Un buon esempio comune è lo simplex algorithm, che è abbastanza veloce in genere, ma ha occasionalmente un tempo di esecuzione nel caso peggiore esponenziale per alcuni input.

D'altra parte, a causa dell'analisi asintotica che ignora le costanti e si applica solo per "input abbastanza grandi", sono praticamente inutili se si prevede che l'input sia relativamente piccolo ed è difficile distinguere tra 2 algoritmi nella stessa classe di complessità, ma con diverse costanti e costante fanno la differenza nel codice di produzione.

tl; dr: ognuno ha il proprio utilizzo e la combinazione di entrambi offre risultati migliori rispetto all'utilizzo di uno solo di essi.

Come nota a margine, quando si utilizza il metodo empirico, assicurarsi di utilizzare gli strumenti statistici e in particolare statistical hypothesis testing prima di trarre conclusioni. Inoltre, ricorda sempre che gli strumenti empirici sono validi solo per la classe di problemi che hai controllato (quindi se non controlli per un array ordinato per esempio, non saprai che quicksort potrebbe impiegare molto più tempo se ne incontra uno).