如果我将多项式时间子例程运行多项式次数,有哪些在指数时间内完成的示例?
“显示对多项式时间子程序的多项式调用可能 导致指数时间算法。”-硬件问题
最佳答案
好吧,如果我们把它当作一个“肮脏的把戏”问题:
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 )
。
关于algorithm - 嵌套多项式时间函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16241943/