Content deleted Content added
Jorge Stolfi (talk | contribs) m →Uses: trim blank lines |
Jorge Stolfi (talk | contribs) →Randomness: fix redlink |
||
Line 12:
In theory, randomization functions are assumed to be truly random, and yield an unpredictably different function every time the algorithm is executed. The randomization technique would not work if, at every execution of the algorithm, the randomization function always performed the same mapping, or a mapping entirely determined by some externally observable parameter (such as the program's startup time). With such a "pseudo-randomization" function, one could in principle construct a sequence of calls such that the function would always yield a "bad" case for the underlying deterministic algorithm. For that sequence of calls, the average cost would be closer to the worst-case cost, rather than the average cost for random inputs.
In practice, however, the main concern is that some bad cases for the deterministic algorithm may occur in practice much more often than it would be predicted by chance. For example, in a naive variant of quicksort, the worst case is when the input items are already sorted — which is a very common occurrence in many appilcations. For such algorithms, even a fixed pseudo-random premutation may be good enough. Even though the resulting "pseudo-randomized" algorithm would still have some "bad" cases, they will be certain peculiar orders that would be quite unlikely to arise in real applications. So, in practice one often uses functions that are derived from [[pseudo-random number
===Uniformity===
| |||