Czego zwykle nie uczą na bootcampach. Praktyczne implementacje typowych algorytmów w idiomatycznym JavaScript.

Przedstawię Ci, jak myśleć o algorytmach, jak je szacować, optymalizować, rekurencje i wszystko, co musisz wiedzieć jako wiarygodny inżynier JavaScript. Rzeczy, które chciałbym wiedzieć na początku swojej kariery podczas rozmowy kwalifikacyjnej.

Zrelaksuj się, nie spiesz się i ciesz się.

Co to jest algorytm?

• Jest to zestaw instrukcji umożliwiających rozwiązanie problemu.
• Twoim zadaniem / celem jako inżyniera jest rozwiązywanie problemów
• Podczas rozwiązywania problemów identyfikujesz wzorce / techniki, które są bardziej wydajne / wydajne
• Pamiętaj, że istnieje wiele sposobów rozwiązania pojedynczego problemu, ale który z nich jest najszybszy, gdy rośnie ilość danych wejściowych do przetworzenia?

• Złożoność czasowa to liczba operacji prymitywnych wykonywanych w algorytmie w miarę dostarczania do niego danych
• Pomaga zrozumieć szybkość algorytmu
  - Jest to przybliżenie czasu potrzebnego do wykonania algorytmu w miarę wzrostu ilości danych wejściowych
  - Jest to przybliżenie, ponieważ nie można dokładnie przewidzieć, ile czasu zajmie wykonanie algorytmu na każdym możliwym typie architektury maszyn / środowiska / konfiguracje sprzętowe / itp.
  Zamiast używać sekund lub milisekund, współczynnik wzrostu jest używany do wskazania, jak bardzo algorytm ma tendencję do rozrastania się w miarę dostarczania mu danych.
• Podsumowując, złożoność czasowa to liczba operacji prymitywnych wykonywanych w celu rozwiązania problemu w miarę wzrostu nakładów iw najgorszym przypadku .
• Pomyśl o kosztach wykonywanych operacji. Im szybszy algorytm, tym więcej danych może przetworzyć w rozsądnym czasie.

• Złożoność przestrzeni to ilość pamięci używanej w odniesieniu do rozmiaru danych wejściowych podczas wykonywania algorytmu

Załóżmy, że masz listę dostawców VPN na platformie. Chcesz znaleźć najdroższe i najtańsze. Pamiętaj, że dostawcy są dodawani codziennie, więc lista stale rośnie.

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

W trakcie przeglądania listy śledzisz najwyższą i najniższą cenę za iterację.

Zobaczmy, jak podczas wyszukiwania najdroższej ceny:

       |  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 |

• wraz ze wzrostem liczby n dostawców liczba operacji rośnie o potęgę dwóch (4², 11², 100² operacji).
• więc w zasadzie im więcej danych rośnie, tym większa będzie praca

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

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

• Każda pozycja na liście jest sprawdzana tylko raz w iteracji pętli i jest przechowywana, jeśli spełnia warunek (to max, to min)
• tutaj złożoność czasowa jest liniowa ( tutaj 2n) z powodu dwóch odrębnych pętli, które patrzą na wszystkie elementy raz
• liczba operacji do wykonania jest dwa razy większa niż liczba elementów lub mówiąc po prostu, wraz ze wzrostem danych praca wzrasta o 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 },
 ...
];

• nie potrzeba pętli, tylko 2 operacje, ustaw pierwszą wartość jako minimum i ustaw ostatnią wartość jako maksymalną
• dlatego złożoność czasowa algorytmu stale rośnie, ponieważ niezależnie od liczby n elementów liczba operacji pozostaje taka sama

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

• Wzrost złożoności czasowej jest reprezentowany przez dużą notację O.
• do tej pory widzieliśmy:
  - Kwadratową złożoność czasową reprezentowaną przez O (n²)
  - Liniową złożoność czasową reprezentowaną przez O (n)
  - Stałą złożoność czasową reprezentowaną przez O (1)
• Ponieważ złożoność czasowa jest przybliżeniem, pomijane są nieistotne liczby, dlatego złożoność czasowa 2n wynosi tylko O ​​(n), a nie O (2n)
• Czynniki są pomijane:
  - 5n to O (n) [wymawiane „o z n”]
  - 24n² to O (n²) [wymawiane „o z n kwadratu”]
• oto graficzne przedstawienie wzrostu:

• znajomość złożoności czasowej pomaga zrozumieć ograniczenia algorytmu pod względem ilości danych, które może wytrzymać, zanim ukończenie zajmie milion lat
• Pomaga również w dokonywaniu kompromisów przy wyborze jednego algorytmu zamiast innych w oparciu o określone warunki
• pojęcie poprawności algorytmicznej dotyczy wyboru algorytmu, czy jest to najbardziej optymalne / poprawne rozwiązanie?

• zauważ z logarytmiczną złożonością czasu (O (log n)) , im więcej danych dostarczasz algorytmowi, tym mniej i mniej pracy musi on wykonać, ale także zauważ, że na początku zajmuje to więcej czasu niż kwadratowa złożoność czasowa
• więc od bardzo wydajnego do bardzo wolnego, masz:
  - C onstałą złożoność czasową reprezentowaną przez O (1)
  - Logarytmiczną złożoność czasową reprezentowaną przez O (log n)
  - Liniową złożoność czasową reprezentowaną przez O (n)
  - Kwadratową złożoność czasową reprezentowaną przez O (n²)
  - C ubiczna złożoność czasowa reprezentowana przez O (n³)
  - Wykładnicza złożoność czasowa reprezentowana przez O (k)