Хабрахабр

Классические алгоритмы и структуры данных на 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 находится в активной разработке. Это значит, что там будут появляться новые имплементации алгоритмов и структур данных. Тем не менее, надеюсь уже сейчас этот репозиторий может быть вам полезен. Легкого кодинга!

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть