algorithm - 时间复杂度n^k，k是数值变量，这个是伪多项式吗？

Question

如果算法的时间复杂度为 n^k

n 为元素个数，k 为数值变量，上限为 720，下限为 1，k 与 n 无关

O(n^k) 可以称为伪多项式吗？

如果不是，你认为这比 O(2^n) 更好吗？

---

编辑：

如果 k 没有上界，O(n^k) 可以称为伪多项式吗？

如果不是，你认为这比 O(2^n) 更好吗？

标签： algorithm

Answer 1

由于k的上限为720，这意味着最坏的情况，算法按O(n ⁷²⁰ )缩放，因此这意味着它是多项式的。

渐近地说，这比O(2 ⁿ )好，因此这意味着最终，对于足够大的n，O(n ⁷²⁰ )算法将优于O(2 ⁿ )算法。但是，这取决于很多因素，如果对于实际输入来说这更好。

例如，如果第一个算法恰好需要n ⁷²⁰步，而第二个算法需要2 ⁿ（大 oh 并不意味着这一点），那么它将持有的第一个n是n=9'516。这意味着第一个算法将执行3.070×10 ²⁸⁶⁵步，而第二个算法将执行 3.994 ×10 ²⁸⁶⁵步。如果这些是简单的 CPU 指令，那么对于今天的技术，这将是几个数量级太大而无法实现。

例如，如果n通常很小，并且指数算法的“常数因子”较低，那么在实践中，有时使用O(2 ⁿ )算法会更好。但如前所述，这实际上取决于算法和输入的细节。