Különbség a randomizált és a rekurzív algoritmus között
Véletlenszerű vs rekurzív algoritmus végrehajtása során A randomizált algoritmusok a logikai véletlenszerűség érzetét véletlenszerű választási lehetőségekkel látják el az algoritmus végrehajtása során. E véletlenszerűség miatt az algoritmus viselkedése akár fix bemenet esetén is megváltozhat. Számos probléma esetén a randomizált algoritmusok a legegyszerűbb és leghatékonyabb megoldásokat kínálják. A rekurzív algoritmusok azon az elgondoláson alapulnak, hogy egy probléma megoldása megtalálható az ugyanazon probléma kisebb alproblémáinak megoldásával. A rekurziót széles körben használják a számítástechnika problémáinak megoldására, és számos magas szintű programozási nyelv támogatja a rekurzív tevékenységet.
Mi a randomizált algoritmus?A randomizált algoritmusok magukban foglalják a véletlenszerűség érzését azáltal, hogy véletlenszerű döntéseket hoznak létre, amelyek az algoritmus végrehajtását vezérlik. Ezt tipikusan úgy végzik el, hogy egy véletlen számok készletét egy pszeudorandom számgenerátorból generálják. Ennek következtében az algoritmus viselkedése akár rögzített bemenet esetén is változhat. A Quicksort egy széles körben ismert algoritmus, amely a véletlenszerűség fogalmát használja, és az O (n log n) futási ideje függetlenül a bemeneti tulajdonságoktól. Továbbá véletlenszerű inkrementális építési módszert alkalmaznak olyan épületszerkezeteknél, mint a konvex hajótest a számítási geometriában. Ebben a módszerben a bemeneti pontok véletlenszerűen átkeverednek, majd egyenként beillesztik a struktúrába. A véletlenszerű algoritmus végrehajtása viszonylag egyszerű, mint egy determinisztikus algoritmus végrehajtása ugyanarra a problémára. A véletlenszerű algoritmusok tervezésének legnagyobb kihívása az idő- és térkomplexitás aszimptotikus elemzésében rejlik.
A rekurzív algoritmusok azon az elgondoláson alapulnak, hogy egy probléma megoldása megtalálható az ugyanazon probléma kisebb alproblémáinak megoldása révén. Egy rekurzív algoritmusban egy függvényt a korábbi verziója határoz meg. Fontos megjegyezni, hogy ez az önkifejezésnek rendelkeznie kell egy megszüntetési feltétellel, hogy elkerülje az örökre való hivatkozást. A lezárási állapotot ellenőrizzük, mielőtt hivatkoznánk rá. A rekurzív algoritmus kezdeti lépése a probléma rekurzív definíciójának alapmondatához kapcsolódik. A kezdeti lépést követő lépések a probléma induktív záradékaival kapcsolatosak. A rekurzív algoritmusok sok helyzetben egyszerűbb megoldást nyújtanak, és közelebb áll a természetes gondolkodáshoz, mint az ugyanazon probléma iteratív algoritmusa. De általában a rekurzív algoritmusok több memóriát igényelnek, és számítással drágák.
Véletlenszerű algoritmusok olyan algoritmusok, amelyek a véletlenszerűséget használják olyan véletlenszerű döntések végrehajtásával, amelyek befolyásolhatják az algoritmus végrehajtását, míg a rekurzív algoritmusok olyan algoritmusok, amelyek azon a gondolaton alapulnak, hogy egy probléma megoldása megtalálható megoldások megtalálásával ugyanazon probléma kisebb alproblémái. A véletlen algoritmusok véletlenszerűsége miatt az algoritmus viselkedése ugyanilyen bemenet esetén is változhat (az algoritmus különböző kiviteleiben). De ez nem lehetséges rekurzív algoritmusokban, és a rekurzív algoritmus viselkedése ugyanaz lenne a rögzített bemenet számára.
