Véletlenszerű vagy rekurzív algoritmus
A véletlenszerű algoritmusok beépítik a véletlenszerűség érzését a logikájába azáltal, hogy véletlenszerű döntéseket hoznak az algoritmus végrehajtása során. Ennek a véletlenszerűségnek köszönhetően az algoritmus viselkedése még egy fix bemenetnél is megváltozhat. Sok probléma esetén a randomizált algoritmusok nyújtják a legegyszerűbb és leghatékonyabb megoldást. A rekurzív algoritmusok azon az elgondoláson alapulnak, hogy a probléma megoldása megtalálható azáltal, hogy megoldásokat találnak ugyanazon probléma kisebb részproblémáira. 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 rekurziót.
Mi az a véletlenszerű algoritmus?
A véletlenszerű algoritmusok a véletlenszerűség érzését foglalják magukba azáltal, hogy véletlenszerű döntéseket hoznak, amelyek irányítják az algoritmus végrehajtását. Ezt általában úgy végezzük, hogy további bemenetként egy véletlenszerű számgenerátor által generált véletlenszám-készletet veszünk. Emiatt az algoritmus viselkedése még egy fix bemenetnél is megváltozhat. A Quicksort egy széles körben ismert algoritmus, amely a véletlenszerűség fogalmát használja, és amelynek futási ideje O (n log n), függetlenül a bemeneti tulajdonságoktól. Továbbá randomizált inkrementális építési módszert alkalmaznak olyan szerkezetekhez, mint a domború hajótest a számítási geometriában. Ebben a módszerben a bemeneti pontokat véletlenszerűen permutálják, majd egyesével illesztik be a struktúrába. A randomizált algoritmus megvalósítása viszonylag egyszerű, mint egy determinisztikus algoritmus végrehajtása ugyanarra a problémára. A randomizált algoritmus tervezésének legnagyobb kihívása az idő és a tér komplexitásának aszimptotikus elemzésének elvégzése.
Mi az a rekurzív algoritmus?
A rekurzív algoritmusok azon az elgondoláson alapulnak, hogy a probléma megoldása megtalálható azáltal, hogy megoldásokat találnak ugyanazon probléma kisebb részproblémáira. Rekurzív algoritmusban egy függvény önmagának korábbi verziója alapján kerül meghatározásra. Fontos megjegyezni, hogy ennek az önreferenciának felmondási feltételnek kell lennie, hogy elkerülje önmagának örökre történő hivatkozását. A felmondás feltételeit ellenőrizzük, mielőtt hivatkoznánk magára. A rekurzív algoritmus kezdeti lépése a probléma rekurzív definíciójának alapklauzulájához kapcsolódik. A kezdeti lépést követő lépések a probléma induktív záradékaihoz kapcsolódnak. A rekurzív algoritmusok sok helyzetben egyszerűbb megoldást nyújtanak, és közelebb állnak a természetes gondolkodásmódhoz, mint ugyanazon probléma iteratív algoritmusai. De általában,a rekurzív algoritmusok több memóriát igényelnek, és számítási szempontból drágák.
Mi a különbség a véletlenszerű és a rekurzív algoritmus között?
A véletlenszerű algoritmusok olyan algoritmusok, amelyek véletlenszerűség érzetét alkalmazzák véletlenszerű döntések meghozatalával, amelyek befolyásolhatják az algoritmus végrehajtását, míg a rekurzív algoritmusok olyan algoritmusok, amelyek azon az elgondoláson alapulnak, hogy egy problémára megoldást lehet találni kisebb részproblémák megoldásának megkeresésével. ugyanannak a problémának. A véletlenszerű algoritmusok véletlenszerűsége miatt az algoritmus viselkedése akár ugyanazon bemenetnél is változhat (az algoritmus különböző végrehajtásaiban). De ez rekurzív algoritmusokban nem lehetséges, és a rekurzív algoritmus viselkedése azonos lenne egy fix bemenetnél.
