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