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

Привет Всем! Я недавно запустил на GitHub проект JavaScript Algorithms and Data Structures, который содержит примеры классических алгоритмов и структур данных написанных на JavaScript с объяснениями, примерами и ссылками для дальнейшего изучения (в частности на соответствующие YouTube видео). Основная задача проекта — помочь программистам в изучении и применении алгоритмов и сделать это на JavaScript-е.
Для того, чтобы сделать процесс изучения более понятным я постарался добавить графические иллюстрации для каждого алгоритма и структуры данных, чтобы быстрее визуально понять о чем идет речь и как тот или иной алгоритм функционирует.

Так же в корневом README вы найдете справочную информацию, которая может пригодиться при изучении. Например:

• Графики Big O нотации (чтобы визуально быстро уловить разницу между O(n!) и O(n^2))
• Список с конкретными значениями Big O (чтобы понимать насколько большое или маленькое значение у 10! (а оно у него аж 3628800))
• Сложность выполнения базовых операций для структур данных (чтобы понять у каких структур быстрое чтение, а у каких поиск или удаление)
• Сравнительная таблица сложности алгоритмов сортировки (чтобы понять какой способ сортировки выбрать и в каком случае, стабильная ли сортировка или нет)

Весь код на 100% покрыт unit-тестами. Это сделано не только для того, чтобы сохранять код в работоспособном состоянии, но так же и для того, чтобы проиллюстрировать методы и случаи употребления данного конкретного алгоритма или структуры данных (что делать, например, если граф направленный в одном из алгоритмов).

Репозиторий так же содержит песочницу. Это небольшой шаблон функции и пустого теста для нее, который должен помочь программисту сразу же приступить к экспериментам с алгоритмами, вместо того, чтобы создавать заново шаблонный код.

На данный момент в репозитории реализованы следующие структуры данных:

• Linked List
• Queue
• Stack
• Hash Table
• Heap
• Priority Queue
• Trie
• Tree (Binary Search Tree, AVL Tree)
• Graph (both directed and undirected)
• Disjoint Set

Дополнительно так же реализованы более 50 популярных алгоритмов. Среди которых есть алгоритмы сортировки, поиска, алгоритмы связанные с графами, деревьями, множествами, строками и математическими выкладками. Алгоритмы разделены на следующие группы:

• Brute Force Algorithms (перебор всех возможных комбинаций и выбор правильного решения)
• Greedy Algorithms (выбор оптимального решения на каждом текущем шаге)
• Divide and Conquer Algorithms (разделение проблемы на меньшие части и решение этих частей проблемы по-отдельности)
• Dynamic Programming Algorithms (построение решения на основании вычисленных ранее на предыдущих шагах данных)
• Backtracking Algorithms (перебор всех комбинаций (как и в Brute Force) с постоянной проверкой того, удовлетворяет ли текущее решение установленным ограничениям или нет, иначе — возврат на шаг назад)

Репозиторий JavaScript Algorithms and Data Structures находится в активной разработке. Это значит, что там будут появляться новые имплементации алгоритмов и структур данных. Тем не менее, надеюсь уже сейчас этот репозиторий может быть вам полезен. Легкого кодинга!

Источник: habr.com

Комментарии: