Главная страница>Связанные с программированием>Другой исходный код
Скачать

изображение

Структуры данных и алгоритмы в JavaScript

Это реализации кода из книги DSA.js и репозитория пакета NPM.

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

Интерактивные структуры данных

Оглавление

  • Установка
  • Функции
  • Что внутри
    • ? Анализ алгоритмов
    • ? Линейные структуры данных
    • ? Нелинейные структуры данных
    • ⚒ Методики алгоритмов
  • Книга
  • Часто задаваемые вопросы
  • Поддерживать
  • Лицензия

Установка

Вы можете клонировать репо или установить код из NPM: 

npm install dsa.js

а затем вы можете импортировать его в свои программы или CLI 

 const { LinkedList , Queue , Stack } = require ( 'dsa.js' ) ;

Список всех доступных структур данных и алгоритмов см. в index.js.

Функции

Алгоритмы — это важный инструментарий для каждого программиста.

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

Алгоритмы + Структуры данных = Программы.

Большинство языков программирования и библиотек действительно предоставляют реализации базовых структур данных и алгоритмов. Однако, чтобы правильно использовать структуры данных, вам необходимо знать компромиссы и выбирать лучший инструмент для работы.

Этот материал научит вас:

  • ? Применяйте стратегии для решения вопросов, связанных с алгоритмами. Никогда больше не застревать. Отлично эти интервью!
  • ✂️ Стройте эффективные алгоритмы. Научитесь разбивать проблемы на управляемые части.
  • ? Совершенствуйте свои навыки решения проблем и станьте всесторонним разработчиком, понимая фундаментальные концепции информатики.
  • ? Охватите важные темы, такие как большое время работы, структуры данных и алгоритмы, которые необходимо знать. Реализуйте более 10 структур данных с нуля.

Что внутри

Весь код и пояснения доступны в этом репозитории. Вы можете просмотреть ссылки и примеры кода из папки (src). Однако примеры встроенного кода не расширены (из-за ограничений asciidoc Github), но вы можете проследить путь и увидеть реализацию.

Примечание. Если вы предпочитаете воспринимать информацию более линейно, вам больше подойдет формат книги.

Темы разделены на четыре основные категории, как вы можете видеть ниже:

? Анализ алгоритмов

Самородки информатики без всякой ерунды. (Нажмите, чтобы развернуть)

Самородки информатики без всякой ерунды

Научитесь рассчитывать время выполнения на примерах кода

Перевод строк кода на приблизительное количество операций

Узнайте, как сравнивать алгоритмы, используя нотацию Big O. (Нажмите, чтобы развернуть)

Узнайте, как сравнивать алгоритмы, используя нотацию Big O.

Сравнение алгоритмов с использованием нотации Big O

Допустим, вы хотите найти дубликаты в массиве. Используя нотацию Big O, мы можем сравнивать разные решения, которые решают одну и ту же проблему, но имеют огромную разницу в том, сколько времени на это потребуется.

  • Оптимальное решение с использованием карты
  • Поиск дубликатов в массиве (наивный подход)
8 примеров, объясняющих с помощью кода, как вычислять временную сложность. (Нажмите, чтобы развернуть)

8 примеров, объясняющих с помощью кода, как вычислять временную сложность

Наиболее распространенные временные сложности

изображение

График временной сложности

Наиболее распространенные временные сложности

? Линейные структуры данных

Понимать все тонкости наиболее распространенных структур данных. (Нажмите, чтобы развернуть)

Понимать все тонкости наиболее распространенных структур данных.

  • Массивы: встроены в большинство языков, поэтому здесь не реализованы. Массив Временная сложность

  • Связанный список: каждый узел данных имеет ссылку на следующий (и предыдущий). Код | Временная сложность связанного списка

  • Очередь: данные передаются по принципу «первым пришел — первым обслужен» (FIFO). Код | Сложность времени в очереди

  • Стек: данные передаются по принципу «последним пришел — первым обслужен» (LIFO). Код | Сложность времени стека

Когда использовать массив или связанный список. Знайте компромиссы. (Нажмите, чтобы развернуть)

Когда использовать массив или связанный список. Знайте компромиссы

Используйте массивы, когда…

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

Используйте связанные списки, когда:

  • Вы будете получать доступ к своим данным последовательно.
  • Вы хотите экономить память и выделять ее только по мере необходимости.
  • Вам нужно постоянное время для удаления/добавления крайностей списка.
  • когда требования к размеру неизвестны – динамическое преимущество размера
Создайте список, стек и очередь. (Нажмите, чтобы развернуть)

Создайте список, стек и очередь с нуля

Создайте любую из этих структур данных с нуля:

  • Связанный список
  • Куча
  • Очередь

? Нелинейные структуры данных

Поймите одну из самых универсальных структур данных: хэш-карты. (Нажмите, чтобы развернуть)

ХэшМапы

Узнайте, как реализовать различные типы карт, такие как:

  • Хэшмап
  • ДеревоКарта

Также узнайте разницу между различными реализациями Карт:

  • HashMap более экономичен по времени. TreeMap более экономичен.
  • Сложность поиска TreeMap составляет O(log n) , а оптимизированный HashMap — в среднем O(1) .
  • Ключи HashMap располагаются в порядке вставки (или в случайном порядке, в зависимости от реализации). Ключи TreeMap всегда отсортированы.
  • TreeMap бесплатно предлагает некоторые статистические данные, такие как: получить минимум, получить максимум, медиану, найти диапазоны ключей. HashMap этого не делает.
  • TreeMap всегда имеет гарантию O(log n) , тогда как HashMap s имеет амортизированное время O(1) , но в редком случае перефразирования потребуется O(n) .
