Content deleted Content added
m v2.04 - Fix errors for CW project (Link equal to linktext) |
|||
Line 32:
Each iteration moves at least one entry to the “exactly full” category (and the last moves two), so the procedure is guaranteed to terminate after at most {{math|''n''−1}} iterations. Each iteration can be done in {{math|''O''(1)}} time, so the table can be set up in {{math|''O''(''n'')}} time.
Vose<ref name=Vose/>{{Rp|974}} points out that floating-point rounding errors may cause the guarantee referred to in step 1 to be violated. If one category empties before the other, the remaining entries may have {{mvar|U<sub>i</sub>}} set to 1 with negligible error. The solution accounting for floating point is sometimes called the '''Walker-Vose method''' or the '''Vose alias method'''.
The Alias structure is not unique.
| |||