什么是近似因子？

Question

近似因子与时间复杂度有何不同？例如，我听说过具有指数因子的多项式算法，这是什么意思？这是否意味着它在技术上不是多项式时间？

Answer 1

没有足够的声望点数，因此张贴为答案。

也许您在两种不同意义上使用 factor 是混淆的根源。时间只是许多可能的复杂性因素中的一个因素，例如存储、带宽等。指数因素在多项式算法的情况下指的是数学方程式中各项的因数。它们不一定暗示时间是一个因素，但也不排除它。这取决于算法建模的内容。