假设您有一个算法，它在输入大小为 n 的多项式步数内完成，例如，P(n)=2n^2+4n+3 。此算法 Θ(n^2) 的渐近紧界。
是否可以说任何算法的 Big-Theta 表示法都是 n 多项式 P(n) 的次方，或者是否存在在任何情况下都是不正确的？
最佳答案
多项式时间算法的复杂度受限于O(nk)，其中0 < k ≤ ∞ .这并不意味着所有算法都具有多项式时间复杂度。有许多具有次多项式复杂度的算法。例子包括O(k)(常数复杂度)，O(k√n)(kth根n, 其中 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/