README.ru-RU.md

JavaScript: Алгоритмы и Структуры Данных

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

Каждый алгоритм и структура данных имеет собственный отдельный README файл с объяснением и ссылками для получения подробной информации (включая видеоролики на YouTube).

Read this in other languages: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português

☝Обратите внимание, проект предназначен для использования только в учебных и исследовательских целях - не предназначен для использования в реальных проектах.

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

Структура данных - это особый способ организации и хранения данных в компьютере, который позволяет данным быть доступными и эффективно изменяться. Также, структура данных - это коллекция данных, содержащая зависимости между ними и функции или операции, работающие с данными.

B - Начинающий, A - Продвинутый

• B Связный список
• B Двусвязный список
• B Очередь
• B Стек
• B Хэш таблица
• B Пирамида - (куча, сортирующее дерево) максимальные и минимальные версии
• B Очередь с приоритетом
• A Префиксное Дерево
• A Дерево
  • A Двоичное Дерево Поиска
  • A АВЛ-дерево
  • A Красно-чёрное Дерево
  • A Сегмент Дерева - с примерами запросов диапазона min / max / sum
  • A Дерево Фенвика (Двоичное индексируемое дерево)
• A Граф (как направленный, так и ненаправленный)
• A Непересекающийся Набор
• A Фильтр Блума

Алгоритмы

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

B - Начинающий, A - Продвинутый

Алгоритмы по темам

• Математика
  • B Небольшая Манипуляция - установка/получение/обновление/очистка битов, умножение/деление на два, сделать отрицательным и т.д.
  • B Факториал
  • B Числа Фибоначчи - классический и закрытый варианты
  • B Тест примитивности (метод пробного деления)
  • B Алгоритм Евклида - вычислить наибольший общий делитель (GCD)
  • B Наименьшее Общее Кратное (LCM)
  • B Решето Эратосфена - поиск всех простых чисел до любого заданного предела
  • B Сила Двух - проверьте, является ли число силой двух (наивные и побитовые алгоритмы)
  • B Треугольник Паскаля
  • B Комплексное Число - комплексные числа и основные операции с ними
  • B Радиан & Степень - радиан в степень и обратное преобразование
  • B Быстрое Включение
  • A Целочисленное Разбиение
  • A Квадратный Корень - метод Ньютона
  • A Алгоритм Лю Хуэя π - приближенные π расчеты на основе N-gons
  • A Дискретное Преобразование Фурье - декомпозиция функции времени (сигнал) на частоты, которые составляют его
• Наборы
  • B Декартово Произведение - продукт из нескольких наборов
  • B Тасование Фишера-Йетса - случайная перестановка конечной последовательности
  • A Алгоритм установки мощности - все подмножества множества (побитовые и обратные решения)
  • A Перестановка (с повторениями и без них)
  • A Комбинация (с повторениями и без них)
  • A Наибольшая Общая Подпоследовательность Longest Common Subsequence (LCS)
  • A Наибольшая Возрастающая Подпоследовательность
  • A Короткая Общая Суперпоследовательность Shortest Common Supersequence (SCS)
  • A Проблема Рюкзака - "0/1" и "Свободный"
  • A Максимальный Подмассив - "Грубая Сила" и "Динамическое программирование" (Kadane) версии
  • A Сумма Комбинаций - найти все комбинации, которые образуют определенную сумму
• Строки
  • B Расстояние Хемминга - количество позиций, в которых символы различаются
  • A Расстояние Левенштейна - минимальное изменяемое расстояние между двумя последовательностями
  • A Алгоритм Кнута-Морриса-Пратта (KMP Алгоритм) - поиск подстроки (сопоставление шаблонов)
  • A Алгоритм Z - поиск подстроки (сопоставление шаблонов)
  • A Алгоритм Рабина Карпа - поиск подстроки
  • A Наибольшая общая подстрока
  • A Сопоставление Регулярных Выражений
