Content deleted Content added
No edit summary |
Jorge Stolfi (talk | contribs) Turned redirect of hash function to a separate article since the concepts are different. |
||
Line 1:
In [[computer science]], '''randomization function''' or '''randomizing function''' is a [[algorithm]] or [[procedure]] that implements a [[random]] [[function (mathematics)|function]] between two specific [[set (mathematics)|set]]s.
Randomizing functions are central to the design of [[randomized algorithms]], that have good [[expected value (statistics)|expected]] performance for any input. For example, consider an algorithm like [[quicksort]], which has small expected running time for random inputs, but is very slow when the input data are presented in certain unfavorable orders. A randomizing function from the integers 1 to ''n'' to the integers 1 to ''n'' can be used used to rerrange the ''n'' input items in "random" order, before calling that algorithm. This modified algorithm will have small expected running time for ''any'' input.
Randomizing functions are related to [[random number generator]]s and [[hash function]]s, but have somewhat different requirements and uses, and often need specific algorithms.
{[stub}}
| |||