Randomized vs Recursive Algorithm
Ang Randomized na algorithm ay nagsasama ng pakiramdam ng randomness sa logic nito sa pamamagitan ng paggawa ng mga random na pagpipilian sa panahon ng pagpapatupad ng algorithm. Dahil sa randomness na ito, maaaring magbago ang pag-uugali ng algorithm kahit para sa isang nakapirming input. Para sa maraming problema, ang mga randomized na algorithm ay nagbibigay ng pinakasimple at mahusay na mga solusyon. Ang mga recursive algorithm ay batay sa ideya na ang solusyon sa isang problema ay matatagpuan sa pamamagitan ng paghahanap ng mga solusyon sa mas maliliit na subproblema ng parehong problema. Ang recursion ay malawakang ginagamit upang makahanap ng mga solusyon sa mga problema sa computer science at maraming mga high-level na programming language ang sumusuporta sa recursion.
Ano ang Randomized Algorithm?
Isinasama ng mga randomized na algorithm ang pakiramdam ng randomness sa pamamagitan ng paggawa ng mga random na pagpipilian na gumagabay sa pagpapatupad ng algorithm. Ito ay karaniwang ginagawa sa pamamagitan ng pagkuha ng isang set ng mga random na numero na nabuo ng isang pseudorandom number generator bilang karagdagang input. Dahil dito, maaaring magbago ang pag-uugali ng algorithm kahit para sa isang nakapirming input. Ang Quicksort ay isang malawak na kilalang algorithm na gumagamit ng konsepto ng randomness at mayroon itong tumatakbong oras na O(n log n) anuman ang mga katangian ng input. Dagdag pa, ginagamit ang randomized incremental construction method para sa pagbuo ng mga istruktura tulad ng convex hull sa computation geometry. Sa pamamaraang ito, ang mga input point ay random na pinahihintulutan at pagkatapos ay isa-isang ipinasok sa istraktura. Ang pagpapatupad ng randomized na algorithm ay medyo simple kaysa sa pagpapatupad ng deterministic algorithm para sa parehong problema. Ang pinakamalaking hamon sa pagdidisenyo ng isang randomized na algorithm ay nakasalalay sa pagsasagawa ng asymptotic analysis para sa pagiging kumplikado ng oras at espasyo.
Ano ang Recursive Algorithm?
Ang mga recursive algorithm ay batay sa ideya na ang solusyon sa isang problema ay mahahanap sa pamamagitan ng paghahanap ng mga solusyon sa mas maliliit na subproblema ng parehong problema. Sa isang recursive algorithm, ang isang function ay tinukoy sa mga tuntunin ng naunang bersyon ng sarili nito. Mahalagang tandaan na ang self reference na ito ay dapat magkaroon ng kondisyon ng pagwawakas upang maiwasan ang pagre-refer sa sarili nito magpakailanman. Ang kundisyon ng pagwawakas ay sinusuri bago banggitin ang sarili nito. Ang paunang hakbang ng isang recursive algorithm ay nauugnay sa batayan ng sugnay ng recursive na kahulugan ng problema. Ang mga hakbang na sumusunod sa paunang hakbang ay nauugnay sa mga inductive clause ng problema. Ang mga recursive algorithm ay nagbibigay ng mas simpleng solusyon sa maraming sitwasyon at mas malapit ito sa natural na paraan ng pag-iisip kaysa sa iterative algorithm para sa parehong problema. Ngunit sa pangkalahatan, ang mga recursive algorithm ay nangangailangan ng mas maraming memorya at ang mga ito ay mahal sa computation.
Ano ang pagkakaiba sa pagitan ng Randomized at Recursive Algorithm?
Ang Random algorithm ay mga algorithm na gumagamit ng sense of randomness sa pamamagitan ng paggawa ng mga random na pagpipilian na maaaring makaapekto sa execution ng algorithm, habang ang recursive algorithm ay mga algorithm na nakabatay sa ideya na ang solusyon sa isang problema ay matatagpuan sa pamamagitan ng paghahanap mga solusyon sa mas maliliit na subproblema ng parehong problema. Dahil sa randomness sa mga random na algorithm, ang pag-uugali ng algorithm ay maaaring magbago kahit para sa parehong input (sa iba't ibang mga execution ng algorithm). Ngunit hindi ito posible sa mga recursive algorithm at ang pag-uugali ng isang recursive algorithm ay magiging pareho para sa isang nakapirming input.
