Probabilistic analysis of algorithms (original) (raw)
In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm.This approach is not the same as that of probabilistic algorithms, but the two may be combined.
| Property | Value |
|---|---|
| dbo:abstract | In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm.This approach is not the same as that of probabilistic algorithms, but the two may be combined. For non-probabilistic, more specifically deterministic, algorithms, the most common types of complexity estimates are the average-case complexity and the almost-always complexity. To obtain the average-case complexity, given an input distribution, the expected time of an algorithm is evaluated, whereas for the almost-always complexity estimate, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds. In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or average of all possible choices in randomized steps is also taken into account, in addition to the input distributions. (en) |
| dbo:wikiPageID | 15383889 (xsd:integer) |
| dbo:wikiPageLength | 1496 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1020332354 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Principle_of_deferred_decision dbr:Algorithm dbc:Randomized_algorithms dbr:Almost_surely dbr:Best,_worst_and_average_case dbr:Deterministic_algorithm dbr:Analysis_of_algorithms dbr:Random_self-reducibility dbr:Amortized_analysis dbc:Analysis_of_algorithms dbr:Average-case_complexity dbr:Probabilistic_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Algorithm-stub dbt:Nosources |
| dcterms:subject | dbc:Randomized_algorithms dbc:Analysis_of_algorithms |
| gold:hypernym | dbr:Approach |
| rdf:type | dbo:ProgrammingLanguage |
| rdfs:comment | In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm.This approach is not the same as that of probabilistic algorithms, but the two may be combined. (en) |
| rdfs:label | Probabilistic analysis of algorithms (en) |
| owl:sameAs | freebase:Probabilistic analysis of algorithms yago-res:Probabilistic analysis of algorithms wikidata:Probabilistic analysis of algorithms https://global.dbpedia.org/id/4tToo |
| prov:wasDerivedFrom | wikipedia-en:Probabilistic_analysis_of_algorithms?oldid=1020332354&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Probabilistic_analysis_of_algorithms |
| is dbo:wikiPageRedirects of | dbr:Average-case_analysis dbr:Average-case_computational_complexity dbr:Probabilistic_analysis |
| is dbo:wikiPageWikiLink of | dbr:Richard_Weber_(mathematician) dbr:Luc_Devroye dbr:Asymptotic_computational_complexity dbr:Average-case_complexity dbr:Randomized_algorithm dbr:Uwe_Schöning dbr:Average-case_analysis dbr:Average-case_computational_complexity dbr:Probabilistic_analysis |
| is foaf:primaryTopic of | wikipedia-en:Probabilistic_analysis_of_algorithms |