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

Question

我正在寻找改进以下简单函数（写在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，进程将被终止（可能是因为它花费的时间太长，我不认为这是内存问题，对吧？）。我如何重新设计以下算法，使其能够处理更大的输入？

Answer 1

我的建议：虽然原始函数在 ~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 的影响在完成所有数学运算以优化原始计算后应该可以忽略不计。我在分析之前做了这个优化。
也许一个完整的封闭形式的解决方案是可能的。我没有投入时间进行进一步调查。

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

efficiency graph size calculation with power function

python

runtime-error

time-complexity

simplify

pow