Skip to content

Latest commit

 

History

History
306 lines (262 loc) · 35.5 KB

README.uk-UA.md

File metadata and controls

306 lines (262 loc) · 35.5 KB

Алгоритми JavaScript та структури даних

CI codecov

Даний репозиторій приклади багатьох популярних алгоритмів та структур даних на основі JavaScript.

Кожен алгоритм та структура даних має свій окремий README-файл із відповідними поясненнями та посиланнями для подальшого вивчення (включаючи посилання на відео на YouTube).

Вивчення матеріалу на інших мовах: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana, Bahasa Indonesia, Arabic

☝ Зверніть увагу! Даний проект призначений лише для навчальних та дослідницьких цілей, і він не призначений для виробництва (продакшн).

Структури даних

Структура даних (в програмуванні) - це спосіб організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру. Точніше, структура даних - це сукупність даних цінності, взаємозв'язки між ними та функції або операції, до яких можна застосувати дані.

B - Початківець, A - Просунутий рівень

Алгоритми

Алгоритм - це однозначна специфікація способу вирішення класу задач. Це набір правил, які точно визначають послідовність операцій.

B - Початківець, A - Просунутий рівень

Алгоритми за тематикою

Парадигма програмування

Парадиигма програмува́ння — це система ідей і понять, які визначають стиль написання комп'ютерних програм, а також спосіб мислення програміста. Це спосіб концептуалізації, що визначає організацію обчислень і структурування роботи, яку виконує комп'ютер.

Як користуватися цим репозиторієм

Встановіть усі залежності

npm install

Запустіть ESLint

Запустіть для перевірки якості коду

npm run lint

Запустіть усі тести

npm test

Запустіть тести за назвою

npm test -- 'LinkedList'

Ігрище

Ви можете побавитись зі структурами даних та алгоритмами в файлі ./src/playground/playground.js та писати тести до них в даному файлі ./src/playground/__test__/playground.test.js.

Для перевірки, чи працює ваш код належним чином запустіть команду:

npm test -- 'playground'

Корисна інформація

Список літератури

▶ Структури даних та алгоритми на YouTube

Асимптотична нотація великого О (нотація Ландау)

Асимптотична нотація великого О (нотація Ландау) розповсюджена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці. Асимптотична нотація великого О

Джерело: Асимптотична нотація великого О.

Нижче наведено список деяких найбільш часто використовуваних позначень нотації Ландаута їх порівняння продуктивності з різними розмірами вхідних даних.

Нотація Ландау Обчислення для 10 елементів Обчислення для 100 елементів Обчислення для 1000 елементів
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

Складність операцій в структурі даних

Структура даних Доступ Пошук Вставка Видалення Коментарі
Масив 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))
Б-дерево log(n) log(n) log(n) log(n)
Червоно-чорне дерево log(n) log(n) log(n) log(n)
АВЛ-дерево 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) Ні Швидке сортування зазвичай виконується на місці з використанням 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