To repozytorium zawiera wiele przykładów JavaScript opartych na znanych algorytmach i strukturach danych.

Każdy algorytm i struktura danych zawiera osobny plik README wraz z powiązanymi wyjaśnieniami i odnośnikami do dalszego czytania (włącznie z tymi do YouTube videos).

Read this in other languages: English 简体中文, 繁體中文, 한국어, Français

Jesteśmy w trakcie pisania książki, która w jasny i specyficzny sposób, wyjaśni główne algorytmy. Jeżeli chcesz dostać powiadomienie o tym kiedy książka “JavaScript Algorithms†zostanie wydana,kliknij tutaj.

Struktura danych to sposób uporządkowania i przechowywania informacji w komputerze żeby mogłaby być sprawnie dostępna i efektywnie zmodyfikowana. Dokładniej, struktura danych jest zbiorem wartości danych, relacjami pomiędzy nimi, zadaniami lub działaniami, które mogą dotyczyć danych.

B - Początkujący, A - Zaawansowany

• B Lista
• B Lista Dwukierunkowa
• B Kolejka
• B Stos
• B Tabela Skrótu
• B Sterta
• B Kolejka Priorytetowa
• A Trie
• A Drzewo
  • A Wyszukiwanie Binarne
  • A AVL Drzewo
  • A Drzewa czerwono-czarne
  • A Drzewo Segmentu - z przykładami zapytań o min / max / sumie sum
  • A Drzewo Fenwicka (Drzewo Indeksowane Binarnie)
• A Graf (zarówno skierowane i nieukierunkowane)
• A Rozłączny Zestaw
• A Filtr Blooma

Algorytm jest to skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Sposób postępowania prowadzący do rozwiązania problemu.

B - Początkujący, A - Zaawansowany

• Matematyka
  • B Manipulacja Bitami - ustaw / uzyskaj / aktualizuj / usuwaj bity, mnożenie / dzielenie przez dwa, tworzenie negatywów itp.
  • B Silna
  • B Ciąg Fibonacciego
  • B Test Pierwszorzędności (metoda podziału na próby)
  • B Algorytm Euclideana - obliczyć Największy Wspólny Dzielnik (GCD)
  • B Najmniejsza Wspólna Wielokrotność (LCM)
  • B Sito Eratosthenes-a - znajdowanie wszystkich liczb pierwszych do określonego limitu
  • B Jest Potęgą Dwójki - sprawdź, czy liczba jest potęgą dwóch (algorytmy naiwne i bitowe)
  • B Trójkąt Pascala
  • A Partycja Całkowita
  • A Algorytm Liu Huia - przybliżone obliczenia na podstawie N-gonów
• Zestawy
  • B Produkt Kartezyjny - wynik wielu zestawów
  • B Przetasowanie Fisher Yates-a - losowa permutacja kończącej się serii
  • A Zestaw Zasilający - podzbiór wszystkich serii
  • A Permutacje (z albo bez powtórzeń)
  • A Kombinacje (z albo bez powtórzeń)
  • A Najdłuższa Wspólna Podsekwencja (LCS)
  • A Najdłuższa Wzrostająca Podsekwencja
  • A Najkrótsza Wspólna Supersekwencja (SCS)
  • A Problem Knapsacka - "0/1" i "Rozwiązany"
  • A Maksymalna Podtablica - "Metoda Siłowa" i "Dynamiczne Programowanie" (Kadane-a) wersje
  • A Suma Kombinacji - znajdź wszystkie kombinacje, które tworzą określoną sumę
• Łańcuchy
  • B Odległość Hamminga - liczba pozycji, w których symbole są różne
  • A Odległość Levenshteina - minimalna odległość edycji między dwiema sekwencjami
  • A Algorytm Knuth–Morris–Pratta (Algorytm KMP) - dopasowywanie wzorców (dopasowywanie wzorców)
  • A Algorytm Z - szukanie podłańcucha(dopasowywanie wzorców)
  • A Algorytm Rabin Karpa - szukanie podłańcucha
  • A Najdłuższa Wspólna Podłańcucha
  • A Dopasowanie Wyrażeń Regularnych