• Поиски
  • B Линейный Поиск
  • B Прыжковый Поиск (или блочный поиск) - поиск в отсортированном массиве
  • B Бинарный Поиск (или двоичный поиск) - поиск в отсортированном массиве
  • B Интерполяционный Поиск - поиск в равномерно распределенном отсортированном массиве
• Сортировки
  • B Пузырьковая Сортировка
  • B Сортировка Выбором
  • B Сортировка Вставками
  • B Пирамидальная Сортировка
  • B Сортировка Слиянием
  • B Быстрая Сортировка - разные реализации
  • B Сортировка Шелла - сортировка включениями с убывающими приращениями
  • B Сортировка Подсчётом
  • B Поразрядная Сортировка
• Связные списки
  • B Прямой Обход
  • B Обратный Обход
• Деревья
  • B Поиск в глубину Depth-First Search (DFS)
  • B Поиск в ширину Breadth-First Search (BFS)
• Графы
  • B Поиск в глубину Depth-First Search (DFS)
  • B Поиск в ширину Breadth-First Search (BFS)
  • B Алгоритм Крускала - поиск минимального остовного дерева (MST) для взвешенного неориентированного графа
  • A Алгоритм Дейкстры - поиск кратчайших путей ко всем вершинам графа из одной вершины
  • A Алгоритм Беллмана-Форда - поиск кратчайших путей ко всем вершинам графа из одной вершины
  • A Алгоритм Флойда-Уоршолла - найти кратчайший путь между всеми парами вершин
  • A Обнаружения Цикла - как для направленных, так и для неориентированных графов (версии на основе DFS и непересекающихся наборов)
  • A Алгоритм Прима - поиск минимального остовного дерева (MST) для взвешенного неориентированного графа
  • A Топологическая Сортировка - метод DFS
  • A Точки Сочленения - Алгоритм Тарьяна (основанный на DFS)
  • A Мосты - Алгоритм на основе DFS
  • A Эйлеров путь и Эйлерова цепь - Алгоритм Флери - посещение каждого края ровно один раз
  • A Гамильтонов Цикл - посещение каждой вершины ровно один раз
  • A Сильно Связные Компоненты - Алгоритм Косарайю
  • A Задача Коммивояжера - кратчайший маршрут, по которому посещает каждый город и возвращается в исходный город
• Криптография
  • B Полиномиальный Хэш - хэш-функция на основе полинома
• Без категории
  • B Ханойская Башня
  • B Квадратная Матрица Вращения - алгоритм на месте
  • B Алгоритм прыжка - обратное отслеживание, динамическое программирование (сверху вниз + снизу вверх) и примеры
  • B Уникальный Путь - обратное отслеживание, динамическое программирование и примеры на основе треугольника Паскаля
  • B Дождь Террасы - проблема улавливания дождевой воды (версии динамического программирования и грубой силы)
  • B Рекурсивная Лестница - подсчитать количество способов добраться до вершины (4 решения)
  • A Проблема N-Queens
  • A Рыцарский Тур

Алгоритмы по парадигме

Алгоритмическая парадигма - это общий метод или подход, который лежит в основе проектирования класса алгоритмов. Это абстракция выше, чем понятие алгоритма, так же как алгоритм - это абстракция выше, чем компьютерная программа.

• Грубая Сила (Полный перебор) - посмотрите на все возможности и выберите лучшее решение
  • B Линейный Поиск
  • B Дождь Террасы - проблема улавливания дождевой воды
  • B Рекурсивная Лестница - подсчитать количество способов добраться до вершины
  • A Максимальный Подмассив
  • A Задача Коммивояжера - кратчайший маршрут, по которому посещает каждый город и возвращается в исходный город
  • A Дискретное Преобразование Фурье - декомпозиция функции времени (сигнал) на частоты, которые составляют его
