多项式时间复杂度的负系数 [英] 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屋！