• Szukanie
  • B Wyszukiwanie Liniowe
  • B Jump Search (lub Przeszukiwanie Bloku) - szukaj w posortowanej tablicy
  • B Wyszukiwanie Binarne - szukaj w posortowanej tablicy
  • B Wyszukiwanie Interpolacyjne - szukaj w równomiernie rozłożonej, posortowanej tablicy
• Sortowanie
  • B Sortowanie bąbelkowe
  • B Sortowanie przez wymiane
  • B Sortowanie przez wstawianie
  • B Sortowanie stogowe
  • B Sortowanie przez scalanie
  • B Sortowanie szybkie - wdrożenia w miejscu i nie na miejscu
  • B Sortowanie Shella
  • B Sortowanie przez zliczanie
  • B Sortowanie pozycyjne
• Drzewa
  • B Przeszukiwanie w głąb (DFS)
  • B Przeszukiwanie wszerz (BFS)
• Grafy
  • B Przeszukiwanie w głąb (DFS)
  • B Przeszukiwanie wszerz (BFS)
  • B Algorytm Kruskala - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
  • A Algorytm Dijkstry - znajdowanie najkrótszej ścieżki z pojedynczego źródła w grafie
  • A Algorytm Bellmana-Forda - znajdowanie najkrótszych ścieżek do wszystkich wierzchołków wykresu z jednego wierzchołka
  • A Algorytm Floyd-Warshalla - znajdź najkrótsze ścieżki między wszystkimi parami wierzchołków
  • A Detect Cycle - zarówno dla wykresów skierowanych, jak i nieukierunkowanych(wersje oparte na DFS i Rozłączny Zestaw)
  • A Algorytm Prima - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
  • A Sortowanie Topologiczne - metoda DFS
  • A Punkty Artykulacji - Algorytm Tarjana (oparty o DFS)
  • A Mosty - Oparty na algorytmie DFS
  • A Ścieżka Euleriana i Obwód Euleriana - Algorytm Fleurya - Odwiedź każdą krawędź dokładnie raz
  • A Cykl Hamiltoniana - Odwiedź każdy wierzchołek dokładnie raz
  • A Silnie Połączone Komponenty - Algorytm Kosaraja
  • A Travelling Salesman Problem - najkrótsza ścieżka która odwiedza każde miasto i wraca miasta początkującego
• Niezkategorizowane
  • B Wieża Hanoi
  • B Kwadratowa Matryca Obrotu - algorytm w miejscu
  • B Jump Game - cofanie, dynamiczne programowanie (od góry do dołu + od dołu do góry) i przykłady chciwego
  • B Unikatowe Ścieżki - cofanie, dynamiczne programowanie i przykłady oparte na Trójkącie Pascala
  • A Problem N-Queens
  • A Knight's Tour

Paradygmat algorytmiczny jest ogólną metodą lub podejściem, które jest podstawą projektowania klasy algorytmów. Jest abstrakcją wyższą niż pojęcie algorytmu, podobnie jak algorytm jest abstrakcją wyższą niż program komputerowy.

• Metoda Siłowa - Sprawdza wszystkie możliwosci i wybiera najlepsze rozwiązanie.
  • B Wyszukiwanie Liniowe
  • A Maksymalna Podtablica
  • A Problem z Podróżującym Sprzedawcą - najkrótsza możliwa trasa, która odwiedza każde miasto i wraca do miasta początkowego
• Chciwy - wybierz najlepszą opcję w obecnym czasie, bez względu na przyszłość
  • B Jump Game
  • A Niezwiązany Problem Knapsacka
  • A Algorytm Dijkstry - znalezienie najkrótszej ścieżki do wszystkich wierzchołków grafu
  • A Algorytm Prima - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
  • A Algorytm Kruskala - znalezienie Minimalnego Drzewa Opinającego (MST) dla ważonego nieukierunkowanego wykresu
