Hazardigita algoritmo: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
KuBOT (diskuto | kontribuoj) e Roboto: anstataŭigo de "Ŝablono:El" per "Ŝablono:EL" (laŭ VP:AA); kosmetikaj ŝanĝoj |
Leyo (diskuto | kontribuoj) e formato de la minuso |
||
Linio 13:
Hazardigita [[montekarla maniero]] estadas uzata por [[integralado]].
Plej popularaj [[primeca provo|primecaj provoj]] estas hazardigitaj algoritmoj. Ĉi tiuj testoj uzas, krom la testata nombro ''n'', iujn aliajn nombrojn ''a'' kiuj estas elektataj je hazarde de iu aro. La probablo de eraro povas reduktiĝas per ripetado de la provo kun multaj sendepende elektitaj ''a''; por du kutime uzataj testoj, por ĉiu komponigita ''n'' almenaŭ duono de la ''a'' detektas komponigitecon de ''n''. Tiel ''k'' ripetadoj reduktas la eraran probablon al maksimume ''2<sup>
La baza strukturo de hazardigita primeca provo estas jena:
Linio 24:
En praktiko, taŭgas akcepti malgrandan probablon de eraro, kiu povas esti farita astronomie malgrandan. Kaj, eĉ kvankam determinismaj polinomo-tempaj primecaj provoj estas ellaboritaj, ili ne anstataŭigas la pli malnovajn probablecajn testojn en [[ĉifriko|ĉifrika]] [[programaro]], kaj ĉi tiu anstataŭigo ne estas atendata por la antaŭvidebla estonto.
Se la probablo de eraro de hazardigita maniero estas ekzemple 2<sup>
[[Rapida ordigo]] estas familiara, kutime uzita algoritmo en kiu hazardo povas esti utila. La determinisma, versio de ĉi tiu algoritmo postulas tempon ''[[Granda O|O]](n<sup>2</sup>)'' por ordigi ''n'' nombrojn por iu degenera enigoj. En la plej simpla varianto, temas pri tabelo kies eroj estas jam en ordigitaj, kaj en ĉiu okazo atakanto povas krei ĉi tian tabelon. Tamen, se la algoritmo elektas erojn hazarde, ĝi havas tre altan probablon de ruliĝo en tempo ''O(n log n)''.
| |||