Randomizált algoritmusok ismertetése, kategorizálása és hatékonysági elemzése

Abstract

A dolgozat célja a randomizált algoritmusok részletes bemutatása és kategorizálása. Illetve a kiválasztott véletlent használó algoritmusok összehasonlítása a determinisztikus megfelelőikkel. Az algoritmusokat felhasználási terület, probléma típus, hatékonyság, pontosság, helyigény, robusztusság és implementálhatóság szempontjából vizsgáltam. Az összehasonlításhoz konkrét példákat választottam, amelyek a bináris keresés, prímszámtesztek, valamint a gyorsrendezés. Az eredmények azt mutatják, hogy bizonyos esetekben a randomizált algoritmusok hatékonyabbak és rugalmasabbak, ami alátámasztja, hogy egyes problématípusoknál különösen előnyösek lehetnek. Az elemzés a Big-O kalkulátor és szakirodalmi források alapján készült.