text: 在計算機科學的計算中，別名方法提出的用於從一個離散的機率分佈中取樣的高效演算法。 該演算法可在任意的機率分佈 ""O"(1) 時間複雜度內進行隨機取樣。演算法.演算法在內部構造兩張表："機率表" "Ki"。具體來說，演算法進行如下操作：Marsaglia等人曾提出名為「平方直方圖」的機率表的替代方案。該方案在上述第3步使用 y"。表的生成.可以在原機率分佈上，增加若干 n" 增加到某些便於計算的值，例如2的冪。生成表的第一步是執行 "Ui" = "npi"，由此將表中的元素為三類：若 "Ki" = "i" 會更加自然。只要不是所有的元素是在「恰好」組，就重複執行以下步驟：每輪迭代至少使一個元素進入「恰好」組。因此，至多經過 "O"("n") 時間內完成。VoseUi" 以課忽略的誤差設定為1。別名表的構造不唯一。由於當 "O"("n" log "n") 的時間複雜度。效率.儘管在產生均勻隨機變數非常快時，Alias方法非常高效；但在某些情況下，就隨機位元的使用而言，還有很大最佳化空間。這是因為，哪怕其實只需少量隨機位元，Alias方法每回也都使用隨機變數 "x" 的所有隨機位元。舉個例子，當機率特別平衡時，會有很多 x" 可以用來做32次隨機取樣，但Alias方法只能用一次。再舉一個例子，當機率特別不平衡時，會有很多 :1–4更為有效。若在相同機率分佈下進行大量重複取樣，平均而言，我們只需遠少於1個隨機位元即可。利用算術編碼技術，在給定時，我們可以達到這一下限。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 別名方法
metadata: https://zh.wikipedia.org/wiki?curid=6823213