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