p*********g
发帖数: 226 | 1 有 n 个独立的 Bernolli 随机变量 x_i. p(x_i=1) = a_i. 现要他们和的分布（即和
为0,1,...,n的概率）。有没有复杂度为O(n)的线性算法？递归需要O(n^2).
多谢。 | a*****3
发帖数: 601 | | p*********g
发帖数: 226 | 3 所有 a_i 取相同值的时候确实是binomial。但这里a_i 可以不同。谢谢
感觉上有点和 Fast Fourier transform 沾边。 | p*********g
发帖数: 226 | 4 solved
http://www.mathworks.com/matlabcentral/fileexchange/28488-bernpdf
overall complexity O^*(n), 就是 n 乘上一个 o(n) (o(n) 是比线性还慢的一个函数)
When n > 22, it calculates the distribution of \sum_{i=1}^{n/2} x_i by
invoking the function itself (recursion). So is \sum_{n/2+1}^n x_i. Then
apply convolution on these two results. When n < 22, it just performs
dynamic programming. Since the convolution takes O(n log n) time, so the
overall time complexity is O^*(n). |
|
