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

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

Например, представьте, что у вас есть небольшой замок с 4 цифрами от 0 до 9. Вы забыли свою комбинацию, но не хотите покупать другой замок. Поскольку вы не можете вспомнить ни одну из цифр, вы должны использовать метод грубой силы, чтобы открыть замок.

Итак, вы устанавливаете все числа обратно в 0 и пробуете их одно за другим: 0001, 0002, 0003 и так далее, пока оно не откроется. В худшем случае потребуется 104 или 10 000 попыток найти вашу комбинацию.

Классическим примером в информатике является задача коммивояжера (TSP). Предположим, продавцу нужно посетить 10 городов по всей стране. Как определить порядок посещения этих городов, чтобы минимизировать общее пройденное расстояние?

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

Временная сложность грубой силы O (m n ) , которую иногда записывают как O (n * m). Итак, если бы мы попытались найти строку из «n» символов в строке из «m» символов, используя грубую силу, нам потребовалось бы n * m попыток.

Подробнее об алгоритмах

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

Вот как их определяет Википедия:

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

Есть определенные требования, которым должен соответствовать алгоритм:

  1. Определенность: каждый шаг в процессе четко сформулирован.
  2. Эффективная вычислимость: каждый шаг процесса может быть выполнен компьютером.
  3. Конечность: программа в конечном итоге будет успешно завершена.

Некоторые распространенные типы алгоритмов включают:

  • алгоритмы сортировки
  • алгоритмы поиска
  • алгоритмы сжатия.

Классы алгоритмов включают

  • График
  • Динамическое программирование
  • Сортировка
  • Поиск
  • Струны
  • Математика
  • Вычислительная геометрия
  • Оптимизация
  • Разное.

Хотя технически это не класс алгоритмов, структуры данных часто группируются вместе с ними.

Эффективность

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

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

Алгоритмы сортировки

Алгоритмы сортировки бывают разных видов в зависимости от ваших потребностей. Вот некоторые, очень распространенные и широко используемые:

Быстрая сортировка

Нет обсуждения сортировки, которое можно завершить без быстрой сортировки. Вот основная концепция: быстрая сортировка

Сортировка слиянием

Алгоритм сортировки, основанный на концепции объединения отсортированных массивов в один отсортированный массив. Подробнее об этом здесь: Mergesort

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

Книги об алгоритмах в JavaScript:

Структуры данных в JavaScript

  • Бесплатная книга о структурах данных в JavaScript
  • GitBook

Изучение структур данных и алгоритмов JavaScript - второе издание

  • Охватывает объектно-ориентированное программирование, прототипное наследование, алгоритмы сортировки и поиска, быструю сортировку, сортировку слиянием, деревья двоичного поиска и сложные концепции алгоритмов.
  • Amazon
  • ISBN-13: 978-1785285493

Структуры данных и алгоритмы с JavaScript: внедрение классических вычислительных подходов в Интернет

  • Охватывает алгоритмы рекурсии, сортировки и поиска, связанные списки и деревья двоичного поиска.
  • Amazon
  • ISBN-13: 978-1449364939