假设您有一个算法，对于输入大小n的输入，以多项式步数完成，例如，P(n)=2n^2+4n+3。该算法的渐近紧界Θ(n^2)。
是真的说任何算法的大θ表示法都是多项式次的幂，还是有任何情况下这不是真的？
最佳答案
多项式时间算法的复杂性受O（NK）的限制，其中0 < k ≤ ∞。这并不意味着所有的算法都具有多项式时间复杂度。有许多算法具有子多项式复杂度。实例包括O（k）（常数复杂度）、O（k n）（n的kthroot，其中1 ≤ k ≤ ∞）、O（log n）、O（log log n）等。还存在具有超多项式时间复杂度的算法。这种复杂性的例子是O（kn），其中1 < k ≤ ∞，o（n！）等等。
关于performance - Big-Theta表示法的这种概括正确吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16282939/