Рандомизиран срещу рекурсивен алгоритъм
Рандомизираните алгоритми включват чувство за случайност в своята логика, като правят произволни избори по време на изпълнението на алгоритъма. Поради тази случайност, поведението на алгоритъма може да се промени дори за фиксиран вход. За много проблеми рандомизираните алгоритми предоставят най-простите и ефективни решения. Рекурсивните алгоритми се основават на идеята, че решението на даден проблем може да бъде намерено чрез намиране на решения за по-малки подпроблеми на същия проблем. Рекурсията се използва широко за намиране на решения на проблеми в компютърните науки и много езици за програмиране на високо ниво поддържат рекурсията.
Какво е рандомизиран алгоритъм?
Рандомизираните алгоритми включват чувство за случайност, като правят произволни избори, които ръководят изпълнението на алгоритъма. Това обикновено се прави като се вземе набор от случайни числа, генерирани от генератор на псевдослучайни числа като допълнителен вход. Поради това поведението на алгоритъма може да се промени дори за фиксиран вход. Quicksort е широко известен алгоритъм, който използва концепцията за произволност и има време на работа O (n log n), независимо от входните свойства. Освен това, метод на рандомизирана инкрементална конструкция се използва за изграждане на конструкции като изпъкнал корпус в изчислителната геометрия. При този метод входните точки се подреждат на случаен принцип и след това се вмъкват една по една в структурата. Внедряването на рандомизиран алгоритъм е относително просто, отколкото прилагането на детерминиран алгоритъм за същия проблем. Най-голямото предизвикателство при проектирането на рандомизиран алгоритъм се крие в извършването на асимптотичен анализ на сложността на времето и пространството.
Какво е рекурсивен алгоритъм?
Рекурсивните алгоритми се основават на идеята, че решението на даден проблем може да бъде намерено чрез намиране на решения за по-малки подпроблеми на същия проблем. В рекурсивен алгоритъм функция се дефинира по отношение на по-ранната версия на себе си. Важно е да се отбележи, че това самопозоваване трябва да има условие за прекратяване, за да се избегне позоваването завинаги. Условието за прекратяване се проверява преди да се позове на себе си. Началната стъпка на рекурсивен алгоритъм е свързана с основната клауза на рекурсивното определение на проблема. Стъпките, които следват първоначалната стъпка, са свързани с индуктивните клаузи на проблема. Рекурсивните алгоритми осигуряват по-просто решение в много ситуации и е по-близо до естествения начин на мислене, отколкото итеративният алгоритъм за същия проблем. Но като цяло,рекурсивните алгоритми изискват повече памет и те са изчислително скъпи.
Каква е разликата между рандомизиран и рекурсивен алгоритъм?
Случайните алгоритми са алгоритми, които използват чувство за случайност, като правят произволни избори, които биха могли да повлияят на изпълнението на алгоритъма, докато рекурсивните алгоритми са алгоритми, които се основават на идеята, че решение на проблем може да бъде намерено чрез намиране на решения за по-малки подпроблеми на същия проблем. Поради случайността в случайните алгоритми, поведението на алгоритъма може да се промени дори за един и същи вход (при различни изпълнения на алгоритъма). Но това не е възможно при рекурсивните алгоритми и поведението на рекурсивния алгоритъм би било същото за фиксиран вход.
