README.pl-PL.md

JavaScript Algorytmy i Struktury Danych

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.

Struktury Danych

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

Algorytmy

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

Algorytmy według tematu

• 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

Algorytmy według paradygmatu

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.

Jak używać repozytorium

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'

Pomocne informacje

Źródła

â–¶ Struktury Danych i Algorytmy na YouTube

Big O Notacja

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.

Big O notacja	Obliczenia na 10 elementów	Obliczenia na 100 elementów	Obliczenia na 1000 elementów
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

Złożoność operacji struktury danych

Struktura Danych	Dostęp	Szukaj	Umieszczanie	Usuwanie	Komentarze
Szereg	1	n	n	n
Sterta	n	n	1	1
Kolejka	n	n	1	1
Lista Powiązana	n	n	1	1
Tablica funkcji mieszanej	-	n	n	n	W wypadku idealnej funkcji skrótu koszt mógłby sie równać O(1)
Binarne Drzewo Poszukiwań	n	n	n	n	W przypadku zrównoważonych kosztów drzew byłoby O(log(n))
B-Drzewo	log(n)	log(n)	log(n)	log(n)
Drzewa czerwono-czarne	log(n)	log(n)	log(n)	log(n)
AVL Drzewo	log(n)	log(n)	log(n)	log(n)
Filtr Blooma	-	1	1	-	Fałszywe dotatnie są możliwe podczas wyszukiwania

Sortowanie Tablic Złożoności Algorytmów

Nazwa	Najlepszy	Średni	Najgorszy	Pamięć	Stabilność	Komentarze
Sortowanie bąbelkowe	n	n2	n2	1	Yes
Sortowanie przez wstawianie	n	n2	n2	1	Yes
Sortowanie przez wybieranie	n2	n2	n2	1	No
Sortowanie przez kopcowanie	n log(n)	n log(n)	n log(n)	1	No
Sortowanie przez scalanie	n log(n)	n log(n)	n log(n)	n	Yes
Szybkie sortowanie	n log(n)	n log(n)	n2	log(n)	No	Szybkie sortowanie jest zazwyczaj robione w miejsce O(log(n)) stosu przestrzeni
Sortowanie Shella	n log(n)	zależy od luki w układzie	n (log(n))2	1	No
Sortowanie przez zliczanie	n + r	n + r	n + r	n + r	Yes	r - największy numer w tablicy
Sortowanie Radix	n * k	n * k	n * k	n + k	Yes	k -długość najdłuższego klucza