优化组合算法的复杂度

Question

我正在努力优化我的代码以解决以下问题：

给你 N 个盒子，索引从 1 到 N。每个盒子要么没有硬币，要么包含一枚硬币。空盒子的数量和装有一枚硬币的盒子的数量分别用n0和n1表示。您随机抽取盒子的子集，其中每个子集都有相同的被选择概率。空集和集合本身被视为子集。

给定 n0 和 n1，随机子集中硬币总数为偶数的概率是多少？

约束：N = n0 + n1 < 100000

例子

1

• 输入：n0 = 1，n1 = 0

• 输出：1.0

• 解释：有两个子集：[]和[0]。两人的总和相等。

2

• 输入：n0 = 0，n1 = 2

• 输出：0.5

• 解释：有四个子集：[]、[1]、[1] 和 [1, 1]。[] 与 [1,1] 之和为偶数。

到目前为止，我尝试在 Python 3.8 中实现，但我认为它工作正常，但计算更大的数字需要很长时间。

prob = 0

n0 = 1

n1 = 4

for j in range(0, n1+1):

        if (j % 2 == 0):

            prob += comb(n1, j)

total_prob = (2**n0 * prob) / (2 ** (n0+n1))

total_prob

Answer 1

假设您的算法是正确的，则可以按如下方式分析确定total_prob。这个总结：prob = 0for j in range(0, n1+1):&nbsp; &nbsp; &nbsp; &nbsp; if (j % 2 == 0):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prob += comb(n1, j)正在计算二项式系数的偶数项，即：comb(n1, 0) + comb(n1, 2) + ... + comb(n1, J)&nbsp; &nbsp; where J is even and J>=n1J > n1 没问题，因为对于 J > n1，comb(n1, J) = 0（nCr 的定义）这个总和就是来源：prob = 2**(n1 - 1)代入total_prob方程中的prob：total_prob = (2**n0) *(2**(n1-1)) / (2 ** (n0+n1))total_prob = 2**(n0 + n1 - 1)/(2**(n0+n1))total_prob = 0.5&nbsp; (always)

Answer 2

import mathdef comb(n, k):&nbsp; # Calculates the combination based on n and k values&nbsp; &nbsp; return math.factorial(n) // math.factorial(n - k) //math.factorial(k)def question(n0, n1):&nbsp; &nbsp; # probability that the total number of coins in the random subset is even&nbsp; &nbsp; """probability of sums of even / total probability"""&nbsp; &nbsp; p = 0&nbsp; &nbsp; for i in range(0, n1+1):&nbsp; &nbsp; &nbsp; &nbsp; if (i % 2 == 0):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p += comb(n1, i)&nbsp; &nbsp; return&nbsp; p / (2 ** n1)