【问题】为达到目标次数，计算对事件集合进行操作次数的期望
问题的全部描述是这样的：定义:
1、由s个子事件组成的事件集合M={M_1,M_2,...,M_s};
2、M_i 对应的目标次数 T_i 自然数)，状态计数 N_i （初始为0）；
3、M_i 对应的发生概率 P_i ；
4、针对M整体的一次操作称为一次实验。
问题：
（1）M中的子事件相互独立，对M进行一次实验，每个子事件都根据其对应概率判断是否发生，如果M_i 发生，则N_i 自增1；
（2）M中的子事件相互排斥（这意味着众 M_i 的和为1，满足归一化条件），对M进行一次实验，其中有且只有一个子事件发生，即如果M_i 发生，则N_i 自增1；
对M进行若干次实验，记使得所有的 N_i >= T_i的最小实验次数为 n。
求在以上两种设定下，n的期望。
这个问题在（1）情况下的一个特殊情况：s=n，P_i=0.5，T_i=1，即是这个帖子的问题：
递推数列的通项表达或变化趋势
http://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=5149&fromuid=3986
(出处: 数学研发论坛)
如果使用递推的方法求准确解，那么：
问题$1$的时间复杂度是$O(2^s*\Pi_{i=1}^s(T_i+1))$，空间复杂度是$O(\Pi_{i=1}^s(T_i+1))$。
问题$2$的时间复杂度是$O(s*\Pi_{i=1}^s(T_i+1))$，空间复杂度是$O(\Pi_{i=1}^s(T_i+1))$。
这些复杂度都随着$s$的增大而指数级增长。
如果使用某种方法求近似解，那么：
两个问题的时间复杂度都是$O(s/e^2)$，空间复杂度都是$O(s)$，其中$e$表示近似解与准确解的相对误差。
当$e$固定时，这个复杂度只是线性增长的。
页:
[1]