javascript-algorithms

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

CI codecov

В этом репозитории содержатся базовые JavaScript-примеры многих популярных алгоритмов и структур данных.

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

Читать на других языках: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Türk, Italiana

☝ Замечание: этот репозиторий предназначен для учебно-исследовательских целей (не для использования в продакшн-системах).

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

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

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'

Полезная информация

Ссылки

▶ О структурах данных и алгоритмах

Нотация «О» большое

Нотация «О» большое используется для классификации алгоритмов в соответствии с ростом времени выполнения и затрачиваемой памяти при увеличении размера входных данных. На диаграмме ниже представлены общие порядки роста алгоритмов в соответствии с нотацией «О» большое.

Big O graphs

Источник: Big O Cheat Sheet.

Ниже представлены часто используемые обозначения в нотации «О» большое, а также сравнение их производительностей на различных размерах входных данных.

Нотация «О» большое 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))
B-дерево 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 — длина самого длинного ключа