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

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

Рандомізовані алгоритми включають почуття випадковості у свою логіку, роблячи випадкові вибори під час виконання алгоритму. Завдяки цій випадковості поведінка алгоритму може змінюватися навіть для фіксованого вводу. Для багатьох проблем рандомізовані алгоритми пропонують найпростіші та ефективні рішення. Рекурсивні алгоритми засновані на ідеї, що рішення проблеми можна знайти, знайшовши рішення для менших підзадач тієї самої проблеми. Рекурсія широко використовується для пошуку вирішення проблем інформатики, і багато мов програмування високого рівня підтримують рекурсію.

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

Рандомізовані алгоритми включають почуття випадковості, роблячи випадкові вибори, які керують виконанням алгоритму. Зазвичай це робиться, беручи набір випадкових чисел, генерованих генератором псевдовипадкових чисел, як додатковий вхід. Через це поведінка алгоритму може змінюватися навіть для фіксованого вводу. Quicksort - широко відомий алгоритм, який використовує поняття випадковості і має час роботи O (n log n) незалежно від вхідних властивостей. Далі метод рандомізованого інкрементального будівництва застосовується для будівельних конструкцій, таких як опуклий корпус, в обчислювальній геометрії. У цьому методі вхідні точки випадковим чином перестановляються і потім вставляються одна за одною до структури. Реалізація рандомізованого алгоритму порівняно проста, ніж реалізація детермінованого алгоритму для тієї ж проблеми. Найбільша проблема в розробці рандомізованого алгоритму полягає у виконанні асимптотичного аналізу для складності часу та простору.

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

Рекурсивні алгоритми засновані на ідеї, що рішення проблеми можна знайти, знайшовши рішення для менших підзадач тієї самої проблеми. У рекурсивному алгоритмі функція визначається з точки зору попередньої версії самої себе. Важливо зауважити, що ця самовідсилання повинна мати умову припинення, щоб уникнути посилання на себе назавжди. Умова припинення перевіряється перед посиланням на себе. Початковий крок рекурсивного алгоритму пов'язаний з базовим пунктом рекурсивного визначення проблеми. Етапи, що слідують за початковим кроком, пов'язані з індуктивними пунктами проблеми. Рекурсивні алгоритми дають більш просте рішення у багатьох ситуаціях, і це ближче до природного способу мислення, ніж ітеративний алгоритм для тієї ж проблеми. Але в цілому рекурсивні алгоритми вимагають більше пам'яті, і вони обчислювально дорогі.

Яка різниця між рандомізованим та рекурсивним алгоритмом?

Випадкові алгоритми - це алгоритми, які використовують почуття випадковості, роблячи випадкові вибори, які можуть вплинути на виконання алгоритму, тоді як рекурсивні алгоритми - це алгоритми, які ґрунтуються на ідеї, що рішення проблеми можна знайти шляхом пошуку рішення менших підзадач тієї ж проблеми. Через випадковість у випадкових алгоритмах поведінка алгоритму може змінюватись навіть для одного і того ж входу (у різних виконання алгоритму). Але це неможливо в рекурсивних алгоритмах, і поведінка рекурсивного алгоритму було б однаковим для фіксованого вводу.