Come misurare l'accuratezza dell'algoritmo?

Naviga le tue risposte
2

Ho alcuni algoritmi di ottimizzazione (per trovare la funzione minima) e vorrei verificare quanto sono buoni. Supponiamo che io costruisca casi di test e confronti i risultati effettivi con quelli teorici. Quali misure dovrei usare per stimare se la funzione minima è stata effettivamente trovata?

Ho pensato a:

  • numero medio di valutazioni delle funzioni (± deviazione standard)
  • tasso di successo (con quale frequenza trova effettivamente minimo)

Ci sono altri che ho perso (diciamo che l'algoritmo termina 1e-4 dalla soluzione nota, quindi è già successo o no?)

La mia preoccupazione principale è la complessità del tempo non . È l'accuratezza dell'algoritmo nei casi in cui la soluzione esatta potrebbe non essere mai trovata (ad esempio spazi di soluzione multidimensionale). Come si calcola la velocità di convergenza?

    
posta alex 25.08.2014 - 23:30
fonte

2 risposte

2

Il modo semplice per dire come "vicina" una soluzione è a un'altra è determinare il suo errore standard.

L'errore standard è la deviazione standard delle risposte che ottieni. Quindi si divide la distanza tra due soluzioni dall'errore standard. Se la risposta è inferiore a 1, è abbastanza vicino, perché potresti ottenere una grossa differenza solo dalla casualità. Se meno di 2, è comunque rispettabile. Oltre 2, dite di no, non chiudere.

Un altro modo è ottenere la seconda derivata della soluzione rispetto a qualsiasi cosa tu stia variando. Quella seconda derivata rappresenta la "nitidezza" della soluzione, e l'errore standard è proporzionale alla radice quadrata inversa di quello.

Se ti piace la matematica, guarda qui e qui .

    
risposta data 26.08.2014 - 03:22
fonte
2
  1. Scopri la complessità dell'algoritmo (la sua Big O)
  2. Misura il tempo necessario per eseguire una iterazione (se è costante), o misurare più iterazioni e ammortizzare il tempo necessario.

Questo è tutto.

Per ottenere il tempo di esecuzione di un particolare n, prendi solo la quantità di tempo per 1 iterazione e collegalo al tuo O grande. Quindi, per esempio, se il tuo Big O è O (n ^ 2), e uno l'iterazione impiega 100 millisecondi, quindi il tempo di esecuzione per n = 6 sarà 10 secondi.

    
risposta data 25.08.2014 - 23:53
fonte

Leggi altre domande sui tag

In C ++, la memoria semantica di acquisizione-rilascio è transitoria? Inserimento / rimozione e atomicità del database test di unità