Quello che di solito non insegnano nei bootcamp. Implementazioni pratiche di algoritmi comuni in JavaScript idiomatico.

Ti presenterò come pensare agli algoritmi, come stimarli, ottimizzarli, le ricorsioni e tutto ciò che devi sapere come ingegnere JavaScript credibile . Cose che avrei voluto sapere all'inizio della mia carriera durante l'intervista.

Rilassati, prenditi il ​​tuo tempo e divertiti.

Cos'è un algoritmo?

• È un insieme di istruzioni per risolvere un problema.
• In qualità di ingegnere, il tuo lavoro / obiettivo è risolvere i problemi
• Quando si risolvono i problemi, si identificano modelli / tecniche più efficienti / performanti
• Ricorda che ci sono molti modi per risolvere un singolo problema, ma qual è il più veloce quando la quantità di dati di input da elaborare aumenta?

• La complessità temporale è il numero di operazioni primitive che vengono eseguite in un algoritmo mentre i dati vengono forniti ad esso
• Aiuta a ragionare sulla velocità di un algoritmo
  - È un'approssimazione del tempo necessario per eseguire un algoritmo all'aumentare dei dati di input
  - È un'approssimazione perché non è possibile prevedere esattamente quanto tempo ci vorrà per eseguire un algoritmo su ogni possibile tipo di architetture della macchina / ambienti / configurazioni hardware / ecc.
  Quindi, invece di usare secondi o millisecondi, viene utilizzato un fattore di crescita per indicare quanto un algoritmo tende a crescere man mano che gli vengono forniti dati.
• Per riassumere la complessità temporale è il numero di operazioni primitive eseguite per risolvere un problema man mano che l'input cresce e nel peggiore dei casi .
• Pensa al costo delle operazioni eseguite. Più veloce è un algoritmo, più dati può elaborare in un tempo ragionevole.

• La complessità dello spazio è la quantità di memoria utilizzata rispetto alla dimensione dell'input durante l'esecuzione di un algoritmo

Supponiamo che tu abbia un elenco di provider VPN su una piattaforma. Vuoi risolvere i più costosi e quelli più economici. Ricorda che i fornitori continuano ad essere aggiunti ogni giorno, quindi l'elenco continua a crescere.

const vpnProviders = [
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 { name: 'tatoVpn', price: 99 },
 { name: 'tutoVpn', price: 54 },
 ...
];

Mentre scorri l'elenco, tieni traccia del prezzo più alto e più basso per iterazione.

Vediamo una rappresentazione di quando si cerca il prezzo più costoso:

       |  234  |  321  |  99  |  54  |
--------------------------------------
  234  |  --   |  321  |  234 |  234 |
--------------------------------------
  321  |  321  |  --   |  321 |  321 |
--------------------------------------
   99  |  234  |  321  |  --  |  99  |
--------------------------------------
   54  |  234  |  321  |  99  |  --  |

 # of providers (n)  |   4  |  11  |  100     |  2000      |
------------------------------------------------------------
 # of operations     |  16  |  121 |  10,000  |  4,000,000 |

• all'aumentare del numero n di provider, il numero di operazioni aumenta della potenza di due (4², 11², 100² operazioni).
• quindi fondamentalmente, più i tuoi dati crescono, più enorme sarà il lavoro necessario

      |  234  |  321   |  ...  |  99  |  54  |
----------------------------------------------
max?  |  234  |  321   |  ...  |  321 |  321 |

      |  234  |  321   |  ...  |  99  |  54  |
- --------------------------------------------
min?  |  234   |  234  |  ...  |  99  |  54  |

• Ogni elemento nell'elenco viene esaminato solo una volta nell'iterazione del ciclo e viene memorizzato se soddisfa la condizione (è max, è min)
• qui la complessità temporale è lineare ( qui, 2n) a causa dei due cicli distinti che guardano tutti gli elementi una volta
• il numero di operazioni da eseguire è il doppio del numero di elementi o semplicemente, man mano che i dati crescono, il lavoro aumenta di 2.

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   8  |   22 |  200  |  4,000 |

const vpnProviders = [
 { name: 'tutoVpn', price: 54 },
 { name: 'tatoVpn', price: 99 },
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 ...
];

• nessuna necessità di loop, solo 2 operazioni, impostare il primo valore come minimo e impostare l'ultimo valore come massimo
• quindi la complessità temporale dell'algoritmo ha una crescita costante perché indipendentemente dal numero n di elementi, il numero di operazioni rimane lo stesso

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   2 |    2  |    2  |   2    |

• La crescita della complessità temporale è rappresentata dalla grande notazione O
• Finora abbiamo visto:
  - Complessità temporale quadratica rappresentata da O (n²)
  - Complessità temporale lineare rappresentata da O (n)
  - Complessità temporale costante rappresentata da O (1)
• Poiché la complessità è un'approssimazione, i numeri insignificanti vengono eliminati quindi una complessità temporale di 2n è solo O (n) non O (2n)
• I fattori vengono eliminati:
  - 5n è O (n) [pronunciato "o di n"]
  - 24n² è O (n²) [pronunciato "o di n quadrato"]
• ecco una rappresentazione grafica della crescita:

• conoscere la complessità temporale ti aiuta a capire i limiti di un algoritmo in termini di quanti dati può sopportare prima che ci voglia un milione di anni per terminare
• Aiuta anche a fare dei compromessi sulla scelta di un algoritmo rispetto ad altri in base a determinate condizioni
• la nozione di correttezza algoritmica riguarda la scelta di un algoritmo, è la soluzione più ottimale / corretta?

• notare con una complessità temporale logaritmica (O (log n)) , più dati alimentate l'algoritmo e meno lavoro deve fare, ma notate anche che all'inizio richiede più tempo di una complessità temporale quadratica
• quindi da molto performante a estremamente lento, si ha:
  - Complessità temporale costante rappresentata da O (1)
  - Complessità temporale l ogaritmica rappresentata da O (log n)
  - Complessità temporale lineare rappresentata da O (n)
  - Complessità temporale quadratica rappresentata da O (n²)
  - Complessità temporale cubica rappresentata da O (n³)
  - Complessità temporale esponenziale rappresentata da O (k)