Quanto è significativa la complessità temporale di Big-O di un algoritmo?

Con il piccolo n Big O è praticamente inutile e sono le costanti nascoste o anche l'effettiva implementazione che sarà più probabilmente il fattore decisivo per cui l'algoritmo è migliore. Questo è il motivo per cui la maggior parte delle funzioni di ordinamento nelle librerie standard passerà a un ordinamento di inserimento più veloce per gli ultimi 5 elementi. L'unico modo per capire quale sarà migliore è il benchmarking con set di dati realistici.

Big O fa bene a grandi serie di dati e discute su come un algoritmo scala, è meglio avere un algoritmo O(n log n) di un O(n^2) quando ti aspetti che i dati crescano in futuro, ma se O(n^2) funziona bene così com'è e le dimensioni degli input rimarranno probabilmente costanti, ma tieni presente che puoi aggiornarlo ma lasciarlo così com'è, ci sono probabilmente altre cose di cui devi preoccuparti adesso.

(Nota: tutti i "grandi" e "piccoli" nei paragrafi precedenti sono pensati per essere presi relativamente, piccolo può essere qualche milione e grande può essere cento dipende tutto da ciascun caso specifico)

Spesso ci sarà un trade-off tra tempo e spazio: per esempio quicksort richiede O(log n) di memoria extra mentre heapsort può usare O(1) di memoria extra, tuttavia le costanti nascoste in heapsort lo rendono meno attraente (c'è anche il problema di stabilità che rende il mergesort più attraente se non ti dispiace pagare i costi extra di memoria).

Un'altra cosa da considerare sono gli indici di database, queste sono tabelle aggiuntive che richiedono log(n) di tempo per aggiornare quando un record viene aggiunto, rimosso o modificato, ma consente le ricerche molto più velocemente ( O(log n) invece di O(n) ). decidere se aggiungerne uno è un costante mal di testa per la maggior parte degli amministratori di database: avrò abbastanza ricerche sull'indice rispetto alla quantità di tempo che passo ad aggiornare l'indice?

Un'ultima cosa da tenere a mente: gli algoritmi più efficienti sono quasi sempre più complicati di quello ingenuo diretto (altrimenti sarebbe quello che avresti usato dall'inizio). Ciò significa un'area di superficie più ampia per bug e codice che è più difficile da seguire, entrambi i problemi non banali da affrontare.

Molto significativo nella mia esperienza. Alla radice di molti problemi di prestazioni, spesso trovo queste cause ...

1. Mancato considerare l'intervallo di n per il quale verrà utilizzato l'algoritmo.
2. Mancata considerazione della complessità temporale dell'algoritmo utilizzato.
3. Mancata considerazione dei requisiti di memoria dell'algoritmo per il probabile intervallo di n.
4. Mancata considerazione delle differenze di latenza tra RAM, Disco, Rete, ecc.
5. (e non meno importante) Mancato test con dati di dimensioni realistiche.

Questo succede nei luoghi di routine nello sviluppo del software aziendale. Ad esempio ...

• Perché la mia query SQL viene eseguita così lentamente?
• Perché la mia interfaccia utente HTML + CSS + js funziona così lentamente? Sto solo facendo qualche operazione jQuery sul DOM?
• Perché la mia app .Net funziona così lentamente? Sto solo usando i set di dati per massaggiare alcuni dati e metterli in una griglia.

Nella maggior parte dei casi in cui n è noto per essere piccoli, non vale la pena dedicare molto tempo alla complessità.

Pensare all'intervallo atteso di n e valutare la complessità è un modo comprovato per sapere quando vale la pena di mettere in discussione algoritmi e architetture. Lo uso principalmente come strumento intuitivo per il calcolo del livello "nella mia testa" o "sul retro del cocktail". Mi fa risparmiare un sacco di tempo.

È uno strumento essenziale per la progettazione del software.

Ciò che è importante non è il valore che O vincola ma il tasso di crescita del valore che O vincola. È qui che arriva il calcolo.

Se prendi la derivata di log (n) per esempio, ottieni 1 / n come velocità di cambiamento. Ciò significa che il tempo impiegato da un algoritmo log (n) cresce come una velocità di 1 / n, il che significa che quando si aggiungono più valori al set, si ottiene un valore inferiore per f (1 / n). Lo stesso vale true su n '= 1, n ^ c' dove c è una costante = cn e c ^ n '= c ^ n (log (c)). Quindi hai un tasso di crescita molto più lento per il tempo impiegato per gli ordini inferiori rispetto a quelli più alti. Una volta colpito esponenziale, il tasso di crescita inizia a crescere ad una velocità superiore alla funzione base.

