优化组合算法的复杂性

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.

到目前为止，我尝试在 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 = 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 没问题，因为 comb(n1, J) = 0 对于 J > n1（nCr 的定义）

这个总和就是source:

prob = 2**(n1 - 1)

代入 total_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)

优化组合算法的复杂性

Optimise complexity of combinatoric algorithm

python

optimization

combinations

mathematical-optimization

EXAMPLES