Практически всегда помогут решить проблему: 6 алгоритмов, которые должен знать каждый разработчик
Разработчик Ричард Уэрпам в своем блоге на Medium признается, что он не большой поклонник структур данных и алгоритмов. Но поработав над разными проектами, обнаружил, что есть шесть важных алгоритмов. Они почти всегда могут помочь решить проблему. О них он и рассказывает в этой статье. Передаем ему слово.
1 Алгоритм сортировки
Что такое сортировка? Это алгоритм, упорядочивающий элементы в списке.
Важные алгоритмы сортировки:
- Cортировка пузырьком: самый простой алгоритм сортировки, работающий путем сравнения смежных элементов и их замены, если они размещены неправильно.
- Сортировка слиянием: техника сортировки, использующая стратегию «разделяй и властвуй».
- Быстрая сортировка: популярный алгоритм сортировки, выполняющий в среднем
n log n
сравнений при сортировке массива изn
элементов. Это очень эффективный и быстрый алгоритм. - Сортировка кучей: происходит с помощью визуализации элементов массива как особого типа полного бинарного дерева (кучи).
2 Алгоритм поиска
Что такое поиск? Это алгоритм, находящий элемент в наборе данных.
Важные алгоритмы поиска:
- Двоичный поиск: использует стратегию «разделяй и властвуй». Отсортированный список делится на две половины, а элемент сравнивается со средним списком.
- Поиск в ширину (BFS): алгоритм обхода графа, который начинает с корневого узла и исследует все соседние узлы.
- Поиск в глубину (DFS): этот алгоритм начинает с первого узла графа и идет все глубже и глубже, пока мы не найдем целевой узел или узел без потомков.
3 Динамическое программирование
Динамическое программирование (DP) — это алгоритмическая техника для решения проблемы оптимизации. Для этого ее разбивают на более простые подпроблемы и считают, что оптимальное решение общей проблемы зависит от оптимального решения подпроблем.
4 Алгоритм рекурсии
Рекурсия — это техника решения проблем, в которой решение зависит от меньших случаев той же проблемы. Вычисление факториалов — классический пример рекурсивного программирования.
В каждой рекурсивной программе есть базовая последовательность шагов:
- Настройте алгоритм. Рекурсивные программы часто требуют исходного значения. Для этого используют параметр, переданный в функцию или нерекурсивную шлюзу, которая устанавливает начальные значения для рекурсивного вычисления.
- Убедитесь, что обрабатываемые текущие значения соответствуют базовому случаю. Если да, обработайте значение и возвратите его.
- Перефразируйте решения с точки зрения меньшей или более простой подпроблемы или подпроблем.
- Примените алгоритм для подзадачи.
- Чтобы сформулировать ответ, объедините результаты.
- Верните результаты.
5 Разделяй и властвуй
Алгоритм «Разделяй и властвуй» рекурсивно делит проблему на две или более подпроблем одного или родственного типа, пока они не станут достаточно простыми для решения.
Алгоритм «Разделяй и властвуй» требует следующих шагов:
- разделите исходную проблему на подпроблемы;
- решайте каждую подпроблему поочередно, рекурсивно;
- объедините решение подпроблем, чтобы получить решение всей проблемы.
6 Хеширование
Хеширование — это техника или процесс, использующий хеш-функцию для отображения ключей и значений в хеш-таблице. Это делается для более быстрого доступа к элементам. Эффективность отображения определяется эффективностью хеш-функции.
Вывод
Сейчас существует очень много алгоритмов разной сложности. Иногда сложно определить, какие из них обязательно нужно знать разработчику. Зачастую это зависит от личных предпочтений и сферы работы. Но в этой статье — те алгоритмы, которые вам точно понадобятся.
Автор: Ричард Уэрпам
Текст адаптировала Евгения Козловская
Сообщить об опечатке
Текст, который будет отправлен нашим редакторам: