E 'possibile valutare l'efficienza di un algoritmo verificabile rispetto a soluzioni alternative che non sono già state costruite? [chiuso]

I always wondered if there was a way to consider an alternative without developing it (or developing it entirely)?

Sì. C'è.

Si chiama "design".

Costruisci un modello (idealmente un modello matematico) di ogni diverso algoritmo.

Fai qualche analisi su quel modello per ottenere la complessità temporale degli algoritmi "Big-O".

Gli algoritmi con meno tempo di solito tendono ad essere più veloci.

Come suggerito da S.Lott, il modo standard per farlo è con astrazione alla notazione Big-O . Ha dimostrato che per gli algoritmi, questa considerazione asintotica è un buon predittore sulla performance reale.

Ma a volte, è troppo approssimativo (ad esempio, non puoi dire quale implementazione di O (n ^ 2) è più veloce) ea volte è fuorviante (può esserci un'implementazione O (n) che è più lenta per i soliti set di input di una O (n ^ 2) implementazione). Ecco perché ci sono molte ricerche sulla prevedibilità delle prestazioni nella nostra università, con una metodologia e uno strumento chiamato Palladio . Se sei interessato, dai un'occhiata e vedi che tali previsioni sono tutt'altro che banali. Se sei ancora più interessato, provalo!

Puoi provare a fare un'approssimazione con alcune tecniche:

• Confronta algoritmi esistenti e già implementati che funzionano in modo simile o sono parti dell'algoritmo che vuoi valutare,
• Costruisci un modello matematico di ogni algoritmo e valuta i modelli (vedi la risposta di S.Lott),
• Costruisci le parti più essenziali, relative alle prestazioni, di ciascun algoritmo e definiscili.

Detto questo, otterrai solo un'idea. Potrebbe funzionare perfettamente in alcuni casi. Può fallire completamente in altri , perché hai omesso l'ottimizzazione del compilatore, o come funziona il processore, o qualche cosa strana in una lingua o in un runtime, ecc.

Ecco perché quando vedi le domande su Programmes.SE "È A più veloce di B", "Se cambio questo e quello, diventerà più veloce?", l'unica risposta che ricevono è invitare l'autore della domanda al profilo l'applicazione.

Prima di tutto devi confrontare la complessità asintotica degli algoritmi (la notazione Big-O che le persone hanno menzionato qui). Questo ti dà un modo per valutare rapidamente quale algoritmo sarà più veloce. Anche se O (n ^ 2) potrebbe essere più veloce di O (n) per una piccola dimensione di input, il fatto che tu sia preoccupato per le prestazioni mi dice che la tua dimensione di input non è così piccola.

Se l'algoritmo alternativo supera l'analisi della complessità, ma non si è ancora sicuri se si tratta di una scelta migliore, allora ci devono essere alcuni dati di riferimento per questo. Chi ha inventato l'algoritmo deve aver scritto un articolo su di esso e deve aver fatto una sorta di valutazione. Potresti essere in grado di avere un'idea della performance dal foglio. A volte gli autori pubblicano i dati che hanno usato per la valutazione, quindi potresti essere in grado di confrontare il tuo algoritmo sugli stessi dati. E, naturalmente, puoi sempre contattare gli autori e chiedere.