优化组合算法的复杂度

Question

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

You are given N boxes indexed from 1 to N. Each box contains either no coins or one coin. The number of empty boxes and the number of boxes with one coin are denoted by n0 and n1, respectively. You take a random subset of the boxes where each subset has the same same probability to be selected. The empty set and the set itself are considered a subset.

Given n0 and n1, what is the probability that the total number of coins in the random subset is even?

Constraint: N = n0 + n1 < 100000

EXAMPLES

1

• Input: n0 = 1, n1 = 0
• Output: 1.0
• Explanation: There are two subsets: [] and [0]. Both of them have an even sum.

2

• Input: n0 = 0, n1 = 2
• Output: 0.5
• Explanation: There are four subsets: [], [1], [1], and [1, 1]. The sum of [] and [1,1] is even.

到目前为止，我尝试在Python3.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

假设你的算法是正确的，那么总的概率可以通过下面的分析来确定

总结如下：

prob = 0
for j in range(0, n1+1):
        if (j % 2 == 0):
            prob += comb(n1, j)

计算二项式系数的偶数项，即：

comb(n1, 0) + comb(n1, 2) + ... + comb(n1, J)
    where J is even and J>=n1

对于J>；n1，因为梳（n1，J）=0表示J>；n1（nCr的定义）

这个总和就是source：

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  (always)

Answer 2

import math

def comb(n, k):  # Calculates the combination based on n and k values
    return math.factorial(n) // math.factorial(n - k) //math.factorial(k)

def question(n0, n1):    # probability that the total number of coins in the random subset is even
    """probability of sums of even / total probability"""
    p = 0
    for i in range(0, n1+1):
        if (i % 2 == 0):
            p += comb(n1, i)

    return  p / (2 ** n1)