Randomizēts pret rekursīvo algoritmu
Randomizēti algoritmi savā loģikā ietver nejaušības sajūtu, veicot nejaušas izvēles algoritma izpildes laikā. Šīs nejaušības dēļ algoritma darbība var mainīties pat fiksētai ievadei. Daudzām problēmām nejaušināti algoritmi nodrošina visvienkāršākos un efektīvākos risinājumus. Rekursīvie algoritmi balstās uz domu, ka problēmas risinājumu var atrast, meklējot risinājumus vienas un tās pašas problēmas mazākām apakšproblēmām. Rekursiju plaši izmanto, lai rastu risinājumus problēmām datorzinātnēs, un daudzas augsta līmeņa programmēšanas valodas atbalsta rekursiju.
Kas ir nejaušināts algoritms?
Nejaušības algoritmi ietver nejaušības sajūtu, veicot nejaušas izvēles, kas nosaka algoritma izpildi. To parasti veic, kā papildu ievadi ņemot nejaušu skaitļu kopu, ko ģenerējis pseidogadījuma skaitļu ģenerators. Sakarā ar to algoritma darbība var mainīties pat fiksētai ievadei. 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 ievades īpašībām. Turklāt skaitļošanas ģeometrijā būvkonstrukcijām, piemēram, izliektam korpusam, tiek izmantota nejaušināta inkrementālās konstrukcijas metode. Izmantojot šo metodi, ievades punkti tiek nejauši permutēti un pēc tam pa vienam tiek ievietoti struktūrā. Randomizēta algoritma ieviešana ir salīdzinoši vienkārša nekā deterministiska algoritma ieviešana tai pašai problēmai. Lielākais izaicinājums randomizēta algoritma izstrādē ir laika un telpas sarežģītības asimptotiskas analīzes veikšana.
Kas ir rekursīvais algoritms?
Rekursīvie algoritmi balstās uz domu, ka problēmas risinājumu var atrast, meklējot risinājumus vienas un tās pašas problēmas mazākām apakšproblēmām. Rekursīvajā algoritmā funkcija tiek definēta, ņemot vērā tās iepriekšējo versiju. Ir svarīgi atzīmēt, ka šai pašnorādīšanai ir jābūt beigu nosacījumam, lai uz visiem laikiem izvairītos no atsauces uz sevi. Pārtraukšanas nosacījums tiek pārbaudīts pirms atsauces uz sevi. Rekursīvā algoritma sākotnējais solis ir saistīts ar problēmas rekursīvās definīcijas pamata klauzulu. Darbības, kas seko sākotnējam solim, ir saistītas ar problēmas induktīvām klauzulām. 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ā iteratīvais algoritms vienai un tai pašai problēmai. Bet kopumā rekursīviem algoritmiem ir nepieciešams vairāk atmiņas, un tie ir dārgi skaitļošanas ziņā.
Kāda ir atšķirība starp randomizēto un rekursīvo algoritmu?
Izlases 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 vienas un tās pašas problēmas mazāku apakšproblēmu risinājumi. Nejaušības dēļ nejaušības algoritmos algoritma uzvedība var mainīties pat vienai un tai pašai ievadei (dažādās algoritma izpildēs). Taču tas nav iespējams rekursīvos algoritmos, un rekursīva algoritma darbība fiksētai ievadei būtu tāda pati.
