Is this generalization of Big
Say you have an algorithm that completes in a polynomial number of steps for the input of size n , like, for example, P(n)=2n^2+4n+3 . The asymptotic tight bound for this algorithm Θ(n^2) .
Is it true to say that the Big-Theta notation for any algorithm is n to the power of the degree of the polynomial P(n) , or are there any cases where that is not true?
The complexity of polynomial time algorithms are bounded by O(nk) , where 0 < k ≤ ∞ . It doesn't mean that all the algorithms are having a polynomial time complexity. There are many algorithms with sub polynomial complexity. Examples include O(k) (constant complexity), O(k√n) (kth root of n, where 1 ≤ k ≤ ∞ ), O(log n) , O(log log n) , etc. There are also algorithms which are having super polynomial time complexity. Examples for such complexities are O(kn) , where 1 < k ≤ ∞ , O(n!) , etc.
上一篇: 使用最差/平均/最佳情况进行渐近分析
下一篇: 这是Big的泛化吗？