javascript-algorithms

JavaScript Algorytmy i Struktury Danych

CI codecov

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, Español, Português, Русский, Türk, Italiana

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

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

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.

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.

Big O grafy

Ź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