algorithm - 嵌套多项式时间函数

Question

如果我将多项式时间子例程运行多项式次数，有哪些在指数时间内完成的示例？

“显示对多项式时间子程序的多项式调用可能导致指数时间算法。”-硬件问题

Answer 1

好吧，如果我们把它当作一个“肮脏的把戏”问题:

def g(a):
    b = 0
    for i in range(a * 2):
        b += 1
    return b

def f(x):
    a = 1
    for i in range(x):
        a = g(a)

g(a) 在 O(a) 中运行，f(x) 在调用 g 之前运行 O(x) 次，但总的来说是 O(2 ^ n )。