Разница между рандомизированным и рекурсивным алгоритмом

Рандомизированный и рекурсивный алгоритм

Рандомизированные алгоритмы включают чувство случайности в свою логику, делая случайные выборы во время выполнения алгоритма. Из-за этой случайности поведение алгоритма может измениться даже для фиксированного ввода. Для многих задач рандомизированные алгоритмы обеспечивают наиболее простые и эффективные решения. Рекурсивные алгоритмы основаны на идее, что решение проблемы может быть найдено путем нахождения решений меньших подзадач той же проблемы. Рекурсия широко используется для поиска решений проблем в области компьютерных наук, и многие языки программирования высокого уровня поддерживают рекурсию.

Что такое рандомизированный алгоритм?

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

Что такое рекурсивный алгоритм?

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

В чем разница между рандомизированным и рекурсивным алгоритмом?

Случайные алгоритмы - это алгоритмы, которые используют чувство случайности, делая случайные выборы, которые могут повлиять на выполнение алгоритма, в то время как рекурсивные алгоритмы - это алгоритмы, основанные на идее, что решение проблемы может быть найдено путем поиска решений для меньших подзадач. той же проблемы. Из-за случайности в случайных алгоритмах поведение алгоритма может измениться даже для одного и того же входа (в разных исполнениях алгоритма). Но это невозможно в рекурсивных алгоритмах, и поведение рекурсивного алгоритма будет таким же для фиксированного ввода.