Atšķirība starp randomizēto un rekursīvo algoritmu

Randomizēts vs rekursīvs algoritms

Nejaušināti algoritmi savā loģikā iekļauj nejaušības sajūtu, algoritma izpildes laikā veicot nejaušas izvēles. Šīs nejaušības dēļ algoritma izturēšanās var mainīties pat fiksētas ieejas gadījumā. Daudzām problēmām nejaušināti algoritmi nodrošina visvienkāršākos un efektīvākos risinājumus. Rekursīvie algoritmi ir balstīti uz ideju, ka problēmas risinājumu var atrast, atrodot risinājumus mazākām tās pašas problēmas apakšproblēmām. Rekursija tiek plaši izmantota, lai atrastu risinājumus datorzinātnes problēmām, un daudzas augsta līmeņa programmēšanas valodas atbalsta rekursiju.

Kas ir nejaušs algoritms?

Nejaušināti algoritmi iekļauj nejaušības sajūtu, veicot nejaušas izvēles, kas virza algoritma izpildi. Parasti to veic, par papildu ieeju ņemot nejaušu skaitļu kopu, ko ģenerējis pseidodēmisku numuru ģenerators. Sakarā ar to algoritma izturēšanās var mainīties pat fiksētas ieejas gadījumā. Quicksort ir plaši pazīstams algoritms, kas izmanto nejaušības jēdzienu, un tā darbības laiks ir O (n log n) neatkarīgi no ieejas īpašībām. Turklāt tādu konstrukciju kā izliekts korpuss aprēķinu ģeometrijā tiek izmantota nejaušināta inkrementālā konstrukcijas metode. Šajā metodē ievades punkti tiek nejauši mainīti un pēc tam pa vienam ievietoti struktūrā. Nejaušināta algoritma ieviešana ir samērā vienkārša nekā šīs pašas problēmas deterministiskā algoritma ieviešana. Lielākais izaicinājums, veidojot nejaušinātu algoritmu, ir asimptotiskas laika un telpas sarežģītības analīzes veikšana.

Kas ir rekursīvs algoritms?

Rekursīvie algoritmi ir balstīti uz ideju, ka problēmas risinājumu var atrast, atrodot risinājumus mazākām tās pašas problēmas apakšproblēmām. Rekursīvajā algoritmā funkcija tiek definēta pēc pašas iepriekšējās versijas. Ir svarīgi atzīmēt, ka šai pašatklāšanai vajadzētu būt izbeigšanas nosacījumam, lai izvairītos no atsauces uz visiem laikiem. Pirms atsauces uz sevi tiek pārbaudīts pārtraukšanas nosacījums. Sākotnējais rekursīvā algoritma solis ir saistīts ar problēmas rekursīvās definīcijas bāzes klauzulu. Darbības, kas seko sākotnējam solim, ir saistītas ar problēmas induktīvajiem noteikumiem. Rekursīvie algoritmi daudzās situācijās nodrošina vienkāršāku risinājumu, un tas ir tuvāk dabiskajam domāšanas veidam nekā vienas un tās pašas problēmas atkārtojošais algoritms. Bet kopumā rekursīvajiem algoritmiem ir nepieciešama lielāka atmiņa, un tie skaitļošanas ziņā ir dārgi.

Kāda ir atšķirība starp randomizētu un rekursīvu algoritmu?

Nejaušie algoritmi ir algoritmi, kas izmanto nejaušības sajūtu, veicot nejaušas izvēles, kas varētu ietekmēt algoritma izpildi, savukārt rekursīvie algoritmi ir algoritmi, kuru pamatā ir ideja, ka problēmas risinājumu var atrast, atrodot risinājumus mazākām apakšproblēmām. no tās pašas problēmas. Nejaušības dēļ nejaušos algoritmos algoritma izturēšanās var mainīties pat vienai un tai pašai ievadei (dažādos algoritma izpildījumos). Bet rekursīvos algoritmos tas nav iespējams, un fiksētam ievadam rekurējoša algoritma darbība būtu vienāda.