Big-Theta符號的這種推廣是否正確？

Question

假設您有一個算法，可以輸入大小爲n的輸入的多項式數完成，例如P(n)=2n^2+4n+3。該算法的漸近緊界限Θ(n^2)。

對於任何算法的Big-Theta符號是否爲n對於多項式的程度冪P(n)是真的嗎？或者是否有任何情況下不是這樣？

Answer 1

的多項式時間算法的複雜度是通過爲O（n ^ķ），其中0 < k ≤ ∞界定。這並不意味着所有的算法都具有多項式時間複雜度。有多種子多項式複雜度的算法。實例包括O（k）的（恆定的複雜性），O（^ķ√N）（K ^第根的n，其中1 ≤ k ≤ ∞），O（log n）的，O（loglogN個）等等。還有一些具有超多項式時間複雜度的算法。用於這種複雜性的實例爲O（ķ^Ñ），其中1 < k ≤ ∞，爲O（n！）等