algorithm - 嵌套多项式时间函数

Question

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

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

score 7 · Accepted Answer

好吧，如果我们将此视为“肮脏的把戏”问题：

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)。

score 1 · Accepted Answer

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

例如，如果您以n ²复杂度n ³次运行子例程，则生成的算法将具有n ⁵运行时间复杂度，这仍然是多项式时间算法。

score 0 · Accepted Answer

f(a) = 2^a

g(b) =总和=0；对于 (i = 1..b) sum=sum+i

f(a) 是 O(n)

g(b) 是 O(n)

g(f(a)) 是指数的

3 回答 3