В этом репозитории содержатся базовые JavaScript-примеры многих популярных алгоритмов и структур данных.
Для каждого алгоритма и структуры данных есть свой файл README с соответствующими пояснениями и ссылками на материалы для дальнейшего изучения (в том числе и ссылки на видеоролики в YouTube).
Читать на других языках: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Türk, Italiana, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch
☝ Замечание: этот репозиторий предназначен для учебно-исследовательских целей (не для использования в продакшн-системах).
Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
B
- Базовый уровень, A
- Продвинутый уровень
B
Связный списокB
Двунаправленный связный списокB
ОчередьB
СтекB
Хеш-таблицаB
Куча — максимальная и минимальная версииB
Очередь с приоритетомA
Префиксное деревоA
ДеревьяA
Двоичное дерево поискаA
АВЛ-деревоA
Красно-чёрное деревоA
Дерево отрезков — для минимума, максимума и суммы отрезковA
Дерево Фенвика (двоичное индексированное дерево)
A
Граф (ориентированный и неориентированный)A
Система непересекающихся множествA
Фильтр Блума
Алгоритм — конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
B
- Базовый уровень, A
- Продвинутый уровень
- Математика
B
Битовые манипуляции — получение/запись/сброс/обновление битов, умножение/деление на 2, сделать отрицательным и т.п.B
Двоичное число с плавающей запятой - двоичное представление чисел с плавающей запятойB
ФакториалB
Числа Фибоначчи — классическое решение, решение в замкнутой формеB
Простые множители - нахождение простых множителей и их подсчёт с использованием теоремы Харди-РамануджанаB
Тест простоты (метод пробного деления)B
Алгоритм Евклида — нахождение наибольшего общего делителя (НОД)B
Наименьшее общее кратное (НОК)B
Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа nB
Степень двойки — является ли число степенью двойки (простое и побитовое решения)B
Треугольник ПаскаляB
Комплексные числа — комплексные числа, базовые операции над нимиB
Радианы и градусы — конвертирование радианов в градусы и наоборотB
Быстрое возведение в степеньB
Схема Горнера - оценка полиномовB
Матрицы - матрицы и основные операции с матрицами (умножение, транспонирование и т.д.)B
Евклидово расстояние - расстояние между двумя точками/векторами/матрицамиA
Разбиение числаA
Квадратный корень — метод НьютонаA
Алгоритм Лю Хуэя — расчёт числа π с заданной точностью методом вписанных правильных многоугольниковA
Дискретное преобразование Фурье — разложение временной функции (сигнала) на частотные составляющие
- Множества
B
Декартово произведение — результат перемножения множествB
Тасование Фишера — Йетса — создание случайных перестановок конечного множестваA
Булеан — все подмножества заданного множества (побитовый поиск и поиск с возвратом)A
Перестановки (с повторениями и без повторений)A
Сочетания (с повторениями и без повторений)A
Наибольшая общая подпоследовательностьA
Наибольшая увеличивающаяся подпоследовательностьA
Наименьшая общая супер-последовательностьA
Задача о рюкзаке — "0/1" и "неограниченный" рюкзакиA
Максимальный под-массив — метод полного перебора и алгоритм КаданеA
Комбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
- Алгоритмы работы со строками
B
Расстояние Хэмминга — число позиций, в которых соответствующие символы различныA
Расстояние Левенштейна — метрика, измеряющая разность между двумя последовательностямиA
Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)A
Z-функция — поиск подстроки (сопоставление с шаблоном)A
Алгоритм Рабина — Карпа — поиск подстрокиA
Наибольшая общая подстрокаA
Разборщик регулярных выражений
- Алгоритмы поиска
B
Линейный поискB
Поиск с перескоком (поиск блоков) — поиск в упорядоченном массивеB
Двоичный поиск — поиск в упорядоченном массивеB
Интерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
- Алгоритмы сортировки
B
Сортировка пузырькомB
Сортировка выборомB
Сортировка вставкамиB
Пирамидальная сортировка (сортировка кучей)B
Сортировка слияниемB
Быстрая сортировка — с использованием дополнительной памяти и без её использованияB
Сортировка ШеллаB
Сортировка подсчётомB
Поразрядная сортировка
- Связный список
- Деревья
- Графы
B
Поиск в глубинуB
Поиск в ширинуB
Алгоритм Краскала — нахождение минимального остовного дерева для взвешенного неориентированного графаA
Алгоритм Дейкстры — нахождение кратчайших путей от одной из вершин графа до всех остальныхA
Алгоритм Беллмана — Форда — нахождение кратчайших путей от одной из вершин графа до всех остальныхA
Алгоритм Флойда — Уоршелла — нахождение кратчайших расстояний между всеми вершинами графаA
Задача нахождения цикла — для ориентированных и неориентированных графов (на основе поиска в глубину и системы непересекающихся множеств)A
Алгоритм Прима — нахождение минимального остовного дерева для взвешенного неориентированного графаA
Топологическая сортировка — на основе поиска в глубинуA
Шарниры (разделяющие вершины) — алгоритм Тарьяна (на основе поиска в глубину)A
Мосты — на основе поиска в глубинуA
Эйлеров путь и Эйлеров цикл — алгоритм Флёри (однократное посещение каждой вершины)A
Гамильтонов цикл — проходит через каждую вершину графа ровно один разA
Компоненты сильной связности — алгоритм КосарайюA
Задача коммивояжёра — кратчайший маршрут, проходящий через указанные города с последующим возвратом в исходный город
- Криптография
B
Полиноминальный хэш — функция кольцевого хэша, основанная на полиномеB
Шифр ограждения рельсов - алгоритм транспозиционного шифра для кодирования сообщенийB
Шифр Цезаря - простой подстановочный шифрB
Шифр Хилла - подстановочный шифр на основе линейной алгебры
- Машинное обучение
B
Нано-нейрон — 7 простых JavaScript функций, отображающих способности машины к обучению (прямое и обратное распространение)B
k-NN - алгоритм классификации k-ближайших соседейB
k-Means - алгоритм кластеризации по методу k-средних
- Обработка изображений
B
Резьба по шву - алгоритм изменения размера изображения с учетом содержания
- Статистика
B
Взвешенная случайность - выбор случайного элемента из списка на основе веса элементов
- Эволюционные алгоритмы
A
Генетический алгоритм - пример применения генетического алгоритма для обучения самопаркующихся автомобилей
- Прочие алгоритмы
B
Ханойская башняB
Поворот квадратной матрицы — используется дополнительная памятьB
Прыжки — на основе бэктрекинга, динамического программирования (сверху-вниз + снизу-вверх) и жадных алгоритмовB
Поиск уникальных путей — на основе бэктрекинга, динамического программирования и треугольника ПаскаляB
Подсчёт дождевой воды — на основе перебора и динамического программированияB
Задача о рекурсивной лестнице — подсчёт количества путей, по которым можно достичь верха лестницы (4 способа)B
Лучшее время для покупки и продажи акций - примеры "разделяй и властвуй" и в один проходA
Задача об N ферзяхA
Маршрут коня
Парадигма программирования — общий метод или подход, лежащий в основе целого класса алгоритмов. Понятие "парадигма программирования" является более абстрактным по отношению к понятию "алгоритм", которое в свою очередь является более абстрактным по отношению к понятию "компьютерная программа".
- Алгоритмы полного перебора — поиск лучшего решения исчерпыванием всевозможных вариантов
B
Линейный поискB
Подсчёт дождевой водыB
Задача о рекурсивной лестнице — подсчёт количества путей, по которым можно достичь верха лестницыA
Максимальный подмассивA
Задача коммивояжёра — кратчайший маршрут, проходящий через указанные города с последующим возвратом в исходный городA
Дискретное преобразование Фурье — разложение временной функции (сигнала) на частотные составляющие
- Жадные алгоритмы — принятие локально оптимальных решений с учётом допущения об оптимальности конечного решения
B
ПрыжкиA
Задача о неограниченном рюкзакеA
Алгоритм Дейкстры — нахождение кратчайших путей от одной из вершин графа до всех остальныхA
Алгоритм Прима — нахождение минимального остовного дерева для взвешенного неориентированного графаA
Алгоритм Краскала — нахождение минимального остовного дерева для взвешенного неориентированного графа
- Разделяй и властвуй — рекурсивное разбиение решаемой задачи на более мелкие
B
Двоичный поискB
Ханойская башняB
Треугольник ПаскаляB
Алгоритм Евклида — нахождение наибольшего общего делителя (НОД)B
Сортировка слияниемB
Быстрая сортировкаB
Поиск в глубину (дерево)B
Поиск в глубину (граф)B
Матрицы - генерирование и обход матриц различной формыB
ПрыжкиB
Быстрое возведение в степеньB
Лучшее время для покупки и продажи акций - примеры "разделяй и властвуй" и в один проходA
Перестановки (с повторениями и без повторений)A
Сочетания (с повторениями и без повторений)
- Динамическое программирование — решение общей задачи конструируется на основе ранее найденных решений подзадач
B
Числа ФибоначчиB
ПрыжкиB
Поиск уникальных путейB
Подсчёт дождевой водыB
Задача о рекурсивной лестнице — подсчёт количества путей, по которым можно достичь верха лестницыB
Резьба по шву - алгоритм изменения размера изображения с учетом содержанияA
Расстояние Левенштейна — метрика, измеряющая разность между двумя последовательностямиA
Наибольшая общая подпоследовательностьA
Наибольшая общая подстрокаA
Наибольшая увеличивающаяся подпоследовательностьA
Наименьшая общая суперпоследовательностьA
Рюкзак 0-1A
Разбиение числаA
Максимальный подмассивA
Алгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графеA
Алгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальныхA
Разборщик регулярных выражений
- Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
B
ПрыжкиB
Поиск уникальных путейB
Булеан — все подмножества заданного множестваA
Гамильтонов цикл — проходит через каждую вершину графа ровно один разA
Задача об N ферзяхA
Маршрут коня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 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 — длина самого длинного ключа |
ℹ️ A few more projects and articles about JavaScript and algorithms on trekhleb.dev