水塘抽樣
水塘抽樣（）是一系列的隨機算法，其目的在於從包含n個項目的集合S中選取k個樣本，其中n為一很大或未知的數量，尤其適用於不能把所有n個項目都存放到内存的情況。最常見例子為在其論文中所提及的算法R。 參照Dictionary of Algorithms and Data Structures所載的O(n)算法，包含以下步驟（假設数组S以0開始標示）： 從S中抽取首k項放入「水塘」中 對於每一個S[j]項（j ≥ k）： 隨機產生一個範圍從0…
标签：#随机化算法
共 5 篇文章
蒙地卡羅方法
蒙特卡罗方法（），也称统计模拟方法，是1940年代中期由于科学技术的发展和电子计算机的发明，而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。 20世纪40年代，在科學家冯·诺伊曼、斯塔尼斯拉夫·烏拉姆和尼古拉斯·梅特罗波利斯於洛斯阿拉莫斯国家实验室为核武器计划工作时，发明了蒙特卡罗方法。因为烏拉姆的叔叔经常在摩納哥的蒙特卡洛赌场输钱得名，而蒙特卡罗方法正是以概率为基础的方法。…
鲍姆-韦尔奇算法
在电气工程、计算机科学、统计计算和生物信息学中，鲍姆-韦尔奇算法是用于寻找隐马尔可夫模型未知参数的最大期望算法，它利用前向-后向算法来计算E-Step的统计信息。 历史 鲍姆-韦尔奇算法是以其发明者伦纳德·埃绍·鲍姆和劳埃德·理查德·韦尔奇的名字命名的。鲍姆-韦尔奇算法和隐马尔可夫模型在20世纪60年代末和70年代初由鲍姆和他的同事在国防分析研究所的一系列文章中首次描述。HMMs最初主要应用于语音处理领域。20世纪80年代，HMMs开始…
莫里斯方法
莫里斯方法（Morris method）是應用統計學中用於全局敏感性分析的「一次改變一因子」統計方法，也就是每次計算時只將一個輸入參數賦予新值但其他參數保持不變。在輸入值的可能範圍內的不同點 x(1 \rightarrow r)，進行 r 次局部變動，以進行全局敏感性分析。 詳述 基本效應分布 與第 i 個輸入因子相關的基本效應之有限分佈，是從 \Omega 隨機抽取不同的 x而得，以 F_i 表示. 變異性 在莫里斯（Max D. M…
拉斯维加斯算法
在电脑运算中，拉斯维加斯算法（Las Vegas algorithm）是一种永远给出正确解的随机化算法；也就是说，它总是给出正确结果，或是返回失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运算所用资源。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。 与拉斯维加斯算法相对的是蒙地卡罗算法。蒙地卡罗算法在一定的概率下可能返回错误的结果，但其运行时间是确定的或有上界的。 特性 随机性：算法在运行过程中使…