`
Iam42
  • 浏览: 275269 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

蓄水池抽样算法

阅读更多

题目:要求从N个元素中随机的抽取k个元素,其中N无法确定

 

解法:首先选择N中的前k个数加入“蓄水池”中,然后从第k+1个数开始,以k/k+i(i=1,2,3...)的概率选择这个数,然后在蓄水池中随机选择一个数,并将其替换,N个元素遍历完毕后,蓄水池中的k个数就是随机选择的。

 

证明:这里即需要证明每个数出现在蓄水池中的概率都是相等的,拟采用数学归纳法

          1.当i=1时,蓄水池中某个数出现的概率

             第k+1个数被取出的概率是k/k+1, 这时,蓄水池中每个数出现的概率都是1,同时,一个数被选择到的概率是1/k, 因此,一个数出现在池中的概率是1-(k/k+1)*(1/k)=k/k+1

          2.假设第i个数被取出的概率是k/k+i,证明在有k+i+1的样本中,一个数出现在池子里的概率是k/k+i+1

             第k+i+1个数被取出的概率是k/k+i+1,  池子中每个数的出现概率都是k/k+i, 池中的数被选择到的概率是1/k, 一个数在池中的概率就是 他出现在池中的概率*他没有被替换的概率,就是(k/k+i)*(1-1/k*k/k+i+1),也就是k/k+i+1

      

2
0
分享到:
评论
2 楼 johnkeepmoving 2014-10-12  
师兄, 想不到搜蓄水池算法搜到你这来了哈...
1 楼 javaboy8282 2012-09-20  
楼主可否贴出代码  代码更直观一点

相关推荐

    蓄水池算法leetcode-leetcode:leetcode

    蓄水池抽样》 Blog: 《结构之法 算法之道》 Something about bit op: Something about array rotate: A Linear Time Majority Vote Algorithm 题解: Maximum Gap: Something about largest-rectangle-in-histogram:...

    蓄水池抽样

    蓄水池抽样,也称为均匀抽样,是一种在大数据集上进行随机抽样的高效算法。这个算法的主要目的是从 N 个元素中等概率地选取 K 个元素,且适用于在线性时间复杂度内完成。以下是对蓄水池抽样的详细解释: 1. **初始...

    蓄水池算法leetcode-randomized-algorithm:随机算法

    蓄水池算法leetcode 固定范围采样 输入大小为 n 个项目 获取 0 到 n -1 之间的随机数 根据输入返回项目[索引] 油藏取样 概括 n项的流 n不知道提前 每个项目结果的概率相等 算法 水库采样算法旨在从未知大小的总体中...

    蓄水池算法leetcode-leetcode-cn.go:leetcode-cn.go

    蓄水池算法 leetcode leetcode-cn.go 数组 267 动态规划 213 数学 190 字符串 187 树 155 深度优先搜索 132 哈希表 132 二分查找 92 贪心算法 78 广度优先搜索 74 双指针 ...分治算法 ...蓄水池抽样 2

    蓄水池算法leetcode-leetcode-js-chimy:leetcode-js-chimy

    蓄水池算法 leetcode leetcode-javascript-chimy 数据结构 1.数组 ...蓄水池抽样 3. 数学 4. 几何 5. 设计 6. 脑筋急转弯 字符串 数组 链表 队列 栈 排序 树 图 贪心算法 分治算法 回溯算法 动态规划

    蓄水池算法leetcode-leetcode-ts:leetcode-ts

    总的来说,蓄水池算法是一种在大数据处理中非常实用的随机抽样方法,尤其适用于LeetCode等在线编程挑战平台。结合TypeScript模板项目,开发者可以更好地理解和实践这一算法,提升自己的编程技能和问题解决能力。

    蓄水池算法leetcode-tech_interview_prep:技术面试准备

    蓄水池算法leetcode 技术面试准备计划 从零开始学习数据结构和算法 如何: 数据结构:记笔记,画概念 此数据结构的算法:记笔记,绘制概念 从零开始实现数据结构及其算法 实施例程: 阅读问题说明 编写单元测试:...

    蓄水池算法leetcode-myLeetCodeSummary:myLeetCode总结

    蓄水池算法 leetcode MyLeetCodeSummary ...蓄水池抽样 几何 Map 数组 哈希表 链表 数学 双指针 字符串 二分查找 分治算法 动态规划 回溯算法 Random Rejection Sampling Sliding Window Ordered Map Line Sweep

    leetcode算法题主函数如何写-blog:博客

    蓄水池抽样算法 leetcode 382 更多可见算法与数据结构可见 数论 蔡勒公式 汉诺塔 计算机网络 [分组转发中的时延] [TDM, CDM, WDM, WDM, STDM] HTTP [多路复用能否取代打包工具] 编译技术 做语言的主人 Unix Linux ...

    蓄水池算法leetcode-leetcode-ts-template:leetcodets模板项目

    总的来说,蓄水池算法是一种在大数据环境下进行随机抽样的高效方法,而"leetcode-ts-template"项目则是利用TypeScript解决LeetCode问题的良好实践,两者都体现了IT行业中实用和创新的精神。通过学习和应用这些知识点...

    蓄水池算法leetcode-leetcode:leetcode练习

    蓄水池算法 leetcode leetcode practice 动态规划 DynamicProgramming 贪心算法 GreedyAlgorithm 分治算法 DivideAndConquer ...回溯算法 ...蓄水池抽样 Array 数组 HashTable 哈希表 SegmenTree 线段树

    leetcode蓄水池JAVA-Leetcode:力码日志

    蓄水池JAVA 力码 旨在熟悉Java和python实现的算法和数据结构。 :) 如果你放弃,你只会输。 标签 大批 标题 解决方案 哈希表 标题 解决方案 链表 标题 解决方案 数学 标题 解决方案 细绳 标题 解决方案 两个指针 标题...

    百度:部分算法面试题1

    1. **蓄水池抽样**:在不知道元素总数的情况下,需要一次性遍历链表并随机抽取k个元素,保证每个元素被选中的概率相等。蓄水池抽样的策略是先选择前k个元素,然后对于剩余的元素,以k/i的概率替换已选中的一个元素。...

    基于分布式核的在线AUC最大化算法.pdf

    蓄水池抽样方法是其中一种常用的策略,通过维护固定大小的缓存空间来存储历史数据,并动态地更新这些数据。这使得在线学习可以在有限的内存资源下,以近似的方式处理大规模数据集。 在上述提及的算法中,作者们借鉴...

    数据结构与算法1

    5. **蓄水池抽样**: - **抽样方法**:在不确定规模的数据集中进行随机采样,保证每个元素被选中的概率相等。 - **步骤**:初始化大小为k的数组,随机替换或保留元素,直到遍历完整个数据集。 - **应用场景**:...

    leetcode蓄水池JAVA-xiao-leetcode:leetcodesrccode,从易到中到难,哈哈哈

    leetcode蓄水池JAVA xiao-leetcode leet code src code, from easy to medium to hard, hahaha array backtracking(回溯) bit_manipulation breadth_first_search(深度优先遍历) depth_first_search(广度优先遍历) ...

    hi-algorithm:算法题解题技巧,算法,数据结构以及设计模式

    面向招聘的算法题技巧 算法题技巧 算法题(按照类型分类) ...蓄水池抽样 脑筋急转弯 记忆化 数学 几何 极小化极大 随机 扫描线算法 拒绝采样 ordered map map 了解更多欢迎关注微信公众号:科科人神

    leetcode中文版-LeetCode:算法练习:LeetCode问题、LeetCode每周竞赛等

    概率:洗牌算法、蓄水池抽样、蒙特卡洛 数论:素数,最小公倍数,最大公约数 位运算:异或,与的巧妙用法 特殊的数:有效数字(状态机),第n个丑数,平方数(DP解法),回文数 数字的转化:溢出检测、模拟运算...

    非科班出身程序员刷题-leetcode:按tag区分的刷题列表,充会员整理的按leetcode频率热度排序的刷题列表每个tag的top42(宇

    非科班出身程序员刷题 个人刷题总结 数组问题 字符串 树 哈希表 动态规划 深度优先搜索 二分查找 贪心 双指针 广度优先搜索 栈 回溯算法 设计 链表 排序 ...分治算法 ...蓄水池抽样 二叉搜索树 记忆化

Global site tag (gtag.js) - Google Analytics