bab*_*now 2 algorithm
可能重复: 如何在未知长度的链表中选择一个统一的随机元素？
假设我们想要随机选择链表中的元素,但我们不知道链表的长度.
设计一种算法,该算法尽可能采用随机选择元素的运行时间.
Kar*_*ath 10
有一个简单的算法O(N),获取长度,然后选择一个元素.
O(N)
但是你可以通过在线算法做得更好,只访问每个元素一次:
您选择第一个元素作为答案,然后在第kth个元素上用该元素替换您的答案,概率为1/k.可以用数学归纳证明该方法没有偏差的事实.
k
1/k
一般化版本(挑选k元素)是水库采样.
归档时间：
13 年，3 月 前
查看次数：
260 次
最近记录：