• Dziel i Zwyciężaj - podziel problem na mniejsze części, a następnie rozwiąż te części
  • B Wyszukiwanie Binarne
  • B Wieża Hanoi
  • B Trójkąt Pascala
  • B Algorytm Euclideana - obliczyć Największy Wspólny Dzielnik(GCD)
  • B Sortowanie przez scalanie
  • B Szybkie Sortowanie
  • B Drzewo Przeszukiwania W Głąb (DFS)
  • B Graf Przeszukiwania W Głąb (DFS)
  • B Jump Game
  • A Permutacje (z albo bez powtórzeń)
  • A Kombinacje (z albo bez powtórzeń)
• Programowanie Dynamiczne - zbuduj rozwiązanie, korzystając z wcześniej znalezionych podrzędnych rozwiązań
  • B Ciąg Fibonacciego
  • B Jump Game
  • B Unikatowe Scieżki
  • A Dystans Levenshteina - minimalna odległość edycji między dwiema sekwencjami
  • A Najdłuższa Wspólna Podsekwencja (LCS)
  • A Najdłuższa Wspólna Podłańcucha
  • A Najdłuższa Wzrostająca Podsekwencja
  • A Najkrótsza Wspólna Supersekwencja
  • A 0/1 Problem Knapsacka
  • A Partycja Całkowita
  • A Maksymalne Podtablice
  • A Algorytm Bellman-Forda - znalezienie najkrótszej ścieżki wszystkich wierzchołków wykresu
  • A Algorytm Floyd-Warshalla - znajdź najkrótsze ścieżki między wszystkimi parami wierzchołków
  • A Dopasowanie Wyrażeń Regularnych
• Algorytm z nawrotami - podobny do metody siłowej, próbuje wygenerować wszystkie możliwe rozwiązania, jednak za każdym razem generujesz następne rozwiązanie które testujesz jeżeli zaspokaja wszystkie warunki, tylko wtedy generuje kolejne rozwiązania. W innym wypadku, cofa sie, i podąża inna ścieżka znaleźenia rozwiązania. Zazwyczaj, używane jest przejście przez Przeszukiwania W Głąb(DFS) przestrzeni stanów.
  • B Jump Game
  • B Unikatowe Scieżki
  • A Cykl Hamiltoniana - Odwiedź każdy wierzchołek dokładnie raz
  • A Problem N-Queens
  • A Knight's Tour
  • A Zestaw Sumy - znajduje wszystkie zestawy które tworzą określoną sumę
• Metoda Podziału i Ograniczeń - Pamięta o niskonakładowym rozwiązaniu znalezionym na każdym etapie szukania nawrotu, używa kosztu niskonakładowego kosztu, które dotychczas zostało znalezione jako niska granica najmniejszego kosztu do rozwiązanie problemu, aby odrzucić cząstkowe rozwiązania o kosztach większych niż niskonakładowe rozwiązanie znalezione do tej pory. Zazwyczan trajektoria BFS, w połączeniu z trajektorią Przeszukiwania W Głąb (DFS) drzewa przestrzeni stanów jest użyte.

Zainstaluj wszystkie zależnosci

npm install

Uruchom ESLint

Możesz to uruchomić aby sprawdzić jakość kodu.

npm run lint

Uruchom wszystkie testy

npm test

Uruchom testy używając określonej nazwy

npm test -- 'LinkedList'

Playground

Możesz pociwiczyć ze strukturą danych i algorytmami w ./src/playground/playground.js zakartotekuj i napisz testy do tego w ./src/playground/__test__/playground.test.js.

Następnie uruchom następującą komendę w celu przetestowania czy twoje kod działa według oczekiwań:

npm test -- 'playground'

â–¶ Struktury Danych i Algorytmy na YouTube

Kolejność wzrastania algorytmów według Big O notacji.

Źródło: Big O Cheat Sheet.

Poniżej umieszczamy listę najbardziej używanych Big O notacji i ich porównania wydajności do róznych rozmiarów z wprowadzonych danych.