Probabilistic analysis of algorithms - Revision history

David Eppstein: /* References */ clean up bare-url links; also remove incorrect category (this is about distributions on inputs, not about randomization within algorithms)

2024-01-25T23:06:40Z

References: clean up bare-url links; also remove incorrect category (this is about distributions on inputs, not about randomization within algorithms)

← Previous revision		Revision as of 23:06, 25 January 2024
Line 14:		Line 14:

	== References ==		== References ==
			*{{citation

			\| last1 = Frieze \| first1 = Alan M.
	* https://link.springer.com/chapter/10.1007/978-3-662-12788-9_2
			\| last2 = Reed \| first2 = Bruce
	* https://books.google.com.tr/books?hl=tr&lr=&id=XDr0BwAAQBAJ&oi=fnd&pg=PA1&dq=Probabilistic+analysis+of+algorithms&ots=8Dccj3ET5H&sig=cYB6-q1_BfdlT22alI3aTHlBgzs&redir_esc=y#v=onepage&q=Probabilistic%20analysis%20of%20algorithms&f=false
			\| editor1-last = Habib \| editor1-first = Michel
⚫	* ~~https://link.springer.com/chapter/~~10.1007/978-3-7091-9076-0_11
			\| editor2-last = McDiarmid \| editor2-first = Colin

			\| editor3-last = Ramirez-Alfonsin \| editor3-first = Jorge
	[[Category:Randomized algorithms]]
			\| editor4-last = Reed \| editor4-first = Bruce
			\| contribution = Probabilistic analysis of algorithms
			\| doi = 10.1007/978-3-662-12788-9_2
			\| isbn = 9783662127889
			\| pages = 36–92
			\| publisher = Springer
			\| series = Algorithms and Combinatorics
			\| title = Probabilistic Methods for Algorithmic Discrete Mathematics
			\| volume = 16
			\| year = 1998}}
			*{{citation
			\| last = Hofri \| first = Micha
			\| doi = 10.1007/978-1-4612-4800-2
			\| isbn = 9781461248002
			\| publisher = Springer
			\| title = Probabilistic Analysis of Algorithms: On Computing Methodologies for Computer Algorithms Performance Evaluation
			\| year = 1987}}
			*{{citation
			\| last = Frieze \| first = A. M.
			\| editor1-last = Tinhofer \| editor1-first = G.
			\| editor2-last = Mayr \| editor2-first = E.
			\| editor3-last = Noltemeier \| editor3-first = H.
			\| editor4-last = Syslo \| editor4-first = M. M.
			\| contribution = Probabilistic analysis of graph algorithms
		⚫	\| doi = 10.1007/978-3-7091-9076-0_11
			\| isbn = 9783709190760
			\| pages = 209–233
			\| publisher = Springer
			\| series = Computing Supplementa
			\| title = Computational Graph Theory
			\| volume = 7
			\| year = 1990}}

	[[Category:Analysis of algorithms]]		[[Category:Analysis of algorithms]]

David Eppstein: untrue that this is unsourced. It has three good sources. The article is short enough that footnoting rather than listing sources at the end would not be more informative.

2024-01-25T21:57:21Z

untrue that this is unsourced. It has three good sources. The article is short enough that footnoting rather than listing sources at the end would not be more informative.

← Previous revision		Revision as of 21:57, 25 January 2024
Line 1:		Line 1:
	{{nosources\|date=April 2021}}
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

Bera678: Added citations

2023-12-30T16:42:22Z

Added citations

← Previous revision		Revision as of 16:42, 30 December 2023
Line 13:		Line 13:
	*[[Random self-reducibility]]		*[[Random self-reducibility]]
	*[[Principle of deferred decision]]		*[[Principle of deferred decision]]

			== References ==

			* https://link.springer.com/chapter/10.1007/978-3-662-12788-9_2
			* https://books.google.com.tr/books?hl=tr&lr=&id=XDr0BwAAQBAJ&oi=fnd&pg=PA1&dq=Probabilistic+analysis+of+algorithms&ots=8Dccj3ET5H&sig=cYB6-q1_BfdlT22alI3aTHlBgzs&redir_esc=y#v=onepage&q=Probabilistic%20analysis%20of%20algorithms&f=false
			* https://link.springer.com/chapter/10.1007/978-3-7091-9076-0_11

	[[Category:Randomized algorithms]]		[[Category:Randomized algorithms]]

