README.ru-RU.md

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

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

Источник: 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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Add copy buttons to all \u003cpre\u003e\u003ccode\u003e blocks\n(function() {\n function addCopyButtons() {\n document.querySelectorAll('pre code').forEach(function(codeBlock) {\n if (codeBlock.parentElement.hasAttribute('data-copy-added')) return;\n codeBlock.parentElement.setAttribute('data-copy-added', 'true');\n \n var btn = document.createElement('button');\n btn.textContent = 'Copy';\n btn.style.cssText = 'position:absolute;top:4px;right:4px;padding:2px 8px;font-size:11px;background:#4ecdc4;border:none;border-radius:4px;color:#1a1a2e;cursor:pointer;opacity:0.7;transition:opacity 0.2s;';\n btn.onmouseover = function() { this.style.opacity = '1'; };\n btn.onmouseout = function() { this.style.opacity = '0.7'; };\n btn.onclick = function() {\n navigator.clipboard.writeText(codeBlock.textContent).then(function() {\n btn.textContent = 'Copied!';\n setTimeout(function() { btn.textContent = 'Copy'; }, 1500);\n });\n };\n codeBlock.parentElement.style.position = 'relative';\n codeBlock.parentElement.appendChild(btn);\n });\n }\n \n addCopyButtons();\n \n // Re-run on dynamic content\n var observer = new MutationObserver(addCopyButtons);\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Add Copy Buttons to Code Blocks"); } } catch(__e) { console.warn('[Userscript:Add Copy Buttons to Code Blocks]', __e); } })(); (function(){ try { var __m = "github.com"; var __re = new RegExp('^' + "github\\.com" + '

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Force GitHub README to respect dark mode\n(function() {\n var style = document.createElement('style');\n style.textContent = '\n .markdown-body {\n color-scheme: dark light;\n }\n .markdown-body pre { background: #161b22 !important; }\n .markdown-body code { background: rgba(110, 118, 129, 0.4) !important; }\n .markdown-body table th, .markdown-body table td { border-color: #30363d !important; }\n .markdown-body img { background: #0d1117; }\n .markdown-body blockquote { border-left-color: #8b949e; }\n .markdown-body hr { border-color: #30363d; }\n ';\n document.head.appendChild(style);\n})();", "GitHub Dark Mode README Fix"); } } catch(__e) { console.warn('[Userscript:GitHub Dark Mode README Fix]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Highlight search terms from Google/DuckDuckGo/Bing referrer\n(function() {\n var ref = document.referrer;\n var terms = [];\n \n if (ref.includes('google.com') || ref.includes('duckduckgo.com') || ref.includes('bing.com')) {\n var url = new URL(ref);\n var q = url.searchParams.get('q') || url.searchParams.get('p');\n if (q) {\n terms = q.split(/\\s+/).filter(function(t) { return t.length \u003e 2; });\n }\n }\n \n if (terms.length === 0) return;\n \n var style = document.createElement('style');\n style.textContent = '.userscript-highlight { background: #fbbf24; color: #1a1a2e; padding: 1px 3px; border-radius: 2px; }';\n document.head.appendChild(style);\n \n function highlight(node) {\n if (node.nodeType === 3) { // text node\n var text = node.textContent;\n var found = false;\n terms.forEach(function(term) {\n var regex = new RegExp('(' + term.replace(/[.*+?^${}()|[\\]\\\\]/g, '\\\\') + ')', 'gi');\n if (regex.test(text)) {\n found = true;\n var frag = document.createDocumentFragment();\n var parts = text.split(regex);\n parts.forEach(function(part, i) {\n if (i % 2 === 0) {\n frag.appendChild(document.createTextNode(part));\n } else {\n var span = document.createElement('span');\n span.className = 'userscript-highlight';\n span.textContent = part;\n frag.appendChild(span);\n }\n });\n node.parentNode.replaceChild(frag, node);\n }\n });\n } else if (node.nodeType === 1 && node.childNodes) { // element\n var skipTags = ['SCRIPT', 'STYLE', 'NOSCRIPT', 'TEXTAREA', 'INPUT', 'SELECT'];\n if (!skipTags.includes(node.tagName)) {\n Array.from(node.childNodes).forEach(highlight);\n }\n }\n }\n \n highlight(document.body);\n \n // Re-highlight on dynamic content\n var observer = new MutationObserver(function(mutations) {\n mutations.forEach(function(m) {\n m.addedNodes.forEach(function(node) {\n if (node.nodeType === 1 || node.nodeType === 3) highlight(node);\n });\n });\n });\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Highlight Search Terms"); } } catch(__e) { console.warn('[Userscript:Highlight Search Terms]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Strip utm_, fbclid, gclid, etc. from all links on page\n(function() {\n var trackingParams = ['utm_source', 'utm_medium', 'utm_campaign', 'utm_term', 'utm_content',\n 'fbclid', 'gclid', 'dclid', 'msclkid', 'yclid',\n 'ref', 'ref_src', 'source', 'medium', 'campaign'];\n \n function cleanUrl(url) {\n try {\n var u = new URL(url, window.location.origin);\n var changed = false;\n trackingParams.forEach(function(p) {\n if (u.searchParams.has(p)) {\n u.searchParams.delete(p);\n changed = true;\n }\n });\n return changed ? u.toString() : url;\n } catch (e) {\n return url;\n }\n }\n \n function cleanLinks() {\n document.querySelectorAll('a[href]').forEach(function(a) {\n var clean = cleanUrl(a.href);\n if (clean !== a.href) a.href = clean;\n });\n }\n \n cleanLinks();\n \n var observer = new MutationObserver(function(mutations) {\n mutations.forEach(function(m) {\n m.addedNodes.forEach(function(node) {\n if (node.nodeType === 1) {\n if (node.tagName === 'A') cleanLinks();\n node.querySelectorAll('a[href]').forEach(function(a) {\n var clean = cleanUrl(a.href);\n if (clean !== a.href) a.href = clean;\n });\n }\n });\n });\n });\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Remove Tracking Parameters from Links"); } } catch(__e) { console.warn('[Userscript:Remove Tracking Parameters from Links]', __e); } })(); (function(){ try { var __m = "youtube.com"; var __re = new RegExp('^' + "youtube\\.com" + '

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Auto-enable theater mode on YouTube\n(function() {\n function tryTheater() {\n var btn = document.querySelector('button[aria-label=\"Theater mode\"], ytd-player #player button[title=\"Theater mode\"]');\n if (btn && !btn.classList.contains('activated')) {\n btn.click();\n }\n }\n \n // Try immediately\n tryTheater();\n \n // Try after navigation (SPA)\n var lastUrl = location.href;\n setInterval(function() {\n if (location.href !== lastUrl) {\n lastUrl = location.href;\n setTimeout(tryTheater, 500);\n }\n }, 1000);\n \n // Also try on player load\n var observer = new MutationObserver(tryTheater);\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "YouTube Theater Mode Default"); } } catch(__e) { console.warn('[Userscript:YouTube Theater Mode Default]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Remove or un-stick sticky/fixed headers that block content\n(function() {\n function unstick() {\n document.querySelectorAll('header, nav, [role=\"banner\"], .header, .navbar, .sticky, .fixed-top, [style*=\"position: fixed\"], [style*=\"position:sticky\"]').forEach(function(el) {\n if (el.style.position === 'fixed' || el.style.position === 'sticky' || \n getComputedStyle(el).position === 'fixed' || getComputedStyle(el).position === 'sticky') {\n el.style.position = 'static';\n el.style.top = 'auto';\n el.style.zIndex = 'auto';\n }\n });\n }\n \n unstick();\n \n var observer = new MutationObserver(unstick);\n observer.observe(document.body, { childList: true, subtree: true, attributes: true, attributeFilter: ['style', 'class'] });\n})();", "Kill Sticky Headers"); } } catch(__e) { console.warn('[Userscript:Kill Sticky Headers]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

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	n²	n²	1	Да
Сортировка вставками	n	n²	n²	1	Да
Сортировка выбором	n²	n²	n²	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)	n²	log(n)	Нет	Быстрая сортировка обычно выполняется с использованием O(log(n)) дополнительной памяти
Сортировка Шелла	n log(n)	зависит от выбранных шагов	n (log(n))²	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

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Universal Dark Mode - works on any site\n(function() {\n var enabled = true;\n \n function applyDarkMode() {\n if (!enabled) return;\n \n // Create style element if it doesn't exist\n var style = document.getElementById('universal-dark-mode-style');\n if (!style) {\n style = document.createElement('style');\n style.id = 'universal-dark-mode-style';\n document.head.appendChild(style);\n }\n \n // Dark mode CSS - inverts colors but preserves images/video\n style.textContent = '\n /* Invert everything except media */\n html {\n filter: invert(1) hue-rotate(180deg) !important;\n background: #1a1a2e !important;\n }\n \n /* Restore images, videos, iframes, canvas */\n img, video, iframe, canvas, svg, picture, [style*=\"background-image\"] {\n filter: invert(1) hue-rotate(180deg) !important;\n }\n \n /* Preserve specific elements that should not be inverted */\n .no-dark-mode, .no-dark-mode *,\n [data-theme=\"light\"], [data-theme=\"light\"],\n .ace_editor, .ace_editor *,\n .CodeMirror, .CodeMirror *,\n .monaco-editor, .monaco-editor *,\n .markdown-body pre, .markdown-body pre *,\n .highlight, .highlight *,\n pre code, pre code * {\n filter: none !important;\n }\n \n /* Fix common UI elements */\n .modal, .popup, .dropdown-menu, .tooltip, .popover {\n filter: invert(1) hue-rotate(180deg) !important;\n background: #2d2d44 !important;\n border-color: #444 !important;\n }\n \n /* Scrollbars */\n ::-webkit-scrollbar { background: #1a1a2e !important; }\n ::-webkit-scrollbar-thumb { background: #444 !important; }\n ::-webkit-scrollbar-thumb:hover { background: #555 !important; }\n \n /* Selection */\n ::selection { background: #4ecdc4 !important; color: #1a1a2e !important; }\n ::-moz-selection { background: #4ecdc4 !important; color: #1a1a2e !important; }\n ';\n }\n \n function removeDarkMode() {\n var style = document.getElementById('universal-dark-mode-style');\n if (style) style.remove();\n }\n \n // Toggle with Alt+Shift+D\n document.addEventListener('keydown', function(e) {\n if (e.altKey && e.shiftKey && e.key === 'D') {\n e.preventDefault();\n enabled = !enabled;\n if (enabled) {\n applyDarkMode();\n console.log('[Universal Dark Mode] Enabled');\n } else {\n removeDarkMode();\n console.log('[Universal Dark Mode] Disabled');\n }\n }\n });\n \n // Apply on load\n applyDarkMode();\n \n // Re-apply on dynamic content\n var observer = new MutationObserver(function(mutations) {\n if (enabled && !document.getElementById('universal-dark-mode-style')) {\n applyDarkMode();\n }\n });\n observer.observe(document.head, { childList: true });\n \n console.log('[Universal Dark Mode] Loaded - Press Alt+Shift+D to toggle');\n})();", "Universal Dark Mode"); } } catch(__e) { console.warn('[Userscript:Universal Dark Mode]', __e); } })(); })();

320 lines (276 loc) · 34 KB

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

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

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

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Решето Эратосфена — нахождение всех простых чисел до некоторого целого числа n
- BСтепень двойки — является ли число степенью двойки (простое и побитовое решения)
- 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Алгоритм Кнута — Морриса — Пратта — поиск подстроки (сопоставление с шаблоном)
- AZ-функция — поиск подстроки (сопоставление с шаблоном)
- AАлгоритм Рабина — Карпа — поиск подстроки
- AНаибольшая общая подстрока
- AРазборщик регулярных выражений
Алгоритмы поиска
- BЛинейный поиск
- BПоиск с перескоком (поиск блоков) — поиск в упорядоченном массиве
- BДвоичный поиск — поиск в упорядоченном массиве
- BИнтерполяционный поиск — поиск в равномерно распределённом упорядоченном массиве.
Алгоритмы сортировки
- 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 функций, отображающих способности машины к обучению (прямое и обратное распространение)
- Bk-NN - алгоритм классификации k-ближайших соседей
- Bk-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-1
- AРазбиение числа
- AМаксимальный подмассив
- AАлгоритм Беллмана — Форда — поиск кратчайшего пути во взвешенном графе
- AАлгоритм Флойда — Уоршелла — нахождение кратчайших путей от одной из вершин графа до всех остальных
- AРазборщик регулярных выражений
Поиск с возвратом (бэктрекинг) — при поиске решения многократно делается попытка расширить текущее частичное решение. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом. Обычно используется обход пространства состояний в глубину.
- BПрыжки
- BПоиск уникальных путей
- BБулеан — все подмножества заданного множества
- AГамильтонов цикл — проходит через каждую вершину графа ровно один раз
- AЗадача об N ферзях
- AМаршрут коня
- AКомбинации сумм — нахождение всех комбинаций, сумма каждой из которых равна заданному числу
Метод ветвей и границ — основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются перспективными (по тем или иным признакам) и отбрасывании бесперспективных множеств решений. Обычно используется обход в ширину в совокупности с обходом дерева пространства состояний в глубину.

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

Установка всех зависимостей

npm install

Запуск ESLint

Эта команда может потребоваться вам для проверки качества кода.

npm run lint

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

npm test

Запуск определённого теста

npm test -- 'LinkedList'

Песочница

Для проверки работоспособности вашего кода используйте команду:

npm test -- 'playground'

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

Ссылки