嵌套多项式时间函数

Question

如果我在多项式时间子程序中运行多项式次数,那么在指数时间内完成这种方式的一些例子是什么？

"表明对多项式时间子程序的多项式调用次数可能导致指数时间算法." - HW的问题

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)在调用之前以O(x)次运行g,但总体而言O(2 ^ n).