Abbiamo veramente bisogno di algoritmi efficienti? [duplicare]

TL; DR O (n ^ 2.81) può sembrare un piccolo guadagno rispetto a O (n ^ 3), ma con l'aumentare del set di dati le differenze diventano molto grandi, molto veloci.

Come ti senti quando una pagina web richiede 5-6 secondi per caricare invece di 1-2 secondi? Che ne dici se Google Maps impiega 20-30 secondi per trovare il percorso migliore invece di 5-10 secondi?

Pensa a cosa succede quando viaggi a grande distanza nello spazio e sei fuori di 1 grado. Ogni piccola somma che puoi disattivare può aumentare drasticamente il tuo obiettivo. Più devi raggiungere il bersaglio più lontano che sarai.

Gli algoritmi efficienti sono importanti quando si gestiscono grandi quantità di dati. Qualcosa che cresce esponenzialmente crescerà incredibilmente velocemente. Più alto è l'esponente più rapida è la crescita. Quando si ha a che fare con miliardi di record, questo inizia a essere davvero importante.

Per i set di dati più piccoli l'ottimizzazione preventiva è considerata una cosa negativa. Dovresti aspettare di vedere dove il programma sta usando il maggior tempo di elaborazione e ottimizzare quel codice (vedi la regola 80-20 ).

Dai anche un'occhiata a unisci l'ordinamento su qualcosa come bubble sort per notare l'enorme differenza tra un algoritmo efficiente e uno inefficiente.

Do computer scientists and mathematicians research such algorithms just for fun/out of curiosity/so they have an original dissertation topic or are there really some real life situations in which naive algorithms are too slow and we need a more efficient one?

L'efficienza è la chiave non per divertimento o per curiosità ma per essere in grado di risolvere i problemi più velocemente in informatica più spesso rispetto allo sviluppo generale del software.

Anche se è vero che i computer sono abbastanza veloci da fare calcoli di O(n) come:

List x = [1,2,3,4,5,6]
print [i for i in x]

A volte quando abbiamo algoritmi che hanno complessità come O(n^2) o anche O(n log(n)) affrontiamo problemi di scalabilità. Quando il set di dati che stiamo eseguendo l'iterazione o esegue qualsiasi computazione in espansione, richiede più tempo per il calcolo. Pertanto, se siamo in grado di trovare algoritmi in grado di ridurre la complessità temporale da dire O(n) a O(log n) , siamo in grado di vedere una differenza maggiore su set di dati più grandi.

Vedi questo ad esempio:

Vogliamo provare e ottenere algoritmi il più vicino possibile alle aree verdi.

Una delle ragioni principali per cui la complessità è un argomento importante nell'informatica è a causa delle classi di complessità P e NP e il tentativo di provare se P = NP , che potrebbe non sembrare un grosso problema nel contesto della programmazione; ma diventa un enorme affare con concetti come la crittografia.

Per uno scenario reale, prendiamo il problema dei commessi viaggiatori che è O(2^nn^2) . Questo problema non è risolvibile in tempo polinomail ( P ) e quindi appartiene alla classe dei problemi di NP perché non c'è ancora ancora un algoritmo per risolverlo in P . Tuttavia, se esiste una ricerca e una soluzione per risolverlo in P , ci sono molte implicazioni che possiamo applicare ad altri algoritmi.

Vale anche la pena dare un'occhiata agli ordinamenti degli algoritmi, ad esempio l'ordinamento delle bolle ha una complessità di O(n^2) , mentre abbiamo trovato algoritmi migliori per l'ordinamento come Heapsort che ha il caso peggiore O(n log(n)) .

Ci sono un sacco di situazioni di vita reale in cui sono ricercate queste ottimizzazioni, mi vengono in mente prima tutti i tipi di simulazioni (nucleare, astronomia, medicina, fisica ...).

E per quanto riguarda i semplici guadagni di produttività perché il foglio di calcolo calcola 10 secondi più velocemente, il video esegue il rendering in 3,5 ore anziché in 4, la banca elabora milioni di transazioni 15 minuti più velocemente, ecc?

E ci sono guadagni "non produttivi", come il tuo videogioco abbastanza veloce da far sì che l'esecuzione dei tuoi comandi sia in ritardo di soli 0,2 secondi anziché di 0,4.

Qualsiasi core CPU / GPU con oltre il 90% di utilizzo (nemmeno in modo continuo) è la prova che vogliamo più .

Molti problemi di ottimizzazione del mondo reale sono limitati dalla quantità di tempo CPU che si è disposti a dedicare a loro. In alcuni casi è possibile eseguire il pesante sgranocchiare in modalità batch, quindi è meno un problema, ma non è sempre un'opzione. Esempio di mondo reale: abbiamo una lista delle parti desiderate, abbiamo un pezzo di legno per tagliarle con difetti nelle posizioni A, B & C. Come otteniamo il miglior risultato probabile? (Non è possibile una risposta perfetta perché non abbiamo ancora visto il resto del legno.) C'è qualcosa come due secondi da quando la fotocamera ha finito di analizzare il legno quando il legno è pronto per essere spinto nella sega - se tu impiega più tempo di quello che stai facendo girare a vuoto un pezzo di attrezzatura da $ 60k.

Nel frattempo, quando la macchina riduce di 6 volte il valore del legno all'anno, anche un piccolo miglioramento nella precisione della tua previsione vale molto.

L'efficienza è più importante che mai perché le prestazioni dei computer sono migliorate! L'hardware è diventato più veloce, ma allo stesso tempo la memoria disponibile e la larghezza di banda sono aumentate altrettanto.

Dato che tendiamo a utilizzare le risorse disponibili, un processore dovrà eseguire 10 volte tanto lavoro se la memoria aumenta di 10 volte. Se si esegue un'operazione O (n) sulla memoria disponibile, allora sarà necessario se la velocità del processore e la memoria aumentano di 10 volte. Ma se la complessità è peggiore di O (n), l'operazione diventerà molto più lenta se il processore e la memoria aumentano di 10 volte.

Quindi gli algoritmi efficienti diventano effettivamente più importanti, più le prestazioni dei nostri computer sono migliorate.

Una grande quantità di ricerche sulla complessità è davvero più matematica che pratica. Spesso si può trarre maggiore beneficio da un algoritmo "meno efficiente" che da uno "più efficiente". Preferiresti moltiplicare le matrici in 10 ^ 3 millisecondi o in 1000000 × 10 ^ 2.81 millisecondi?

C'è anche il fatto che in molti casi è preferibile avere un algoritmo che ovviamente lavori piuttosto che uno il cui funzionamento dipende da una prova lunga, complessa e delicata. È solo una cosa in meno di cui preoccuparsi.

Spesso è meglio migliorare il fattore costante, parallelismo o design semplicemente migliore a livello di codice.

Ma d'altra parte se hai a che fare con una matrice con un milione di righe e colonne, la potenza di n inizia ad avere un significato reale e n ^ 2.81 passaggi più complicati possono richiedere meno tempo di n ^ 3 semplici.

Molti software sarebbero messi in ginocchio. Se cambi solo l'accesso al dizionario su un tempo lineare invece che costante. Cambia i tuoi algoritmi grafici per disegnare un pixel alla volta e il tuo computer muore.

Nessun computer è abbastanza veloce da gestire codice abbastanza brutto.