• Жадный алгоритм - выбирайте оптимальный вариант на текущий момент, без каких-либо раздумий на будущее
  • B Алгоритм прыжка
  • A Проблема Сободного Рюкзака
  • A Алгоритм Дейкстры - поиск кратчайших путей ко всем вершинам графа из одной вершины
  • A Алгоритм Прима - поиск минимального остовного дерева (MST) для взвешенного неориентированного графа
  • A Алгоритм Крускала - поиск минимального остовного дерева (MST) для взвешенного неориентированного графа
• Разделяй и властвуй - разделите проблему на более мелкие части, а затем решите эти части
  • B Бинарный Поиск
  • B Ханойская Башня
  • B Треугольник Паскаля
  • B Алгоритм Евклида - вычислить наибольший общий делитель (GCD)
  • B Сортировка Слиянием
  • B Быстрая Сортировка
  • B Поиск по дереву в глубину (DFS)
  • B Поиск по графам в глубину (DFS)
  • B Алгоритм прыжка
  • B Быстрое Включение
  • A Перестановка (с повторениями и без них)
  • A Комбинация (с повторениями и без них)
• Динамическое Программирование - создайте решение, используя ранее найденные подрешения
  • B Числа Фибоначчи
  • B Алгоритм прыжка
  • B Уникальный Путь
  • B Дождь Террасы - проблема улавливания дождевой воды
  • B Рекурсивная Лестница - подсчитать количество способов добраться до вершины
  • A Расстояние Левенштейна - минимальное изменяемое расстояние между двумя последовательностями
  • A Наибольшая Общая Подпоследовательность (LCS)
  • A Наибольшая общая подстрока
  • A Наибольшая Возрастающая Подпоследовательность
  • A Короткая Общая Суперпоследовательность
  • A 0/1 Проблема Рюкзака
  • A Целочисленное Разбиение
  • A Максимальный Подмассив
  • A Алгоритм Беллмана-Форда - поиск кратчайших путей ко всем вершинам графа из одной вершины
  • A Алгоритм Флойда-Уоршолла - найти кратчайший путь между всеми парами вершин
  • A Сопоставление Регулярных Выражений
• Возврат (Бэктрекинг) - подобно "грубой силе", попробуйте создать все возможные решения, но каждый раз, когда вы создаете следующее решение, тестируйте его на удовлетворение всем условиям, и только тогда продолжайте генерировать последующие решения. В противном случае, отступите и продолжайте искать другой путь поиска решения. Обычно используется метод DFS.
  • B Алгоритм прыжка
  • B Уникальный Путь
  • B Алгоритм установки мощности - все подмножества множества
  • A Гамильтонов Цикл - посещение каждой вершины ровно один раз
  • A Проблема N-Queens
  • A Рыцарский Тур
  • A Сумма Комбинаций - найти все комбинации, которые образуют определенную сумму
• Ветви И Границы - запомните самое дешевое решение - это решение найденное на каждом этапе возврата (бэктрекинга), используйте решение найденное до нижней границы стоимости решения проблемы, чтобы отказаться от решений с затратами больше, чем самое дешевое решение которое уже найдено. Обычно используется метод BFS в сочетании с методом DFS.

Как использовать репозиторий

Установите все зависимости

npm install

Запуск ESLint

Вы можете запустить его, чтобы проверить качество кода.

npm run lint

Запуск тестов

npm test

Запуск теста по имени

npm test -- 'LinkedList'

Песочница

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

Затем просто запустите следующую команду, чтобы проверить, работает ли ваш код в песочнице так, как ожидалось:

npm test -- 'playground'

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

Ссылки на источники

▶ Data Structures and Algorithms on YouTube

Big O нотации

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)	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	-	Возможны ложные срабатывания при поиске

Сложность операций сортировки

Name	Лучшее	Среднее	Худшее	Память	Стабильность	Комментарий
Пузырьковая Сортировка	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	No
Сортировка Подсчётом	n + r	n + r	n + r	n + r	Да	r - самое большое число в массиве
Поразрядная Сортировка	n * k	n * k	n * k	n + k	Да	k - длина самого длинного ключа