Cosa significa per tempo di esecuzione previsto e tempo di esecuzione medio di un algoritmo?

Il tempo previsto è solo la media, prevista , il tempo di esecuzione dell'algoritmo utilizzando l'input previsto .

Supponiamo che tu abbia qualche milione di record utente e desideri ordinarli, potresti voler utilizzare un algoritmo che è il più adatto per il tuo input, e come tale fornisce i migliori atteso tempo di esecuzione, al contrario di un algoritmo che ha il miglior tempo di esecuzione nel caso peggiore ma un tempo di esecuzione peggiore peggiore.

A volte ad esempio i fattori costanti per la complessità temporale di un algoritmo sono così alti che ha senso utilizzare algoritmi con una complessità temporale peggiore ma fattori costanti più piccoli, in quanto ti danno attesi migliori tempo di esecuzione con input piccoli, anche se sarebbe terribilmente sovraperformato con input più grandi.

Forse un esempio migliore sarebbe il classico algoritmo di quicksort, che ha il tempo di esecuzione nel caso peggiore di O (n²) ma il tempo di esecuzione medio previsto di O (n log n), indipendentemente dall'input . Questo perché l'algoritmo usa (o meglio, può usare , a seconda dell'implementazione) la randomizzazione. Quindi è un cosiddetto algoritmo randomizzato . Funziona in modo leggermente diverso ad ogni invocazione anche con lo stesso input . In quanto tale, non vi è alcun input di caso peggiore universale per l'implementazione, perché l'input del caso peggiore dipende dal modo in cui l'algoritmo sceglie il pivot per dividere l'input dato. E come tale, non si può semplicemente fornire un input predefinito che causa il tempo di esecuzione nel caso peggiore. Questo è spesso il caso di algoritmi randomizzati, che mirano a una migliore durata media prevista, indipendentemente dall'input.

Si tratta di utilizzare l'algoritmo giusto per l'input a portata di mano.

Il tempo di esecuzione previsto di un algoritmo randomizzato è un concetto ben definito, proprio come il tempo di esecuzione del caso peggiore. Se un algoritmo è randomizzato, il suo tempo di esecuzione è anche casuale, il che significa che possiamo definire il valore atteso del suo tempo di esecuzione.

Un esempio ben noto è Quicksort: se selezioniamo i pivot in modo casuale, possiamo dimostrare che il tempo di esecuzione previsto diventa O (n log n), anche se il suo peggior tempo di esecuzione resta O (n ^ 2). Un esempio in cui la randomizzazione è molto potente è il più piccolo problema di circoscrizione: esiste un algoritmo semplice il cui caso peggiore è O (n ^ 3), ma in attesa, il suo tempo di esecuzione è solo O (n).

Il tempo medio di esecuzione viene solitamente utilizzato quando si parla del comportamento di un algoritmo "per la maggior parte degli input". Definiamo un modo per generare un input a caso, per esempio riempiamo un array con numeri casuali, oppure permutiamo casualmente i numeri da 1 a n (quindi non duplicati), o lanciamo una moneta e otteniamo un set discendente o ascendente di numeri. Il tempo di esecuzione medio di un algoritmo per quella distribuzione casuale di input è quindi il tempo di esecuzione previsto dell'algoritmo (nel qual caso l'algoritmo potrebbe non essere randomizzato, ma l'input è).

Ad esempio: ci sono problemi geometrici per cui esistono algoritmi che sembrano funzionare bene a prima vista, finché non si scopre un modo molto strano di distribuire, ad esempio, le linee di input. Se si assume che le linee siano distribuite casualmente, è possibile che questi strani scenari siano estremamente improbabili, quindi il tuo algoritmo si rivela buono.

Contrasto: il tempo di esecuzione previsto riguarda il modo in cui un algoritmo esegue "a meno che tu non abbia sfortuna": riprovare lo stesso algoritmo sullo stesso input ma con scelte casuali diverse può portare a risolverlo molto più velocemente. Il tempo medio di esecuzione parla di quanto bene un algoritmo esegue "per la maggior parte degli input": provare lo stesso algoritmo sullo stesso input non ti aiuterà (eccetto forse se l'algoritmo è anche randomizzato).