math - 为什么 n^O(1) 表示多项式时间？

Question

如果某个算法的运行时间对于某个 k为 O(n ^{k )，则该算法在多项式时间内运行。}但是，我也看到多项式时间定义为时间 n ^O(1)。

我对此有一些疑问：

1. 为什么是 n ^O(1)多项式时间？k怎么了？
2. 如果 n ^O(1)是多项式时间，则 3n ²应该是 n ^O(1)。但是3去哪儿了？这是如何运作的？

谢谢！

Answer 1

^{当你有一个像“运行时是 O(n)”或“运行时是 O(n 2} ) ”这样的表达式时，O(n) 和 O(n ² ) 术语不是实际的函数。相反，它们是具有某些属性的其他功能的占位符。例如，采用以下语句：

算法的运行时间是 O(n)

这句话真的意味着

有一些函数 f(n)，其中算法的运行时间是 f(n) 并且 f(n) = O(n)

例如，如果一个函数的实际运行时间是 137n + 42，那么“算法的运行时间是 O(n)”的说法是正确的，因为有一些函数（即 f(n) = 137n + 42）的运行时间为算法是 f(n) 和 f(n) = O(n)。

鉴于此，让我们考虑一下“算法的运行时间为 n ^O(1) ”这句话的含义。该语句等价于

有一些函数 f(n)，其中算法的运行时间是 n ^f(n)并且 f(n) = O(1)

现在我们已经更清楚地了解了术语，这到底是什么意思？直观地说，如果一个函数最终从上方以某个常数为界，则该函数是 O(1)。因此，一旦 n 变得足够大，任何 O(1) 的函数 f(n) 必须满足 f(n) ≤ k。因此，至少直观地说，n ^O(1)的意思是“n 提升到最多为 k 的某个幂”，这听起来像是多项式函数的定义。

当然，还有一个令人讨厌的恒定因素问题。函数 137n ³肯定是 O(n ³ )，但它前面有一个巨大的常数项。另一方面，如果我们有一个形式为 n ^{O(1)的函数，则在 n 3}前面没有常数项。我们如何处理这个？

这是我们可以用数学变得可爱的地方。在 137n ³的情况下，注意当 n > 1 时，我们有

137n ³ = n ^{log _n 137} n ³ = n ^{3 + log _n 137}

_{请注意，这是 n 的 log n} 137次幂。虽然看起来函数 log _n 137 会随着 n 的增大而增长，但它实际上具有相反的行为：它随着n 的增长而减小。这样做的原因是我们可以使用基础公式的变化将 log _n 137 重写为

日志_n 137 = 日志 137 / 日志 n

当 log n 减少时，这在长期内明显减少。因此，表达式 3 + log _n 137 最终会受到某个常数的限制，所以它是 O(1)。

使用这种技术，可以将 O(n ^k ) 转换为 n ^O(1)，方法是选择 n 的指数为 k 加上出现在大的 n ^k项前面的常数因子的对数底 n -O 表示法。类似地，我们可以通过选择 k 作为任何常数，将 n ^O(1)转换回O(n ^k )，该常数使 O(1) 项在 n 的指数中隐藏的函数的上限。

希望这可以帮助！