Pravděpodobnostní algoritmus
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
Pravděpodobnostní (náhodnostní) algoritmy jsou nedeterministické algoritmy, které se snaží najít řešení rychleji nebo řešení těžko řešitelných problémů, často tzv. NP-úplných problémů. Pravděpodobnostní algoritmus se může náhodně rozhodovat mezi různými možnostmi jak pokračovat. Pro stejný vstup může dávat takový algoritmus různé výsledky, které mohou být dokonce nesprávné. Mnohdy se tedy na daném vstupu spustí pravděpodobnostní algoritmus vícekrát, aby se s větší pravděpodobností dospělo ke správnému výsledku.
Všechny tři varianty jsou ekvivalentní.
Pravděpodobnostní algoritmy jsou většinou jednoduché, avšak analýza jejich časové složitosti je často náročná.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.