Quindi comprendere Big O consente di confrontare facilmente il tempo degli algoritmi per input, anche se l'input non è mai 'infinito'. Per inciso, infinito nello sviluppo di software o CS spesso significa "Arbitrariamente grande" piuttosto che l'infinito tecnico, matematico poiché i computer in pratica sono dispositivi finiti.

La complessità asintotica è davvero molto significativa. Conoscete la storia dell'inventore degli scacchi, che ha chiesto al re di dargli 2 ^ 65-1 chicchi di grano come ricompensa? :)

Sei corretto, un algoritmo polinomiale di alto livello rischia di essere inutile. E per sapere che la complessità temporale del tuo algoritmo è un polinomio di alto grado, devi guardare il big-O. Inoltre, una complessità temporale di O (1.00000001 ^ n) è rara. Ma tu vedi O (2 ^ n) tutto il tempo, come nel problema di soddisfacibilità booleana.

Se non comprendi la complessità del tuo algoritmo, puoi facilmente trovarti in una situazione in cui il tuo programma funziona bene con un input di test, ma si blocca quando il tuo cliente gli dà un input che è solo il doppio.

Direi che l'analisi big-O non è qualcosa su cui fai affidamento , è piuttosto una sorta di avvertimento sul rendimento.

Se qualcosa è O (2 ^ n), non significa che sia lento, ma significa che dovresti prestare attenzione ad esso.

Se ottimizzi qualche algoritmo, l'analisi big-O può mostrare quali posti devono essere misurati per primi, perché hanno maggiori probabilità di essere colli di bottiglia.

Come altri hanno detto, big-O conta se n può diventare grande. Il problema è che è di un tale interesse accademico che viene insegnato molto, quindi gli studenti finiscono per essere predisposti a pensare che sia la cosa solo che conta.

Quindi se entrano in progetti in cui i fattori costanti sono più grandi del necessario per ordine di grandezza, sono così impreparati che spesso non riconoscono nemmeno che potrebbe essere un problema.

I fattori costanti sono trattati come un ripensamento irrilevante, e agli studenti viene detto "usa un profiler" (tipicamente gprof ), nonostante la scarsa esperienza in termini di velocità effettiva.

significativo? Sì. Ma non racconta tutta la storia.

Ciò che la complessità asintotica ti dice è quanto bene il tuo programma scalerà rispetto alle dimensioni dell'input. Ad esempio, supponiamo di avere un programma che viene eseguito entro un tempo accettabile per il momento su piccoli input. Quindi la complessità ti dirà una stima approssimativa del tempo necessario per elaborare qualcosa di più fattori.

Ciò che non ti dice è la velocità con cui verrà effettivamente eseguito, perché ti mancano ancora due bit critici di informazioni:

• Il coefficiente / fattore costante : se il tuo algoritmo è O(1) ma il coefficiente è enorme , allora probabilmente non sarà di gran beneficio se non lavori con input ugualmente enormi .
• Il ridimensionamento per piccoli input : la complessità asintotica descrive il comportamento quando la dimensione di input si avvicina all'infinito. Tuttavia, il comportamento dell'algoritmo a piccole dimensioni di input può essere drasticamente diverso. Pertanto, se la tua applicazione coinvolge principalmente piccoli input, allora devi ottimizzare per quelli invece di preoccuparti della complessità asintotica.

La complessità asintotica va bene come una "stima zeroth-order" grezza per grandi input, ma quello che ti interessa è se qualcosa funziona in modo accettabile sugli input che ti interessano . Ciò comporterà un calcolo matematico e / o profilazione più complicato.

Un pensiero specifico su big-O dalla mia esperienza pratica: generalmente i fattori lineari dominano sulle costanti per qualsiasi dimensione decente N. Cioè, un algoritmo O (n ^ 2) è generalmente terribile rispetto a O (n), per dati di qualsiasi dimensione ragionevole Tuttavia, i fattori logaritmici possono essere paragonabili alle costanti in molti casi. In altre parole, anche per N abbastanza grande, O (nlogn) può essere comparabile o addirittura più veloce di O (n), a seconda delle costanti. Ad esempio, a volte è possibile fare lo stesso problema in cui uno dei passaggi consiste nel mettere tutti i dati in una tabella hash, che è O (n), oppure ordinando in O (nlogn). L'ordinamento di solito è implementato molto efficientemente nella maggior parte delle lingue, e l'hashing non ha necessariamente le costanti migliori, quindi ho visto che l'ordinamento ha battuto l'hashing.