JavaScript algoritmlari va ma'lumotlar tuzilmalari

Bu repozitoriyada JavaScript-ga asoslangan ko'plab mashhur algoritmlar va ma'lumotlar tuzilmalarining namunalari mavjud.

Har bir algoritm va ma'lumotlar tuzilmasining alohida README fayli bo'lib, unda tegishli tushuntirishlar va qo'shimcha o'qish uchun havolalar (shu jumladan YouTube videolariga ham havolalar) mavjud.

Read this in other languages: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türkçe, Italiana, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch, Uzbek עברית

Ma'lumotlar tuzilmalari

Ma'lumotlar tuzilmasi - bu kompyuterda ma'lumotlarni samarali tarzda olish va o'zgartirish uchun ularni tashkil etish va saqlashning ma'lum bir usuli. Ayniqsa, ma'lumotlar tuzilmasi ma'lumot qiymatlarining to'plami, ular orasidagi munosabatlar va ma'lumotlarga qo'llanilishi mumkin bo'lgan funksiyalar yoki operatsiyalardir.

B - Boshlang'ich, A - Ilg'or

B Bog'langan ro'yxat
B Ikki marta bog'langan ro'yxat
B Navbat
B Stek
B Hash jadvali
B Heap - maksimal va minimal heap versiyalari
B Ustuvor navbat
A Trie
A Daraxt
- A Ikkilik qidiruv daraxt
- A AVL daraxt
- A Qizil-qora daraxt
- A Segment daraxt - min/max/sum diapazon so'rovlari bilan misollar
- A Fenwick daraxt (ikkilik indeksli daraxt)
A Graf (yo'naltirilgan hamda yo'naltirilmagan)
A Ajratilgan to'plam - union-find ma'lumotlar strukturasi yoki merge-find to'plami
A Bloom filtri
A LRU keshi - Eng kam ishlatilgan (LRU) keshi

Algoritmlar

Algoritm muammolar sinfini qanday hal qilishning aniq spetsifikatsiyasi. Bu operatsiyalar ketma-ketligini aniqlaydigan qoidalar to'plami.

B - Boshlang'ich, A - Ilg'or

Mavzu bo'yicha algoritmlar

Matematika
- B Bit manipulatsiyasi - bitlarni qo'yish/olish/yangilash/tozalash, ikkilikka ko'paytirish/bo'lish, manfiy qilish va hokazo.
- B Ikkilik suzuvchi nuqta - suzuvchi nuqtali sonlarning ikkilik tasviri.
- B Faktorial
- B Fibonachchi raqam - klassik va yopiq shakldagi versiyalar
- B Asosiy omillar - tub omillarni topish va ularni Xardi-Ramanujan teoremasi yordamida sanash
- B Birlamchilik testi (sinov bo'linish usuli)
- B Evklid algoritmi - eng katta umumiy bo'luvchini (EKUB) hisoblash
- B Eng kichik umumiy karrali (EKUK)
- B Eratosfen elagi - berilgan chegaragacha barcha tub sonlarni topish
- B Ikkining darajasimi - raqamning ikkining darajasi ekanligini tekshirish (sodda va bitli algoritmlar)
- B Paskal uchburchagi
- B Kompleks sonlar - kompleks sonlar va ular bilan asosiy amallar
- B Radian & Daraja - radianlarni darajaga va orqaga aylantirish
- B Tez ko'tarish
- B Horner metodi - polinomlarni baholash
- B Matritsalar - matritsalar va asosiy matritsa operatsiyalari (ko'paytirish, transpozitsiya va boshqalar).
- B Evklid masofasi - ikki nuqta/vektor/matritsa orasidagi masofa
- A Butun sonlarni bo'lish
- A Kvadrat ildiz - Nyuton metodi
- A Liu Hui π algoritmi - N-gonlarga asoslangan π ning taxminiy hisoblari
- A Diskret Furye transformatsiyasi - vaqt funksiyasini (signalni) uni tashkil etuvchi chastotalarga ajratish
Sets
- B Karteziya maxsuloti - bir nechta to'plamlarning ko'paytmasi
- B Fisher–Yates Shuffle - chekli ketma-ketlikni tasodifiy almashtirish
- A Power Set - to'plamning barcha kichik to'plamlari (bitwise, backtracking va kaskadli echimlar)
- A Permutatsiyalar (takroriyalash bilan va takroriyalashsiz)
- A Kombinatsiyalar (takroriyalash bilan va takroriyalashsiz)
- A Eng uzun umumiy ketma-ketlik (LCS)
- A Eng uzun ortib boruvchi ketma-ketlik
- A Eng qisqa umumiy ketma-ketlik (SCS)
- A Knapsack muammosi - "0/1" va "Bir-biriga bog'lanmagan"
- A Maksimal kichik massiv - Toʻliq kuch va dinamik dasturlash (Kadane usuli) versiyalari
- A Kombinatsiya yig'indisi - ma'lum summani tashkil etuvchi barcha kombinatsiyalarni topish
Stringlar
- B Hamming masofasi - belgilarning bir-biridan farq qiladigan pozitsiyalar soni
- B Palindrom - satrning teskari tomoni ham bir xil ekanligini tekshirish
- A Levenshtein masofasi - ikki ketma-ketlik o'rtasidagi minimal tahrirlash masofasi
- A Knuth–Morris–Pratt Algoritmi (KMP Algoritmi) - kichik qatorlarni qidirish (mosh keluvchi naqshni qidirish)
- A Z Algoritmi - kichik qatorlarni qidirish (mosh keluvchi naqshni qidirish)
- A Rabin Karp Algoritmi - kichik qatorlarni qidirish
- A Eng uzun umumiy kichik matn
- A Regulyar ifoda moslashuvi (RegEx)
Qidiruvlar
- B Linear qidirish
- B Jump qidirish (yoki Blok qidirish) - saralangan qatorda qidirish
- B Ikkilik qidirish - saralangan qatorda qidirish
- B Interpolatsiya qidirish - bir tekis taqsimlangan saralangan qatorda qidirish
Tartiblash
- B Pufakcha tartiblash
- B Tanlash tartibi
- B Kiritish tartibi
- B Heap tartibi
- B Birlashtirish tartibi
- B Tezkor saralash - joyida va joyida bo'lmagan amalga oshirish
- B Shell tartiblash
- B Sanash tartibi
- B Radiksli tartiblash
- B Bucket tartiblash
Bog'langan ro'yhatlar
- B To'g'ri traversal
- B Teskari traversal
Daraxtlar
- B Birinchi-pastga qarab qidirish (Depth-First Search)
- B Birinchi-yonga qarab qidirish (Breadth-First Search)
Grafiklar
- B Birinchi-pastga qarab qidirish (Depth-First Search)
- B Birinchi-yonga qarab qidirish (Breadth-First Search)
- B Kruskal Algoritmi - og'irlikdagi yo'naltirilmagan grafik uchun Minimal kengayuvchi daraxtni (MST) topish
- A Dijkstra Algoritmi - grafikning bir cho'qqisidan qolgan barcha nuqtalarga eng qisqa yo'llarni topish
- A Bellman-Ford Algoritmi - grafikning bir cho'qqisidan qolgan barcha nuqtalarga eng qisqa yo'llarni topish
- A Floyd-Warshall Algoritmi - grafikning barcha uchlari orasidagi eng qisqa masofalarni topish
- A Siklni aniqlash - yo'naltirilgan va yo'naltirilmagan grafiklar uchun (DFS va Disjoint Set-ga asoslangan versiyalar)
- A Prim Algoritmi - og'irlikdagi yo'naltirilmagan grafik uchun Minimal kengayuvchi daraxtni (MST) topish
- A Topologik saralash - DFS metodi
- A Artikulyatsiya nuqtalari - Tarjan algoritmi (DFS asosida)
- A Ko'priklar - DFS asosidagi algoritm
- A Eyler yo'li va Eyler sxemasi - Fleury algoritmi - Har bir chekkaga bir marta tashrif buyurish
- A Gamilton sikli - Har bir cho'qqiga bir marta tashrif buyurish
- A Kuchli bog'langan komponentlar - Kosaraju algoritmi
- A Sayohatchi sotuvchi muammosi - har bir shaharga tashrif buyuradigan va kelib chiqqan shaharga qaytib keladigan eng qisqa yo'l
Kriptografiya
- B Polynomial Hash - polinomga asoslangan hash funktsiyasi
- B Rail Fence Cipher - xabarlarni kodlash uchun transpozitsiya shifrlash algoritmi
- B Caesar Cipher - oddiy almashtirish shifridir
- B Hill Cipher - chiziqli algebraga asoslangan almashtirish shifri
Machine Learning
- B NanoNeuron - Mashinalar aslida qanday o'rganishi mumkinligini ko'rsatadigan 7 ta oddiy JS funksiyasi (forward/backward tarqalish)
- B k-NN - eng yaqin qo'shnilarni tasniflash algoritmi
- B k-Means - k-Means kalsterlash algoritmi
Tasvirga ishlov berish
- B Seam Carving - kontentga moslashuvchan rasm o'lchamini o'zgartirish algoritmi
Statistikalar
- B Weighted Random - elementlarning og'irligi asosida ro'yxatdan tasodifiy elementni tanlash
Evolyutsion algoritmlar
- A Genetik algoritm - avtoturargohni o'rgatish uchun genetik algoritm qanday qo'llanilishiga misol.
Kategoriyasiz
- B Xanoy minorasi
- B Kvadrat matritsaning aylanishi - joyidagi algoritm
- B Sakrash o'yini - orqaga qaytish, dinamik dasturlash (yuqoridan pastga + pastdan yuqoriga) va ochko'z misollar
- B Noyob yo'llar - orqaga qaytish, dinamik dasturlash va Paskal uchburchagiga asoslangan misolla
- B Yomg'ir teraslari - yomg'ir suvini ushlab turish muammosi (dinamik dasturlash va qo'pol kuch versiyalari)
- B Rekursiv zinapoya - yuqoriga chiqish yo'llari sonini hisoblash (4 ta echim)
- B Aksiyalarni sotib olish va sotish uchun eng yaxshi vaqt - bo'linib-zabt etish va bir marta o'tish misollari
- A N-Queens Muommosi
- A Ritsar sayohati

Paradigma bo'yicha algoritmlar

Algorithmic paradigm - bu algoritmlar sinfini loyihalashtirishga asos bo'lib xizmat qiladigan umumiy usul yoki yondashuv. Bu algoritm tushunchasidan yuqori darajadagi abstraktsiya bo'lib, algoritm kompyuter dasturi tushunchasidan yuqori darajadagi abstraktsiya bo'lgani kabi.

Brute Force - barcha imkoniyatlarni ko'rib chiqib va eng yaxshi echimni tanlash
- B Chiziqli qidirish
- B Yomg'irli teraslar - yomg'ir suvini to'plash muammosi
- B Rekursiv zinapoya - cho'qqiga chiqish yo'llari sonini hisoblash
- A Maksimal kichik massiv
- A Sayohatchi sotuvchi muammosi - har bir shaharga tashrif buyuradigan va kelib chiqqan shaharga qaytib keladigan eng qisqa yo'l
- A Diskret Furye transformatsiyasi - vaqt funksiyasini (signalni) uni tashkil etuvchi chastotalarga ajratish
Greedy - kelajakni o'ylamasdan, hozirgi vaqtda eng yaxshi variantni tanlash
- B Sakrash o'yini
- A Bog'lanmagan yukxalta muammosi
- A Dijkstra Algoritmi - grafikning bir cho'qqisidan qolgan barcha nuqtalarga eng qisqa yo'llarni topish
- A Prim Algoritmi - og'irlikdagi yo'naltirilmagan grafik uchun Minimal kengayuvchi daraxtni (MST) topish
- A Kruskal Algoritmi - og'irlikdagi yo'naltirilmagan grafik uchun Minimal kengayuvchi daraxtni (MST) topish
Divide and Conquer - muammoni kichikroq qismlarga bo'lib va keyin bu qismlarni hal qilish
- B Ikkilik qidiruv
- B Xanoy minorasi
- B Paskal uchburchagi
- B Evklid Algoritmi - eng katta umumiy bo'luvchini (EKUB) hisoblash
- B Birlashtirish tartibi
- B Tezkor saralash
- B Birinchi-pastga qarab qidirish daraxti (DFS)
- B Birinchi-pastga qarab qidirish grafigi (DFS)
- B Matritsalar - turli shakldagi matritsalarni hosil qilish va kesib o'tish
- B Sakrash o'yini
- B Tez ko'tarish
- B Aksiyalarni sotib olish va sotish uchun eng yaxshi vaqt - bo'linib-zabt etish va bir marta o'tish misollari
- A Permutatsiyalar (takroriyalash bilan va takroriyalashsiz)
- A Kombinatsiyalar (takroriyalash bilan va takroriyalashsiz)
- A Maksimal kichik massiv
Dinamik dasturlash - ilgari topilgan kichik yechimlar yordamida yechim yaratish
- B Fibonachchi raqam
- B Sakrash o'yini
- B Noyob yo'llar
- B Yomg'ir teraslari - yomg'ir suvini to'plash muammosi
- B Recursive Staircase - count the number of ways to reach to the top
- B Seam Carving - kontentga moslashuvchan rasm o'lchamini o'zgartirish algoritmi
- A Levenshtein masofasi - ikki ketma-ketlik o'rtasidagi minimal tahrirlash masofasi
- A Eng uzun umumiy ketma-ketlik (LCS)
- A Eng uzun umumiy kichik matn
- A Eng uzun ortib boruvchi ketma-ketlik
- A Eng qisqa umumiy ketma-ketlik
- A 0/1 Knapsak muommosi
- A Butun sonlarni bo'lish
- A Maksimal kichik massiv
- A Bellman-Ford Algoritmi - grafikning bir cho'qqisidan qolgan barcha nuqtalarga eng qisqa yo'llarni topish
- A Floyd-Warshall Algoritmi -grafikning barcha uchlari orasidagi eng qisqa masofalarni topish
- A Regulyar ifoda moslashuvi
Backtracking - brute forcega o'xshab, barcha mumkin bo'lgan yechimlarni generatsiya qilishga harakat qiladi, lekin har safar keyingi yechimni yaratganingizda, yechim barcha shartlarga javob beradimi yoki yo'qligini tekshirasiz va shundan keyingina keyingi yechimlarni ishlab chiqarishni davom ettirasiz. Aks holda, orqaga qaytib, yechim topishning boshqa yo'liga o'tasiz. Odatda state-space ning DFS-qidiruvi ishlatiladi.
- B Sakrash o'yini
- B Noyob yo'llar
- B Power Set - to'plamning barcha kichik to'plamlari
- A Gamilton sikli - Har bir cho'qqiga bir marta tashrif buyurish
- A N-Queens muommosi
- A Ritsar sayohati
- A Kombinatsiya yig'indisi - ma'lum summani tashkil etuvchi barcha kombinatsiyalarni topish
Branch & Bound - shu paytgacha topilgan eng arzon echimdan kattaroq xarajatlarga ega qisman echimlarni bekor qilish uchun, backtracking qidiruvining har bir bosqichida topilgan eng arzon echimni eslab qoling va shu paytgacha topilgan eng arzon yechim narxidan muammoni eng kam xarajatli yechim narxining past chegarasi sifatida foydalaning. Odatda state-space daraxtining DFS o'tishi bilan birgalikda BFS traversal qo'llaniladi.

Ushbu repozitoriyadan qanday foydalanish kerak

Barcha dependensiylarni o'rnating

npm install

ESLint ni ishga tushiring

Kod sifatini tekshirish uchun ESLint ni ishga tushirishingiz mumkin.

npm run lint

Barcha testlarni ishga tushuring

npm test

Testlarni nom bo'yicha ishga tushirish

npm test -- 'LinkedList'

Muammolarni bartaraf qilish (Troubleshooting)

Agar linting yoki sinov muvaffaqiyatsiz bo'lsa, node_modules papkasini o'chirib, npm paketlarini qayta o'rnatishga harakat qiling:

rm -rf ./node_modules
npm i

Shuningdek, to'g'ri Node versiyasidan foydalanayotganingizga ishonch hosil qiling (>=16). Agar Node versiyasini boshqarish uchun nvm dan foydalanayotgan bo'lsangiz, loyihaning ildiz papkasidan nvm use ni ishga tushiring va to'g'ri versiya tanlanadi.

O'yin maydoni (Playground)

./src/playground/playground.js faylida ma'lumotlar strukturalari va algoritmlar bilan o'ynashingiz, ./src/playground/test/playground.test.js faylida esa ular uchun testlar yozishingiz mumkin.

Shundan so'ng, playground kodingiz kutilgandek ishlashini tekshirish uchun quyidagi buyruqni ishga tushirishingiz kifoya:

npm test -- 'playground'

Foydali ma'lumotlar

Manbalar

Big O Notation

Big O notation algoritmlarni kirish hajmi oshgani sayin ularning ishlash vaqti yoki bo'sh joy talablari qanday o'sishiga qarab tasniflash uchun ishlatiladi. Quyidagi jadvalda siz Big O notatsiyasida ko'rsatilgan algoritmlarning o'sishining eng keng tarqalgan tartiblarini topishingiz mumkin.

Manba: Big O Cheat Sheet.

Quyida eng ko'p qo'llaniladigan Big O notatsiyalarining ro'yxati va ularning kirish ma'lumotlarining turli o'lchamlariga nisbatan ishlashini taqqoslash keltirilgan.

Big O Notatsiya	Turi	10 ta element uchun hisob-kitoblar	100 ta element uchun hisob-kitoblar	1000 ta element uchun hisob-kitoblar
O(1)	O'zgarmas	1	1	1
O(log N)	Logarifmik	3	6	9
O(N)	Chiziqli	10	100	1000
O(N log N)	n log(n)	30	600	9000
O(N^2)	Kvadrat	100	10000	1000000
O(2^N)	Eksponensial	1024	1.26e+29	1.07e+301
O(N!)	Faktorial	3628800	9.3e+157	4.02e+2567

Ma'lumotlar tuzilmalarining operatsiyalari murakkabligi

Ma'lumotlar tuzilmalari	Kirish	Qidirish	Kiritish	O'chirish	Izohlar
Massiv	1	n	n	n
Stak	n	n	1	1
Navbat	n	n	1	1
Bog'langan ro'yhat	n	n	1	n
Hash jadval	-	n	n	n	Mukammal xash funksiyasi bo'lsa, xarajatlar O (1) bo'ladi.
Ikkilik qidiruv daraxti	n	n	n	n	Balanslangan daraxt narxida O(log(n)) bo'ladi.
B-daraxti	log(n)	log(n)	log(n)	log(n)
Qizil-qora daraxt	log(n)	log(n)	log(n)	log(n)
AVL Daraxt	log(n)	log(n)	log(n)	log(n)
Bloom filtri	-	1	1	-	Qidiruv paytida noto'g'ri pozitivlar bo'lishi mumkin

Massivlarni saralash algoritmlarining murakkabligi

Nomi	Eng yaxshi	O'rta	Eng yomon	Xotira	Barqaror	Izohlar
Pufakcha tartiblash	n	n<sup>2</sup>	n<sup>2</sup>	1	Ha
Kiritish tartibi	n	n<sup>2</sup>	n<sup>2</sup>	1	Ha
Tanlash tartibi	n<sup>2</sup>	n<sup>2</sup>	n<sup>2</sup>	1	Yo'q
Heap tartibi	n log(n)	n log(n)	n log(n)	1	Yo'q
Birlashtirish tartibi	n log(n)	n log(n)	n log(n)	n	Ha
Tezkor saralash	n log(n)	n log(n)	n<sup>2</sup>	log(n)	Yo'q	Tezkor saralash odatda O(log(n)) stek maydoni bilan joyida amalga oshiriladi
Shell tartiblash	n log(n)	depends on gap sequence	n (log(n))<sup>2</sup>	1	Yo'q
Sanash tartibi	n + r	n + r	n + r	n + r	Ha	r - massivdagi eng katta raqam
Radiksli tartiblash	n * k	n * k	n * k	n + k	Ha	k - eng uzun kalitning uzunligi

Loyihani qo'llab-quvvatlovchilar

Siz ushbu loyihani ❤️️ GitHub yoki ❤️️ Patreon orqali qo'llab-quvvatlashingiz mumkin.

Ushbu loyihani qo'llab-quvvatlagan odamlar ∑ = 1

Muallif

@trekhleb

A few more projects and articles about JavaScript and algorithms on trekhleb.dev