这是一个多项式时间算法吗？

Question

如果一个算法的输入大小是2^n，并且该算法在$O(n2^n)$时间内运行。在这种情况下，我们可以说该算法相对于输入大小以多项式时间运行吗？

- NARAYAN CHANGDER

Answer 1

是的，这将是一个O(k log k)时间复杂度的算法，其中k = 2^n。

- David Eisenstat

---

谢谢，@David。那么，我可以说这是多项式时间或伪多项式吗？我对这两个概念感到困惑。 - NARAYAN CHANGDER

一个好问题和一个好答案 - 一切都取决于正确的定义；让我感到有些困惑的是，例如对于矩阵乘法算法，运行时间通常以 n 来表示，而输入的大小却是 n*n。 - Codor

@NARAYANCHANGDER 多项式。一个伪多项式运行时间的例子是 O(k^log k)。 - David Eisenstat