使用幂函数计算效率图大小

efficiency graph size calculation with power function

我正在寻找改进以下简单函数(写在python),计算特定图的最大尺寸:

def max_size_BDD(n):
i = 1
size = 2
while i <= n:
    size += min(pow(2, i-1), pow(2, pow(2, n-i+1))-pow(2, pow(2, n-i)))
    i+=1
    print(str(i)+" // "+ str(size))
return size

如果我将它作为输入 n = 45,进程将被终止(可能是因为它花费的时间太长,我不认为这是内存问题,对吧?)。我如何重新设计以下算法,使其能够处理更大的输入?

我的建议:虽然原始函数在 ~10 时开始 运行 出现问题,但我实际上没有任何限制(即使对于 n = 100000000,我也保持在 1s 以下)。

def exp_base_2(n):
    return 1 << n


def max_size_bdd(n):
    # find i at which the min branch switches
    start_i = n
    while exp_base_2(n - start_i + 1) < start_i:
        start_i -= 1

    # evaluate all to that point
    size = 1 + 2 ** start_i

    # evaluate remaining terms (in an uncritical range of n - i)
    for i in range(start_i + 1, n + 1):
        val = exp_base_2(exp_base_2(n - i))
        size += val * (val - 1)
        print(f"{i} // {size}")
    return size

备注:

  • 核心思想:避免2的大次方,如果最后用min就不用计算了
  • 我匆忙做了所有这些,也许我可以稍后添加更多解释......如果有人感兴趣的话。然后,我也可以对新的实现做一个更体面的验证。
  • exp_base_2 的影响在完成所有数学运算以优化原始计算后应该可以忽略不计。我在分析之前做了这个优化。
  • 也许一个完整的封闭形式的解决方案是可能的。我没有投入时间进行进一步调查。