Знать свойства графов и деревьев. (Нажмите, чтобы развернуть)

Знать свойства графов и деревьев.

Графики

Знайте все свойства графиков с множеством изображений и иллюстраций.

пример графика с аэропортами США

Графы : узлы данных, которые могут иметь соединение или ребро с нулем или несколькими соседними узлами. В отличие от деревьев, узлы могут иметь несколько родителей — циклов. Код | Временная сложность графика

Деревья

Изучите все виды деревьев и их свойства.

Свойства древовидной структуры данных

  • Деревья : узлы данных имеют ноль или более соседних узлов, то есть дочерних узлов. Каждый узел может иметь только один родительский узел, в противном случае это граф, а не дерево. Код | Документы

    • Двоичные деревья : то же, что дерево, но может иметь не более двух дочерних элементов. Код | Документы

    • Двоичные деревья поиска (BST): то же, что и двоичное дерево, но значения узлов сохраняют этот порядок left < parent < right . Код | BST Временная сложность

    • Деревья AVL : самобалансированное BST для максимизации времени поиска. Код | Документы AVL Tree | Документация по самобалансировке и повороту деревьев

    • Красно-черные деревья : самобалансированный BST, более свободный, чем AVL, для максимальной скорости вставки. Код

Реализуйте двоичное дерево поиска для быстрого поиска.

Реализуйте двоичное дерево поиска для быстрого поиска.

  • Узнайте, как добавлять, удалять или обновлять значения в дереве: вставка узла в дерево

  • Как сделать дерево сбалансированным?

От несбалансированного BST к сбалансированному BST 

 1                           2
                         /   
   2        =>           1     3
    
     3

⚒ Алгоритмический набор инструментов

Никогда не застревайте, решая проблему с помощью 7 простых шагов. (Нажмите, чтобы развернуть)

Никогда не застревайте в решении проблемы с помощью 8 простых шагов

  1. Понять проблему
  2. Создайте простой пример (пока нет крайних случаев)
  3. Решения для мозгового штурма (жадный алгоритм, разделяй и властвуй, возврат, грубая сила)
  4. Проверьте свой ответ на простом примере (мысленно)
  5. Оптимизируйте решение
  6. Напишите код. Да, теперь вы можете кодировать.
  7. Проверьте свой написанный код
  8. Проанализируйте сложность, как пространства, так и времени, и обязательно оптимизируйте дальше.

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

Освойте самые популярные алгоритмы сортировки (сортировка слиянием, быстрая сортировка и т. д.) (Нажмите, чтобы развернуть)

Освойте самые популярные алгоритмы сортировки

Мы собираемся изучить три основных алгоритма сортировки O(n^2), которые имеют низкие накладные расходы:

  • Пузырьковая сортировка. Код | Документы

  • Сортировка вставками. Код | Документы

  • Сортировка выбором. Код | Документы

а затем обсудим эффективные алгоритмы сортировки O(n log n), такие как:

  • Сортировка слиянием. Код | Документы

  • Быстрая сортировка. Код | Документы

Изучите различные подходы к решению таких задач, как «разделяй и властвуй», динамическое программирование, жадные алгоритмы и возврат. (Нажмите, чтобы развернуть)

Изучите различные подходы к решению алгоритмических задач.

Мы собираемся обсудить следующие методы решения алгоритмических задач:

  • Жадные алгоритмы: делает жадный выбор, используя эвристику, чтобы найти лучшее решение, не оглядываясь назад.
  • Динамическое программирование: метод ускорения рекурсивных алгоритмов при наличии множества перекрывающихся подзадач . Он использует мемоизацию , чтобы избежать дублирования работы.
  • Разделяй и властвуй: разделите проблемы на более мелкие части, решайте каждую подзадачу, а затем объединяйте результаты.
  • Возврат: поиск всех (или некоторых) возможных путей. Однако он останавливается и возвращается , как только заметит, что текущее решение не работает.
  • Грубая сила : генерирует все возможные решения и пробует их все. (Используйте его как последнее средство или как отправную точку).

Часто задаваемые вопросы

Как бы я применил их в своей повседневной работе? (Нажмите, чтобы развернуть)

Нам, программистам, приходится решать проблемы каждый день. Если вы хотите хорошо решать проблемы, полезно знать о широком спектре решений. Зачастую эффективнее изучить существующие ресурсы, чем найти ответ самостоятельно. Чем больше у вас инструментов и практики, тем лучше. Эта книга поможет вам понять компромиссы между структурами данных и рассуждать о производительности алгоритмов.

Почему вы создали этот репозиторий/книгу?

Книг об алгоритмах в JavaScript не так много. Этот материал восполняет этот пробел. А еще это хорошая практика :)

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

Да, откройте проблему или задайте вопросы на [slack-канале](https://dsajs-slackin.herokuapp.com).

Книга

Этот проект также доступен в книге. Вы получите красиво отформатированный PDF-файл с более чем 180 страницами + версии ePub и Mobi.

Поддерживать

Свяжитесь со мной в одном из следующих мест!

  • Твиттер @iAmAdrianMejia
  • Общайтесь на dsajs.slack.com

Лицензия

Расширять
Дополнительная информация
Связанные приложения
Рекомендуем вам
Связанные новости Все