Если я запустил подпрограмму полиномиального времени многочленное число раз, каковы некоторые примеры того, как это делается в экспоненциальном времени?Вложенные функции полиномиального времени
«показать, что многочленное число вызовов подпрограмм полиномиального времени может привести к экспоненциальному алгоритму». - проблема HW
Ну, если рассматривать это как «грязный трюк» вопрос:
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)
г (а) работает в O (а), ф (х) работает в O раз (х) перед вызовом до g, но в целом это O(2^n).
O (a) не является многочленом. Точно так же, как проблема ранца с O (NV), но она не полиномиальная. – Sayakiss
g определенно является полиномиальным относительно его входного параметра, но да, это решение, которое может быть неправильным. –
Сложность измеряется входной длиной. Чтобы ввести только бит log (a). Таким образом, вход с длиной la будет стоить O (2^la). Это экспоненциально. – Sayakiss
Ваш вопрос немного запутан. Но если вы выполняете подпрограмму полиномиального времени, число полиномов за раз вы никогда не получите экспоненциальную функцию времени. После выполнения подпрограммы с полиномиальным временем многочленовое число раз, вы все равно получите многочленную временную сложность.
Например, если запустить подпрограмму с п сложности п количество раз, в результате чего алгоритм будет иметь п время выполнения сложности, которые до сих пор за полиномиальное время алгоритм.
Надеюсь, что есть решение, иначе мой профессор не очень милый ... – theB3RV
Я понимаю, это означает, что это не правильный пример. .. – theB3RV
полиномиальный полином по-прежнему является полиномом. Таким образом, вы никогда не получите экспоненциальный алгоритм, если в этом вопросе не будет никаких дополнительных условий. – Deepu
F (A) = 2^а
г (б) = сумма = 0; для (я = 1..b) сумма = сумма + I
F (а) представляет собой О (п)
г (б) представляет собой О (п)
г (е (а)) экспоненциально
Вы уверены, что существует хотя бы один пример? – Sayakiss
Надеюсь, что в противном случае im получит -10% на это назначение hw – theB3RV
Как определить подпрограмму полиномиального времени? Возможно, в этой проблеме есть трюк. –