Рандомизированный и рекурсивный алгоритм
Рандомизированные алгоритмы включают в свою логику ощущение случайности, делая случайный выбор во время выполнения алгоритма. Из-за этой случайности поведение алгоритма может меняться даже при фиксированном входе. Для многих задач рандомизированные алгоритмы обеспечивают самые простые и эффективные решения. Рекурсивные алгоритмы основаны на идее, что решение проблемы может быть найдено путем поиска решений более мелких подзадач той же самой проблемы. Рекурсия широко используется для поиска решений проблем в информатике, и многие языки программирования высокого уровня поддерживают рекурсию.
Что такое рандомизированный алгоритм?
Рандомизированные алгоритмы включают ощущение случайности, делая случайный выбор, который определяет выполнение алгоритма. Обычно это делается путем использования в качестве дополнительных входных данных набора случайных чисел, сгенерированных генератором псевдослучайных чисел. Благодаря этому поведение алгоритма может меняться даже при фиксированном входе. Быстрая сортировка - это широко известный алгоритм, в котором используется концепция случайности, и его время работы равно O(n log n) независимо от входных свойств. Кроме того, метод рандомизированного пошагового построения используется для построения таких конструкций, как выпуклая оболочка в вычислительной геометрии. В этом методе входные точки случайным образом переставляются, а затем вставляются одна за другой в структуру. Реализация рандомизированного алгоритма относительно проста, чем реализация детерминированного алгоритма для той же задачи. Самая большая проблема при разработке рандомизированного алгоритма заключается в выполнении асимптотического анализа временной и пространственной сложности.
Что такое рекурсивный алгоритм?
Рекурсивные алгоритмы основаны на идее, что решение проблемы может быть найдено путем поиска решений более мелких подзадач той же самой проблемы. В рекурсивном алгоритме функция определяется в терминах самой ранней версии. Важно отметить, что эта ссылка на себя должна иметь условие завершения, чтобы избежать вечной ссылки на себя. Условие завершения проверяется перед обращением к самому себе. Начальный шаг рекурсивного алгоритма связан с базовым предложением рекурсивного определения проблемы. Шаги, следующие за начальным, связаны с индуктивными положениями задачи. Рекурсивные алгоритмы обеспечивают более простое решение во многих ситуациях и ближе к естественному образу мышления, чем итерационный алгоритм для той же проблемы. Но в целом рекурсивные алгоритмы требуют больше памяти и требуют больших вычислительных ресурсов.
В чем разница между рандомизированным и рекурсивным алгоритмом?
Случайные алгоритмы - это алгоритмы, которые используют ощущение случайности, делая случайный выбор, который может повлиять на выполнение алгоритма, в то время как рекурсивные алгоритмы - это алгоритмы, основанные на идее, что решение проблемы можно найти, найдя решения более мелких подзадач одной и той же проблемы. Из-за случайности в случайных алгоритмах поведение алгоритма может меняться даже для одного и того же входа (при разных исполнениях алгоритма). Но это невозможно в рекурсивных алгоритмах, и поведение рекурсивного алгоритма будет таким же для фиксированного ввода.
