Практически всегда помогут решить проблему: 6 алгоритмов, которые должен знать каждый разработчик

Разработчик Ричард Уэрпам в своем блоге на Medium признается, что он не большой поклонник структур данных и алгоритмов. Но поработав над разными проектами, обнаружил, что есть шесть важных алгоритмов. Они почти всегда могут помочь решить проблему. О них он и рассказывает в этой статье. Передаем ему слово.

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

Что такое сортировка? Это алгоритм, упорядочивающий элементы в списке.

Важные алгоритмы сортировки:

• Cортировка пузырьком: самый простой алгоритм сортировки, работающий путем сравнения смежных элементов и их замены, если они размещены неправильно.
• Сортировка слиянием: техника сортировки, использующая стратегию «разделяй и властвуй».
• Быстрая сортировка: популярный алгоритм сортировки, выполняющий в среднем n log n сравнений при сортировке массива из n элементов. Это очень эффективный и быстрый алгоритм.
• Сортировка кучей: происходит с помощью визуализации элементов массива как особого типа полного бинарного дерева (кучи).

2 Алгоритм поиска

Что такое поиск? Это алгоритм, находящий элемент в наборе данных.

Важные алгоритмы поиска:

• Двоичный поиск: использует стратегию «разделяй и властвуй». Отсортированный список делится на две половины, а элемент сравнивается со средним списком.
• Поиск в ширину (BFS): алгоритм обхода графа, который начинает с корневого узла и исследует все соседние узлы.
• Поиск в глубину (DFS): этот алгоритм начинает с первого узла графа и идет все глубже и глубже, пока мы не найдем целевой узел или узел без потомков.

3 Динамическое программирование

Динамическое программирование (DP) — это алгоритмическая техника для решения проблемы оптимизации. Для этого ее разбивают на более простые подпроблемы и считают, что оптимальное решение общей проблемы зависит от оптимального решения подпроблем.

4 Алгоритм рекурсии

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

В каждой рекурсивной программе есть базовая последовательность шагов:

• Настройте алгоритм. Рекурсивные программы часто требуют исходного значения. Для этого используют параметр, переданный в функцию или нерекурсивную шлюзу, которая устанавливает начальные значения для рекурсивного вычисления.
• Убедитесь, что обрабатываемые текущие значения соответствуют базовому случаю. Если да, обработайте значение и возвратите его.
• Перефразируйте решения с точки зрения меньшей или более простой подпроблемы или подпроблем.
• Примените алгоритм для подзадачи.
• Чтобы сформулировать ответ, объедините результаты.
• Верните результаты.

5 Разделяй и властвуй

Алгоритм «Разделяй и властвуй» рекурсивно делит проблему на две или более подпроблем одного или родственного типа, пока они не станут достаточно простыми для решения.

Алгоритм «Разделяй и властвуй» требует следующих шагов: 

• разделите исходную проблему на подпроблемы;
• решайте каждую подпроблему поочередно, рекурсивно;
• объедините решение подпроблем, чтобы получить решение всей проблемы.

6 Хеширование

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

Вывод

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

Автор: Ричард Уэрпам

Текст адаптировала Евгения Козловская