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

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

Для каждого алгоритма и структуры данных есть свой README с инструкциями, а также дополнительные материалы для чтения и видео на YouTube.

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

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

• связанный список
• очередь
• куча
• хеш-таблица
• куча
• приоритетная очередь
• словарное дерево
• Дерево
  • бинарный поиск
  • АВЛ-дерево
  • красно-черное дерево
  • суффиксное дерево
  • дерево сегментов или дерево интервалов
  • бинарное индексное дерево
• рисунок(ориентированные и неориентированные графы)
• и проверить

алгоритм

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

Темы алгоритмов

• математика
  • факториал
  • Числа Фибоначчи
  • Основное обнаружение(Исключение)
  • Евклидов алгоритм- Вычислить наибольший общий делитель (НОД)
  • ЛКМ (LCM)
  • Целочисленное разделение
• собирать
  • Декартово произведение- Многократные результаты
  • силовой набор- все подмножества множества
  • расположение(с/без повторения)
  • комбинация(с/без повторения)
  • Алгоритм перемешивания- случайная перестановка конечных последовательностей
  • самая длинная общая подпоследовательность (LCS)
  • самая длинная возрастающая подпоследовательность
  • Shortest Common Supersequence (SCS)
  • проблема с рюкзаком - "0/1" and "Unbound" ones
  • проблема максимального подмассива- Алгоритм BF и динамическое программирование
• нить
  • Расстояние Левенштейна- Минимальное расстояние редактирования между двумя последовательностями
  • Расстояние Хэмминга- Количество различных позиций символов
  • Алгоритм Кнута-Морриса-Платта- Поиск подстроки
  • Быстрый поиск строки- Поиск подстроки
  • самая длинная общая подстрока
• поиск
  • бинарный поиск
• Сортировать
  • Пузырьковая сортировка
  • сортировка выбором
  • Сортировка вставками
  • сортировка кучей
  • Сортировка слиянием
  • быстрая сортировка
  • Сортировка холмов
• Дерево
  • поиск в глубину (DFS)
  • Поиск в ширину (BFS)
• рисунок
  • поиск в глубину (DFS)
  • Поиск в ширину (BFS)
  • Алгоритм Дейкстры m- Найти кратчайший путь ко всем вершинам графа
  • Алгоритм Беллмана-Форда- Найти кратчайший путь ко всем вершинам графа
  • Алгоритм круга- Для ориентированных и неориентированных графов (версии на основе DFS и непересекающихся множеств)
  • Алгоритм Пуллина- Найдите минимальное остовное дерево (MST) взвешенного неориентированного графа
  • Алгоритм Крускера- Найдите минимальное остовное дерево (MST) взвешенного неориентированного графа
  • топологическая сортировка- метод ДФС
  • точка артикуляции- Алгоритм Тарьяна (на основе DFS)
  • мост- Алгоритм на основе DFS
  • Путь Эйлера и проблема одного штриха- Алгоритм Флери - посещение каждого ребра за раз
  • Гамильтонова диаграмма- посетить каждую вершину ровно один раз
  • Сильно связанные компоненты- Алгоритм Косараджу
  • задача коммивояжера- Выберите кратчайший маршрут, чтобы посетить каждый город и вернуться в исходный город
• некатегоризированный
  • Ханойская башня
  • Задача восьми ферзей
  • Рыцарский патруль

Алгоритмическая парадигма

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

• Алгоритм БФ- Найдите все возможности и выберите лучшее решение

  • максимальный подмассив
  • задача коммивояжера- Выберите кратчайший маршрут, чтобы посетить каждый город и вернуться в исходный город

• Жадный закон- Выбирайте лучший вариант на данный момент вне зависимости от будущих ситуаций

  • проблема с рюкзаком
  • Алгоритм Дейкстры- Найти кратчайший путь ко всем вершинам графа
  • Алгоритм Прима- Найдите минимальное остовное дерево (MST) взвешенного неориентированного графа
  • Алгоритм Крускала- Найдите минимальное остовное дерево (MST) взвешенного неориентированного графа

• разделяй и властвуй- Разделите проблему на более мелкие части и решите эти части

  • бинарный поиск
  • Ханойская башня
  • Евклидов алгоритм- Вычислить наибольший общий делитель (НОД)
  • расположение(с/без повторения)
  • комбинация(с/без повторения)
  • Сортировка слиянием
  • Quicksort
  • поиск в глубину дерева (DFS)
  • Граф поиска в глубину (DFS)

• динамическое программирование- Создавайте решения, используя ранее найденные подрешения

  • Числа Фибоначчи
  • Расстояние Левенштейна- Минимальное расстояние редактирования между двумя последовательностями
  • самая длинная общая подпоследовательность (LCS)
  • самая длинная общая подстрока
  • самая длинная возрастающая подпоследовательность
  • кратчайшая общая подпоследовательность
  • 0-1 Проблема с рюкзаком
  • Целочисленное разделение
  • максимальный подмассив
  • Алгоритм Беллмана-Форда- Найти кратчайший путь ко всем вершинам графа

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

  • Гамильтонова диаграмма- посетить каждую вершину ровно один раз
  • Задача восьми ферзей
  • Рыцарский патруль

• B & B

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

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

npm install
скопировать код

выполнить тест

npm test
скопировать код

Выполнить тест по имени

npm test -- -t 'LinkedList'
скопировать код

Playground

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

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

npm test -- -t 'playground'
скопировать код

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

Цитировать

▶ Ютуб

Обозначение большого O

Порядок возрастания алгоритма указан в нотации Big O.

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

Ниже приведен список некоторых из наиболее часто используемых нотаций Big O и сравнение их производительности с входными данными разного размера.

Обозначение большого 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	1
хеш-таблица	-	n	n	n
бинарное дерево поиска	n	n	n	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)

Сложность алгоритмов сортировки массивов

название	оптимальный	средний	худший	ОЗУ	стабильность
Пузырьковая сортировка	n	n^2	n^2	1	Yes
Сортировка вставками	n	n^2	n^2	1	Yes
сортировка выбором	n^2	n^2	n^2	1	No
сортировка кучей	n log(n)	n log(n)	n log(n)	1	No
Сортировка слиянием	n log(n)	n log(n)	n log(n)	n	Yes
быстрая сортировка	n log(n)	n log(n)	n^2	log(n)	No
Сортировка холмов	n log(n)	зависит от последовательности пробелов	n (log(n))^2	1	No