Классификация алгоритмов с примерами

Существует много способов классификации алгоритмов, и некоторые из них показаны ниже:

1. Метод реализации
2. Метод проектирования
3. Другие классификации

Классификация по способу реализации:

1. Рекурсия или итерация

• Арекурсивный алгоритм — это алгоритм, который многократно вызывает сам себя до тех пор, пока не будет выполнено базовое условие. Это распространенный метод, используемый в функциональных языках программирования, таких как C, C++ и т. д.
• Итерационные алгоритмы используют такие конструкции, как циклы, а иногда и другие структуры данных, такие как стеки и очереди, для решения проблем.
• Некоторые задачи подходят для рекурсивных, а другие подходят для итеративных. Например, задача о ханойских башнях может быть легко понята в рекурсивной реализации. Каждая рекурсивная версия имеет итеративную версию и наоборот.

2. Процедурный или декларативный (непроцессуальный) -

• В декларативных языках программирования мы говорим, что хотим, не говоря, как это сделать.
• В процедурном программировании мы должны указать точные шаги для получения результата. Например, SQL является более декларативным, чем процедурным, поскольку в запросах не указываются шаги для получения результата. Примеры процедурных языков включают C, PHP и PERL.

3. Последовательный, параллельный или распределенный.

• В общем, при обсуждении алгоритмов мы предполагаем, что компьютеры выполняют по одной инструкции за раз. Такие алгоритмы называются последовательными.
• Параллельные алгоритмы используют преимущества компьютерной архитектуры для одновременной обработки нескольких инструкций. Они делят проблему на подзадачи и обслуживают их для нескольких процессоров или потоков. Итерационные алгоритмы обычно распараллелены.
• Если параллельные алгоритмы распределены по разным машинам, то мы называем такие алгоритмы распределенными алгоритмами.

4. Детерминированный или недетерминированный.

• Детерминистические алгоритмы решают проблему с заранее определенным процессом, тогда как недетерминированные алгоритмы угадывают лучшее решение на каждом этапе с помощью эвристики.

5. Точный или приблизительный-

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

Классификация по методу проектирования:

Другой способ классификации алгоритмов — по методу их разработки.

1. Жадный метод.

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

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

Стратегия «разделяй и властвуй» решает проблему путем:

1. Разделение: разбивка проблемы на подзадачи, которые сами по себе являются более мелкими экземплярами проблемы того же типа.
2. Рекурсия: Рекурсивное решение этих подзадач.
3. Conquer: Соответствующим образом комбинируя их ответы.

Примеры: алгоритмы сортировки слиянием и бинарного поиска.

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

• Динамическое программирование (DP) и запоминание работают вместе. Разница между DP и разделяй и властвуй заключается в том, что в случае последнего между подзадачами нет зависимости, тогда как в DP подзадачи будут перекрываться. Используя запоминание [ведение таблицы для уже решенных подзадач], DP снижает экспоненциальную сложность до полиномиальной (O (n2), O (n3) и т. Д.) Для многих задач.
• Разница между динамическим программированием и рекурсией заключается в запоминании рекурсивных вызовов. Когда подзадачи самостоятельны и нет повторения, запоминание не происходит.
• Помогите, следовательно, динамическое программирование не является решением всех проблем.
• Используя запоминание [ведение таблицы уже решенных подзадач], динамическое программирование снижает сложность с экспоненциальной до полиномиальной.

4. Линейное программирование-

• В линейном программировании существуют неравенства с точки зрения входных данных и максимизации (или минимизации) некоторой линейной функции входных данных.
• Многие проблемы (например, максимальный поток для ориентированных графов) можно решать с помощью линейного программирования.

5. Сокращение [Преобразуй и властвуй]

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

Другие классификации:

1. Классификация по областям исследований-

• В компьютерных науках каждая область имеет свои проблемы и нуждается в эффективных алгоритмах. Примеры: алгоритмы поиска, алгоритмы сортировки, алгоритмы слияния, численные алгоритмы, графовые алгоритмы, строковые алгоритмы, геометрические алгоритмы, комбинаторные алгоритмы, машинное обучение, криптография, параллельные алгоритмы, алгоритмы сжатия данных, методы синтаксического анализа и многое другое.

2. Классификация по сложности-

• В этой классификации алгоритмы классифицируются по времени, затрачиваемому на поиск решения, в зависимости от размера входных данных. Некоторые алгоритмы требуют линейной временной сложности (O(n)), другие требуют экспоненциального времени, а некоторые никогда не останавливаются. Обратите внимание, что некоторые задачи могут иметь несколько алгоритмов разной сложности.

3. Рандомизированные алгоритмы.

• Несколько алгоритмов делают выбор случайным образом. Для некоторых задач самые быстрые решения должны включать случайность. Пример: Быстрая сортировка.