Классификация алгоритмов
Классификация по назначению
У каждого алгоритма есть цель. Например, целью алгоритма быстрой сортировки является сортировка данных по возрастанию или убыванию. Но цели бесконечны по числу, поэтому мы группируем их по типам.
Классификация по реализации
Один и тот же алгоритм может быть реализован по разным основным принципам.
- Рекурсия или итерация
Рекурсивный алгоритм вызывает себя многократно, пока не будет выполнено условие. Это распространённый метод в функциональном программировании.
Итеративные алгоритмы используют циклы.
В зависимости от проблемы наиболее подходит та или иная реализация. Например, проблему Башен Ханоя лучше всего понимать в рекурсивной форме. Но каждая рекурсивная версия имеет итеративный эквивалент и наоборот.
- Логика или процедура
Алгоритм также можно рассматривать как управляемый логический вычет.
Логический компонент выражает аксиомы, которые будет использовать процесс, а управляющий компонент определяет, как вычеты применяются к аксиомам .
Это основа логического программирования. Чистые логические языки программирования имеют предопределённое управление, осталось выразить только аксиомы.
- Последовательный или параллельный
В общем случае предполагается, что инструкции алгоритмов выполняются одна за другой, и мы говорим о последовательном алгоритме, но они могут быть и параллельными, когда архитектура компьютера позволяет обрабатывать несколько инструкций одновременно.
При этом задача делится на подзадачи, закрепленные за разными процессорами. Итерационные алгоритмы являются распараллеливаемыми, особенно алгоритмы сортировки.
- Детерминированный или не
Детерминированные алгоритмы выполняют предопределённый процесс для решения задачи, в то время как недетерминированные алгоритмы должны угадывать лучшее решение на каждом шаге. с помощью эвристики.
Классификация по парадигме проектирования
Парадигма проектирования - область исследования или класс задач, требующих определенного типа алгоритма.
- Разделяй и властвуй
Принцип «разделяй и властвуй» рекурсивно сводит проблему к более простому случаю или набору подзадач, пока она не достигнет достаточного уровня простоты для простого решения. Алгоритм сортировки слиянием - один из примеров. Сортируемый список делится на подсписки, отсортированные отдельно .
Поиск дихотомии - еще один пример, основанный на том же принципе.
- Динамическое программирование
Кратчайший путь на взвешенном графе можно найти, используя кратчайший путь между соседними рёбрами.
Когда оптимальное решение задачи получается из оптимальных решений подзадач, динамическое программирование избегает перерасчёта уже решённых решений.
- Основное отличие от подхода «разделяй и властвуй» состоит в том, что в последнем подзадачи независимы, тогда как в динамическом программировании возможна суперпозиция.
- ПрогДинамический таран и запоминание идут рука об руку. Разница с прямой рекурсией заключается в кэшировании, или запоминании рекурсивных вызовов. Это бесполезно, когда подзадачи независимы. В противном случае запоминание таблицы ранее решённых задач уменьшает сложность от экспоненциальной до полиномиальной.
- Жадный метод
Это аналогично динамическому программированию с той разницей, что решения подзадач не должны быть известны на каждом этапе обработки. Наоборот, делается «жадный» выбор, который заключается в принятии наилучшего возможного в тот момент решения. В качестве примера можно привести алгоритм Крускала.
- Линейное программирование
Задача выражается в виде множества линейных неравенств, затем мы пытаемся максимизировать или минимизировать входные данные. Это может решить многие задачи, включая задачу о максимальном потоке на ориентированном графе, в частности, используя симплексный алгоритм.
Вариант, называемый целочисленным программированием, состоит из ограничения пространства решений целыми числами.
- Сокращение.
Состоит из превращения одной проблемы в другую, более простую в решении.
Простой пример, поиск медианы неупорядоченного списка состоит из сортировки списка первым, чтобы непосредственно извлечь медианное значение, которое находится в середине списка! Мы видим, что цель - найти самую очевидную трансформацию.
- Использование графиков
Многие задачи, в том числе и игру в шахматы, можно решить, смоделировав её как график. Используются алгоритмы исследования графов. К ним относятся алгоритмы поиска и обратного отслеживания.
- Вероятностный и эвристический
- Вероятностный
Они делают случайный выбор. - Генетический
Ищет решение проблемы, имитируя биологические эволюционные процессы, с последовательными поколениями, которые являются промежуточными решениями. Фактически это повторяет принцип выживания сильнейшего. - Эвристика
Цель - не найти оптимальное решение, а хорошее решение, если лучшее потребовало бы слишком много времени или ресурсов.
- Вероятностный
Классификация по сложности
Некоторые алгоритмы завершаются за линейное время, другие требуют экспоненциального времени, а третьи никогда не завершаются.