多项式时间复杂度的负系数 [英] Negative Coefficients in Polynomial time Complexity
问题描述
假设某些算法具有多项式时间复杂度 T(n),那么任何一项是否都可能具有负系数?直观上,答案似乎是一个明显的否,因为没有任何算法可以减少前面步骤所花费的现有时间,但是我想确定。
Assuming some algorithm has a polynomial time complexity T(n), is it possible for any of the terms to have a negative coefficient? Intuitively, the answer seems like an obvious "No" since there is no part of any algorithm that reduces the existing amount of time taken by previous steps but I want to be certain.
推荐答案
在讨论多项式复杂度时,只有度数最高的系数才算在内。
When talking about polynomial complexity, only the coefficient with the highest degree counts.
但是我认为您可以让T(n)= n * n-n = n *(n-1)。 n-1代表您在第一次或最后一次迭代中不执行的操作。
But I think you can have T(n) = n*n - n = n*(n-1). The n-1 would represent something you don't do on the first or last iteration.
无论如何,复杂度仍然是n * n。
Anyway, the complexity would still be n*n.
这篇关于多项式时间复杂度的负系数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!