嵌套多项式时间函数

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)在调用g之前运行了O(a)次，f(x)运行了O(x)次，但总的来说是O(2 ^ n)。

Answer 2

你的问题有点令人困惑。但是如果你运行一个多项式时间子程序一个多项式次数你永远不会得到一个指数时间函数。在一个多项式时间子例程运行了多项式次之后，你仍然会得到一个多项式时间的运行时间复杂度。

例如，如果你运行一个子例程，复杂度为n²复杂度为n³，结果算法的运行时间复杂度为n⁵，这仍然是一个多项式时间算法。

Answer 3

f(a) = 2^a

g(b) = sum=0;For (i = 1..b) sum=sum+i

f(a) = O(n)

g(b) = O(n)

g(f(a))是指数