组合算法的优化复杂度

Question

我很难在以下问题上优化我的代码：

你会得到从1到N索引的N个盒子，每个盒子要么没有硬币，要么一个硬币。空盒数和一枚硬币盒数分别用n0和n1表示。你采取一个随机子集的框，其中每个子集有相同的概率被选择。空集和集合本身被视为子集。 给定n0和n1，随机子集中硬币总数为偶数的概率是多少？ 约束:n= n0 + n1 < 100000 示例 1

• 输入: n0 = 1，n1 =0
• 产出: 1.0
• 说明:有两个子集：[]和。他们两个人都有一个相等的数目。

2

• 输入: n0 = 0，n1 =2
• 产出: 0.5
• 说明:有四个子集：[]，1,1和1，1，1之和为偶数。

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

假设您的算法是正确的，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是可以的，因为梳( n1，J) =0对于J>n1(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  (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)