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

в 15:25, , рубрики: algorithm, algorithms, data structure, data structures, javascript, programming, Алгоритмы, Программирование

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

Автор: Алексей

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js