🇺🇦 უკრაინას თავს ესხმის რუსეთის არმია. მოკლულია მშვიდობიანი მოსახლეობა. ბომბავენ საცხოვრებელ უბნებს.
- დაეხმარეთ უკრაინას:
- მეტი ინფორმაცია war.ukraine.ua და უკრაინის საგარეო საქმეთა სამინისტრო
🇬🇪 საქართველოს 20% ოკუპირებულია რუსეთის არმიის მიერ.
- მეტი ინფორმაცია wikipedia
ეს საცავი(რეპოზიტორი) შეიცავს JavaScript-ზე დაფუძნებულ მაგალითებს ალგორითმებისა და მონაცემთა სტრუქტურებზე.
თითოეულ ალგორითმსა და მონაცემთა სტრუქტურას აქვს საკუთარი ცალკე README ფაილი, ახსნა-განმარტებებითა და ბმულებით შემდგომი კითხვისთვის (მათ შორის YouTube ვიდეოების ბმულებით).
წაიკითხეთ სხვა ენებზე: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türkçe, Italiano, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch, Uzbek, עברית, ქართული
"მონაცემთა სტრუქტურა" არის მონაცემების(ინფორმაციის) ორგანიზებისა და შენახვის კონკრეტული გზა კომპიუტერში, იმგვარად რომ შეიძლებოდეს ეფექტურად წვდომა და მოდიფიცირება. ანუ, "მონაცემთა სტრუქტურა" არის მონაცემების(ინფორმაციის) ერთეულების კოლექცია, მათ შორის კავშირები, და ფუნქციები, ოპერაციები აღნიშნულ მონაცემებზე სამუშაოდ.
გახსოვდეთ, რომ თითოეულ მონაცემს აქვს საკუთარი დადებითი და უარყოფითი მხარეები. მეტი ყურადღება უნდა მიაქციოთ იმას, თუ რატომ ირჩევთ კონკრეტულ მონაცემთა სტრუქტურას, ვიდრე იმას, თუ როგორ განვახორციელოთ(დავაიმპლემენტიროთ) იგი.
მ - მარტივი, რ - რთული
მბმული სიარორმხრივად ბმული სიამრიგიმსტეკიმჰეშ-ცხრილიმგროვა - max და min heap ვერსიებიმპრიორიტეტული რიგირTrieრხერორობითი ძიების ხერAVL ხერწითელ-შავი ხერსეგმენტირებული ხე - min/max/sum დიაპაზონის მოთხოვნების მაგალითებითრფენვიკის ხე (ორობითი ინდექსირებული ხე)
რგრაფი (როგორც მიმართული, ასევე არამიმართული)რგანცალკავებული სეტი - union–find მონაცემთა სტრუქტურა ან merge–find სეტირBloom FilterრLRU ქეში - ბოლოს გამოყენებული (LRU) ქეში
ალგორითმი არის ცალსახა გზა(წესები) იმისა, თუ როგორ გადავჭრათ კონკრეტული პრობლემა. ეს არის წესების სიმრავლე, რომელიც ზუსტად განსაზღვრავს ოპერაციების თანმიმდევრობას.(მაგალითად საჭმლის მომზადების რეცეპტი შეიძლება ჩაითვალოს როგორც ალგორითმი)
მ - მარტივი, რ - რთული
- მათემატიკა
რბიტების მანიპულაცია - set/get/update/clear ბიტები, გამრავლება/გაყოფა ორზე, უარყოფითად გადაქცევა და სხვა.რორობითი მცურავ წერტილიანი რიცხვი - მცურავი წერტილიანი რიცხვების ორობითი წარმოდგენა.რფაქტორიალირფიბონაჩის რიცხვი - კლასიკური და დახურული ფორმის ვერსიებირმარტივი რიცხვები - მარტივი რიცხვების პოვნა და მათი დათვლა ჰარდი-რამანუჯანის თეორემის გამოყენებითრმარტივობის ტესტი (საცდელი გაყოფის მეთოდი)რევკლიდეს ალგორითმი - უდიდესი საერთო გამყოფის (უსგ-GCD) გამოთვლარუმცირესი საერთო ჯერადი (უსჯ-LCM)რერატოსთენეს საცერი - ყველა მარტივი რიცხვის პოვნა ნებისმიერ მოცემულ რიცხვამდერარის ორის ხარისხი - შეამოწმეთ არის თუ არა რიცხვი ორის ხარისხირპასკალის სამკუთხედირკომპლექსური რიცხვი - კომპლექსური რიცხვები და ძირითადი ოპერაციები მათზერრადიანი და გრადუსი - რადიანიდან გრადუსში გადაყვანა და პირიქით გრადუსიდან რადიანში გადაყვანარსწრაფი ხარისხში აყვანარჰორნერის მეთოდი - პოლინომის შეფასებარმატრიცები - მატრიცები და ძირითადი მატრიცული ოპერაციები (გამრავლება, ტრანსპოზიცია და სხვა)რევკლიდური მანძილი - მანძილი ორ წერტილს/ვექტორს/მატრიცას შორისმმთელი რიცხვის დანაწილებამკვადრატული ფესვი - ნიუტონის მეთოდიმლიუ ჰუის π ალგორითმი - მიახლოებითი π გამოთვლებიმდისკრეტული ფურიეს ტრანსფორმაცია - დროის ფუნქციის (სიგნალის) დეკომპოზიცია მის შემადგენელ სიხშირეებად
- სიმრავლეები
რდეკარტის ნამრავლი - სიმრავლეების ნამრავლირფიშერ-იეიტსის შემთხვევითი გადანაცვლება - სასრული მიმდევრობის შემთხვევითი გადანაცვლებამსიმრავლეების სიმძლავვრე - სიმრავლის ყველა ქვესიმრავლე (ორობითი ალგორითმები და კასკადური ამონახსნები)მპერმუტაციები (გამეორებებით და გამეორებების გარეშე)მკომბინაციები (გამეორებებით და გამეორებების გარეშე)მუგრძესი საერთო ქვემიმდევრობა (LCS)მუგრძესი მზარდი ქვემიმდევრობამუმოკლესი საერთო სუპერმიმდევრობა (SCS)მზურგჩანთის პრობლემა - "0/1" და "უსაზღვრო" ვარიანტებიმმაქსიმალური ქვემასივი - "სრული გადარჩევა" და "დინამიური პროგრამირების" (კადანეს) ვერსიებიმკომბინაციების ჯამი - იპოვეთ ყველა კომბინაცია, რომელიც ქმნის კონკრეტულ ჯამს
- სტრიქონები
რჰამინგის მანძილი - განსხვავებული სიმბოლოების რაოდენობარპალინდრომი - შეამოწმეთ არის თუ არა სტრიქონი სარკისებულიმლევენშტეინის მანძილი - მინიმალური განსხვავება ორ მიმდევრობას შორისმკნუთ-მორის-პრატის ალგორითმი (KMP ალგორითმი) - ქვესტრიქონის ძიება (მსგავსების მოძიება)მZ ალგორითმი - ქვესტრიქონის ძიება (მსგავსების მოძიება)მრაბინ-კარპის ალგორითმი - ქვესტრიქონის ძიებამუგრძესი საერთო ქვესტრიქონიმრეგულარული გამოხატვითი დამთხვევა
- ძიება
რწრფივი ძიებარნახტომებით ძიება - ძიება დალაგებულ მასივშირორობითი ძიება - ძიება დალაგებულ მასივშირინტერპოლაციით ძიება - ძიება ერთგვაროვნად განაწილებულ დალაგებულ მასივში
- დახარისხება(დალაგება)
რბუშტულასებრი დალაგებარამორჩევით დალაგებარჩასმის დალაგებარგროვით დალაგებარშერწყმით დალაგებარსწრაფი დალაგება - in-place და non-in-place რეალიზაციებირშელ დალაგებარდათვლის დალაგებარრადიქს დალაგებარვედროს დალაგება
- ბმული სიები
- ხეები
რსიღრმეში ძიება (DFS)რსიგანეში ძიება (BFS)
- გრაფები
რსიღრმეში ძიება (DFS)რსიგანეში ძიება (BFS)რკრუსკალის ალგორითმი - მინიმალური დამფარავი ხის (MST) პოვნა შეწონილი არამიმართული გრაფისთვისმდეიქსტრას ალგორითმი - უმოკლესი გზების პოვნა გრაფის ყველა წვეროზე ერთი წვეროდანმბელმან-ფორდის ალგორითმი - უმოკლესი გზების პოვნა გრაფის ყველა წვეროზე ერთი წვეროდანმფლოიდ-ვარშალის ალგორითმი - იპოვეთ უმოკლესი გზები ყველა წვეროს წყვილს შორისმციკლის გამოვლენა - როგორც მიმართული, ასევე არამიმართული გრაფებისთვის (DFS და Disjoint Set-ზე დაფუძნებული ვერსიები)მპრიმის ალგორითმი - მინიმალური დამფარავი ხის (MST) პოვნა შეწონილი არამიმართული გრაფისთვისმტოპოლოგიური დალაგება - DFS მეთოდიმარტიკულაციის წერტილები - ტარჯანის ალგორითმი (DFS-ზე დაფუძნებული)მხიდები - DFS-ზე დაფუძნებული ალგორითმიმეილერის გზა და ეილერის წრე - ფლერის ალგორითმი - ეწვიეთ ყველა კიდეს ზუსტად ერთხელმჰამილტონის ციკლი - ეწვიეთ ყველა წვეროს ზუსტად ერთხელმძლიერად დაკავშირებული კომპონენტები - კოსარაჯუს ალგორითმიმმოგზაური ვაჭრის პრობლემა - უმოკლესი მარშრუტი, რომელითაც მოივლი ყველა ქალაქს და ბრუნდები საწყის ქალაქში
- კრიპტოგრაფია
რპოლინომური ჰეში - პოლინომზე დაფუძნებული მოძრავი ჰეშ ფუნქციარრელსის ღობის შიფრი - შეტყობინებების დაშიფვრისს ტრანსპოზიციის შიფრის ალგორითმირკეისრის შიფრი - მარტივი ჩანაცვლების შიფრირჰილის შიფრი - წრფივ ალგებრაზე დაფუძნებული ჩანაცვლების შიფრი
- მანქანური სწავლება
რNanoNeuron - 7 მარტივი JS ფუნქცია, რომელიც აჩვენებს, თუ როგორ შეიძლება მანქანებმა რეალურად ისწავლონ (წინ და უკან გავრცელება)რk-NN - k-უახლოესი მეზობლის კლასიფიკაციის ალგორითმირk-Means - k-Means კლასტერიზაციის ალგორითმი
- გამოსახულების(სურათის) დამუშავება
რSeam Carving - სურათის ზომის შეცვლის ალგორითმი
- სტატისტიკა
რშეწონილი შემთხვევითი შერჩევა - აირჩიეთ შემთხვევითი ელემენტი სიიდან ელემენტების წონების საფუძველზე
- თვით განვითარებადი(ევოლუციური) ალგორითმები
მგენეტიკური ალგორითმი - მაგალითი იმისა, თუ როგორ შეიძლება გენეტიკური ალგორითმი გამოყენებულ იქნას მანქანების აუტომატური პარკირების ტრენინგისთვის
- სხვა(კატეგორიის გარეშე)
რჰანოის კოშკირკვადრატული მატრიცის შებრუნება - in-place ალგორითმირთამაში Jump - უკუგაყოლა, დინამიური პროგრამირება (ზემოდან ქვემოთ + ქვემოდან ზემოთ) და ხარბი მაგალითებირუნიკალური გზების ამოცანა - უკუგაყოლა, დინამიური პროგრამირება და პასკალის სამკუთხედზე დაფუძნებული მაგალითებირწვიმის ტერასები - წვიმის წყლის დაჭერის პრობლემა (დინამიური პროგრამირებისა და უხეში ძალის ვერსიები)რრეკურსიული კიბე - მწვერვალზე მისასვლელი გზების რაოდენობა (4 ამონახსნი)რსაუკეთესო დრო აქციების შესაძენად და გასაყიდად - დაყავი და იბატონე და ერთგზის მაგალითებირვალიდური ფრჩხილები - შეამოწმეთ აქვს თუ არა სტრიქონს ვალიდური ფრჩხილები (სტეკის გამოყენებით)მN-დედოფლის პრობლემამმხედრის ტური
ალგორითმული პარადიგმა არის გენერიკული მეთოდი ან მიდგომა, რომელიც ეფუძნება ალგორითმების კლასის დიზაინს. ეს არის აბსტრაქცია, რომელიც უფრო მაღალია, ვიდრე ალგორითმის კონცეფცია, ისევე როგორც ალგორითმი არის აბსტრაქცია, რომელიც უფრო მაღალია, ვიდრე კომპიუტერული პროგრამა.
- სრული გადარჩევა - ყველა შესაძლებლობას(შესაძლო ვარიანტის) შემოწმება და აირჩიეთ საუკეთესო ამონახსნი
რწრფივი ძიებარწვიმის ტერასები - წვიმის წყლის დაჭერის პრობლემარრეკურსიული კიბე - მწვერვალზე მისასვლელი გზების რაოდენობამმაქსიმალური ქვემასივიმმოგზაური ვაჭრის პრობლემა - უმოკლესი მარშრუტი, რომელითაც მოივლი ყველა ქალაქს და ბრუნდები საწყის ქალაქშიმდისკრეტული ფურიეს ტრანსფორმაცია - დროის ფუნქციის (სიგნალის) დეკომპოზიცია მის შემადგენელ სიხშირეებად
- ხარბი - აირჩიეთ საუკეთესო ვარიანტი მიმდინარე დროს, მომავლის გათვალისწინების გარეშე
რთამაში Jumpმზურგჩანთის პრობლემამდეიქსტრას ალგორითმი - უმოკლესი გზის პოვნა გრაფის ყველა წვეროზემპრიმის ალგორითმი - მინიმალური დამფარავი ხის (MST) პოვნა შეწონილი არამიმართული გრაფისთვისმკრუსკალის ალგორითმი - მინიმალური დამფარავი ხის (MST) პოვნა შეწონილი არამიმართული გრაფისთვის
- დაყავი და იბატონე - გაყავით პრობლემა პატარა ნაწილებად და შემდეგ ამოხსენით ეს ნაწილები
რორობითი ძიებარჰანოის კოშკირპასკალის სამკუთხედირევკლიდეს ალგორითმი - უდიდესი საერთო გამყოფის (უსგ-GCD) გამოთვლარშერწყმითი დალაგებარსწრაფი დალაგებარხის სიღმეში ძიება (DFS)რგრაფის სიღმეში ძიება (DFS)რმატრიცები - სხვადასხვა ფორმის მატრიცების გენერირება და ტრასირებართამაში Jumpრსწრაფი ხარისხში აყვანარსაუკეთესო დრო აქციების შესაძენად და გასაყიდად - დაყავი და იბატონემპერმუტაციები (გამეორებებით და გამეორებების გარეშე)მკომბინაციები (გამეორებებით და გამეორებების გარეშე)მმაქსიმალური ქვემასივი
- დინამიური პროგრამირება - ააგეთ ამონახსნი ადრე ნაპოვნი ქვე-ამონახსნების გამოყენებით
რფიბონაჩის რიცხვირთამაში Jumpრუნიკალური გზების ამოცანარწვიმის ტერასები - წვიმის წყლის დაჭერის პრობლემარრეკურსიული კიბე - მწვერვალზე მისასვლელი გზების რაოდენობარSeam Carving - სურათის ზომის შეცვლის ალგორითმიმლევენშტეინის მანძილი - მინიმალური განსხვავება ორ მიმდევრობას შორისმუგრძესი საერთო ქვემიმდევრობა (LCS)მუგრძესი საერთო ქვესტრიქონიმუგრძესი მზარდი ქვემიმდევრობამუმოკლესი საერთო სუპერმიმდევრობამ0/1 ზურგჩანთის პრობლემამმთელი რიცხვის დანაწილებამმაქსიმალური ქვემასივიმბელმან-ფორდის ალგორითმი - უმოკლესი გზის პოვნა გრაფის ყველა წვეროზემფლოიდ-ვარშალის ალგორითმი - იპოვეთ უმოკლესი გზები ყველა წვეროს წყვილს შორისმრეგულარული გამოსახულების დამთხვევა
- უკუსვლითი(backtracking) - სრული გადარჩევის მსგავსად, შეეცადეთ დააგენერიროთ ყველა შესაძლო ამონახსნი, მაგრამ ყოველ ჯერზე, როცა აგენერირებთ შემდეგ ამონახსნს, შეამოწმეთ თუ აკმაყოფილებს ყველა პირობას და მხოლოდ მაშინ განაგრძობთ შემდგომი ამონახსნების გენერირება. წინააღმდეგ შემთხვევაში, უკან დაბრუნდით და გადადით სხვა გზაზე. ჩვეულებრივ გამოიყენება სიღრმეში ძებნით(DFS) გადავლა.
რთამაში Jumpრუნიკალური გზების ამოცანარსიმრავლეების სიმძლავვრე - სიმრავლის ყველა ქვესიმრავლე (ორობითი ალგორითმები და კასკადური ამონახსნები)მჰამილტონის ციკლი - ეწვიეთ ყველა წვეროს ზუსტად ერთხელმN-დედოფლის პრობლემამმხედრის ტურიმკომბინაციის ჯამი - იპოვეთ ყველა კომბინაცია, რომელიც ქმნის კონკრეტულ ჯამს
ინსტალაცია
npm installგაუშვით ESLint
შეიძლება გსურდეთ მისი გაშვება კოდის ხარისხის შესამოწმებლად.
npm run lintტესტების გაშვება
npm testკონკრეტული ტესტის გაშვება (სახელით)
npm test -- 'LinkedList'Troubleshooting
თუ linting ან testing არ მუშაობს, შეეცადეთ წაშალოთ node_modules ფოლდერი და ხელახლა დააინსტალიროთ npm პაკეტები:
rm -rf ./node_modules
npm iასევე, დარწმუნდით, რომ იყენებთ სწორ Node ვერსიას (>=16). თუ იყენებთ nvm Node ვერსიის მართვისთვის, შეგიძლიათ გაუშვათ nvm use პროექტის root ფოლდერიდან და სწორი ვერსია აირჩევა ავტომატურად.
Playground
შეგიძლიათ წაეთამაშოთ მონაცემთა სტრუქტურებითა და ალგორითმებით ./src/playground/playground.js ფაილში და დაწეროთ
ტესტები ./src/playground/__test__/playground.test.js-ში.
შემდეგ, უბრალოდ, გაუშვით შემდეგი ბრძანება, რათა შეამოწმოთ მუშაობს თუ არა თქვენი Playground, როგორც მოსალოდნელია:
npm test -- 'playground'Big O აღნიშვნა გამოიყენება ალგორითმების კლასიფიცირებისთვის, თუ როგორ იზრდება მათი გაშვების დრო ან დაკავებული მეხსიერება, შემავალი მონაცემების ზომის ზრდასთან ერთად. ქვემოთ მოცემულ დიაგრამაზე შეგიძლიათ იპოვოთ ყველაზე გავრცელებული ალგორითმების ზრდის რიგები, რომლებიც მითითებულია Big O აღნიშვნით.
წყარო: Big O Cheat Sheet.
ქვემოთ მოცემულია ზოგიერთი ყველაზე გამოყენებული Big O აღნიშვნების სია და მათი შესრულების შედარება შემავალი მონაცემების სხვადასხვა ზომებთან.
| Big O აღნიშვნა | ტიპი | 10 ელემენტისთვის | 100 ელემენტისთვის | 1000 ელემენტისთვის |
|---|---|---|---|---|
| O(1) | მუდმივი | 1 | 1 | 1 |
| O(log N) | ლოგარითმული | 3 | 6 | 9 |
| O(N) | წრფივი | 10 | 100 | 1000 |
| O(N log N) | 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 |
| მონაცემთა სტრუქტურა | წვდომა | ძიება | ჩასმა | წაშლა | კომენტარები |
|---|---|---|---|---|---|
| მასივი | 1 | n | n | n | |
| სტეკი | n | n | 1 | 1 | |
| რიგი | n | n | 1 | 1 | |
| ბმული სია | n | n | 1 | n | |
| ჰეშ-ცხრილი | - | n | n | n | სრულყოფილი ჰეშ ფუნქციის შემთხვევაში ღირებულება იქნება O(1) |
| ორობითი ძიების ხე | n | n | n | n | დაბალანსებული ხის შემთხვევაში ღირებულება იქნება O(log(n)) |
| B-ხე | log(n) | log(n) | log(n) | log(n) | |
| წითელ-შავი ხე | log(n) | log(n) | log(n) | log(n) | |
| AVL ხე | log(n) | log(n) | log(n) | log(n) | |
| ბლუმის ფილტრი | - | 1 | 1 | - | ძიებისას შესაძლებელია ყალბი დადებითი შედეგები |
| სახელი | საუკეთესო | საშუალო | უარესი | მეხსიერება | სტაბილური | კომენტარები |
|---|---|---|---|---|---|---|
| ბუშტულასებრი დალაგება | n | n2 | n2 | 1 | დიახ | |
| ჩასმის დალაგება | n | n2 | n2 | 1 | დიახ | |
| ამორჩევით დალაგება | n2 | n2 | n2 | 1 | არა | |
| გროვით დალაგება | n log(n) | n log(n) | n log(n) | 1 | არა | |
| შერწყმითი დალაგება | n log(n) | n log(n) | n log(n) | n | დიახ | |
| სწრაფი დალაგება | n log(n) | n log(n) | n2 | log(n) | არა | Quicksort ჩვეულებრივ კეთდება in-place O(log(n)) სტეკის სივრცით |
| შელ დალაგება | n log(n) | დამოკიდებულია ხარვეზების თანმიმდევრობაზე | n (log(n))2 | 1 | არა | |
| დათვლის დალაგება | n + r | n + r | n + r | n + r | დიახ | r - მასივში ყველაზე დიდი რიცხვი |
| რადიქს დალაგება | n * k | n * k | n * k | n + k | დიახ | k - ყველაზე გრძელი გასაღების სიგრძე |
თქვენ შეგიძლიათ მხარდაჭერა გამოუხატოთ ამ პროექტს ❤️️ GitHub ან ❤️️ Patreon-ით.
ადამიანები, რომლებიც მხარს უჭერენ ამ პროექტს ∑ = 1
კიდევ რამდენიმე პროექტი და სტატია JavaScript-სა და ალგორითმებზე trekhleb.dev-ზე