Грокаем алгоритмы на javascript

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Реализация задач из книги про алгоритмы

EnigmaSn/grokking-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация примеров и задач из книги Грокаем Алгоритмы на Javascript

Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?

Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Реализация задач из книги про алгоритмы

datsenko-md/grokking-algorithms-js

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация примеров и задач из книги Грокаем Алгоритмы на Javascript

Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?

Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Grokking Algorithms written in Javascript

dtr200/grokking-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

readme.md

That’s how i implemented algorithms and some data structures in Javascript. I used «Grokking algorithms» from Aditya Bhargava.

• Binary search tree
• Binary search
• Breadth-first search
• Dijkstra’s algorithm
• Greedy algorithm
• Hash table
• Quick sort
• Selection sort

Моя реализация следующих алгоритмов и структур данных на основе книги «Грокаем Алгоритмы» А. Бхаргава:

• Бинарное дерево поиска
• Бинарный поиск
• Поиск в ширину
• Алгоритм Дейкстры
• Жадный алгоритм
• Хеш-таблица
• Быстрая сортировка
• Сортировка выбором

About

Grokking Algorithms written in Javascript

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Aditya Bhargava. Grokking Algoritms. A summary of the book with java script examples.

KiraJS/grokking-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Адитья Бхаргава. Грокаем алгоритмы. Конспект книги с примерами реализации алгоритмов на java script.

Глава 1. Знакомство с алгоритмами

Алгоритм на входе получает отсортированный список элементов. Возвращает позицию искомого элемента или null.

Пример: игра «угадай число». Загадано число от 1 до 100. При каждой попытке возвращается ответ: «мало», «много» или «угадал». Плохой способ – перебирать все числа подряд. При самом отрицательном сценарии потребуется 100 попыток. Эффективный способ – начнем с 50. Если мало, то пробуем 75. Если много, то 63 и тд, каждый раз исключая половину оставшихся возможных вариантов. Какое бы число не было задумано, его можно угадать не более чем за 7 попыток.

При простом поиске из 240 000 вариантов может потребоваться 240 000 попыток. При бинарном — максимум 18. Для списка из n элементов простой поиск занимает n шагов, бинарный log2n шагов.

Логарифм по смыслу противоположен возведению в степень. Логарифм по основанию 10 от 100 означает в какую степень нужно возвести 10, чтобы получить 100. Ответ 10

В нотации «О большое»(об этом позже), log всегда означает 2. Для списка из 8 элементов log8 == 3, тк 2^3 === 8.

Бинарный поиск работает только с отсортированным списком.

Скорость измеряется не временем, а ростом кол-ва операций.

Если максимальное к-во попыток совпадает с размером списка, при простом поиске, время выполнения — линейное время пыполнения.

При бинарном поиске — поиск выполняется за логарифмическое время.

Факториальное время — ужасный ужас — при очень длинном списке, поиск становится невероятно долгим. Наример, поиск кратчайшего расстояния для того, чтобы объехать n городов: 5 городов — 120 операций, 6 городов — 720, 7 городов — 5040.

линейное время — O(n)

логарифмическое время — O(log n)

факториальное время — O(n!)

Глава 2. Сортировка выбором

Память компьютера можно представить в виде огромного шкафа с множеством ящиков. У каждого ящика есть адрес. Когда требуется сохранить в памяти какое-то значение, мы запрашиваем у компьютера место в памяти, а он выдает адрес для сохранения значения. Если нужно сохранить несколько значений, есть 2 основных способа: массивы и связные списки.

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

Получить запись быстрее можно из массива — обратиться по нужному адресу. При такой же операции со списком нужно пройти по всей цепочке. С записью — наоборот. Нужна всего одна операция для записи значения в список и n операций для записи в массив.

чтение из списка – O(n) запись в список – O(1) удаление из списка – O(1)

чтение из массива – O(1) запись в массив – O(n) удаление из массива – O(n)

Легкий для понимания алгоритм, но очень медленно работает – O(n^2); Каждый раз перебирается n элементов-1

Рекурсия — вызов функции самой себя. Состоит из двух частей: базового и рекурсивного случая. В базовом — условие выхода.

Под вызов каждой функции определяется блок в памяти для всех переменных. Блоки определяются в стек. Вызов ф-и из другой ф-и приостанавливает ее действие — частично завершенное состояние.

Глава 4. Быстрая сортировка

Работает быстрее сортировки выбором и часто применяется. Базовый случай — пустой массив или массив из одного элемента. O(n log n) – в среднем. В худшем случае – O(n^2); Зависит от опорного элемента.

Хэш-функция – функция, которая получает строку(набор байтов) и возвращает число. Хэш-таблицы – структура данных, связывающая ключи со значениями. O(1) – в среднем. Отлично подходят для хранения кэша.

Коллизия — ситуация, когда двум ключам назначается один элемент массива. Простейшее решение – связный список в этом элементе. Хорошая хэш-функция создает минимальное кол-во коллизий.

Граф моделирует набор связей. Каждый граф состоит из узлов и ребер.

Этот алгоритм отвечает на два вопроса: существует ли путь от одного узла к другому и какой путь кратчайший. Поиск производится сначала по связям первого уровня, потом второго урвня и тд. Связи, по которым нужно продолжать поиск добавляются в список и образуют очередь. Очередь относится к категории структур FIFO (First In, First Out).

Время выполнения – O(V+E) V – кол-во вершин, E – кол-во ребер;

Дерево — граф, в котором нет ребер, указывающих в обратном направлении

Глава 7. Алгоритм Дейкстры

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

На каждом шаге алгоритма выбирается локальное оптимальное решение. В итоге получается глобально-оптимальное. Время выполнения – O(n^2)

About

Aditya Bhargava. Grokking Algoritms. A summary of the book with java script examples.

Источник