对大符号的推广是正确的吗?

Question

假设您有一个算法，它以多项式的步骤完成大小为n的输入，例如，P(n)=2n^2+4n+3。该算法的渐近紧界Θ(n^2) .

是否说任何算法的Big-Theta符号都是n的多项式P(n)的次幂，或者是否存在不正确的情况?

Answer 1

多项式时间算法的复杂度以O(n^k)为界，其中0 < k ≤ ∞。这并不意味着所有算法的时间复杂度都是多项式。有许多算法具有次多项式复杂度。例子包括 O (k) (恒定的复杂性), O(<一口> k √n) (k <一口> 共舞,√n, 1 ≤ k ≤ ∞), O (log n) , O (log n) ,等等。也有一些算法具有超多项式的时间复杂度。这种复杂性的例子有O(kⁿ)，其中1 < k ≤ ∞、O(n!)等等。