AnomieBOT: Dating maintenance tags: {{Nosources}}

2021-04-28T14:27:54Z

Dating maintenance tags: {{Nosources}}

← Previous revision		Revision as of 14:27, 28 April 2021
Line 1:		Line 1:
	{{nosources}}		{{nosources\|date=April 2021}}
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

Reyk: tag for lack of sources, remove long-challenged dubious claim

2021-04-28T14:07:53Z

tag for lack of sources, remove long-challenged dubious claim

← Previous revision		Revision as of 14:07, 28 April 2021
Line 1:		Line 1:
			{{nosources}}
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

	For non-probabilistic, more specifically [[deterministic algorithm\|deterministic]], algorithms, the most common types of complexity estimates are the [[average-case complexity]] ~~(expected-time complexity){{Dubious\|date=March 2011}}~~ 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.		For non-probabilistic, more specifically [[deterministic algorithm\|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.		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.

FlaxenHobbit at 12:19, 16 December 2019

2019-12-16T12:19:24Z

← Previous revision		Revision as of 12:19, 16 December 2019
Line 3:		Line 3:
	This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

	For non-probabilistic, more specifically [[deterministic algorithm]]s, the most common types of complexity estimates are the [[average-case complexity]] (expected-time complexity{{Dubious\|date=March 2011}} 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.		For non-probabilistic, more specifically [[deterministic algorithm\|deterministic]], algorithms, the most common types of complexity estimates are the [[average-case complexity]] (expected-time complexity){{Dubious\|date=March 2011}} 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 ~~averaging~~ ~~for~~ all possible choices in randomized steps ~~are~~ also taken into an account, in addition to the input distributions.		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.

	==See also==		==See also==

FlaxenHobbit: Fixed grammar.

2019-12-16T12:15:21Z

Fixed grammar.

← Previous revision		Revision as of 12:15, 16 December 2019
Line 1:		Line 1:
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 ~~algorithms~~.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

	For non-probabilistic, more specifically~~, for~~ [[deterministic algorithm]]s, the most common types of complexity estimates are the [[average-case complexity]] (~~'''~~expected time complexity~~''')~~{{Dubious\|date=March 2011}} 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.		For non-probabilistic, more specifically [[deterministic algorithm]]s, the most common types of complexity estimates are the [[average-case complexity]] (expected-time complexity{{Dubious\|date=March 2011}} 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 averaging for all possible choices in randomized steps are also taken into an account, in addition to the input distributions.		In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or averaging for all possible choices in randomized steps are also taken into an account, in addition to the input distributions.

Abelmoschus Esculentus: Reverted edits by 2405:204:224:F56C:9DF:2459:C51F:D24E (talk) (HG) (3.4.6)

2018-12-11T07:16:19Z

Reverted edits by 2405:204:224:F56C:9DF:2459:C51F:D24E (talk) (HG) (3.4.6)

← Previous revision		Revision as of 07:16, 11 December 2018
Line 1:		Line 1:
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[~~Anlysis~~ of algorithms\|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 algorithms.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 algorithms.

	This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

2405:204:224:F56C:9DF:2459:C51F:D24E at 07:15, 11 December 2018

2018-12-11T07:15:51Z

← Previous revision		Revision as of 07:15, 11 December 2018
Line 1:		Line 1:
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[~~Analysis~~ of algorithms\|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 algorithms.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Anlysis of algorithms\|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 algorithms.

	This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.

27.59.156.127 at 06:15, 5 August 2018

2018-08-05T06:15:26Z

← Previous revision		Revision as of 06:15, 5 August 2018
Line 1:		Line 1:
	In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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~~.		In [[analysis of algorithms]], '''probabilistic analysis of algorithms''' is an approach to estimate the [[Analysis of algorithms\|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 algorithms.

	This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.		This approach is not the same as that of [[probabilistic algorithm]]s, but the two may be combined.