time-complexity - 阶乘的大 O 化简

Question

为以下函数计算 BigO 和常数：我不知道如何进一步简化它。有什么建议吗？谢谢

 T(n) =  (n!n+n^3)(n^2+7logn)      
      <= (n!n+n^3)(n^2 +7n)   (since n>= log n)
      <= (n!n+n^3)(n^2 +7n)    (n^3 >= 7n if n > 3) 
      <= (n!n+n^3)(n^2 + n^3)   
      <= (n!n+n^3)(n!n + n^3)  (n!n >= n^2)    
         :

标签： time-complexitybig-ocomplexity-theory

Answer 1

通过展开可以找到最高阶项：

 T(n) =  (n!n+n^3)(n^2+7logn) 
      =  n!n^3 + 6n!nlogn + n^5 + 7n^3logn

在这一点上，我们可以简单地比较术语，看看哪个最大：

n!n^3 vs 6n!nlogn
since n^2 > 7logn for n >= 4, n!n^3 > 7n!nlogn for n >= 1

n!n^3 vs n^5
since n! > n^2 for n >= 4, n!n^3 > n^5 for n >= 4

n!n^3 vs 7n^3logn
since n! > 7logn for n >= 4, n!n^3 > 7n^3logn for n >= 4

基于这一切，对于 n >= 4，

 T(n) =  (n!n+n^3)(n^2+7logn) 
      =  n!n^3 + 6n!nlogn + n^5 + 7n^3logn
     <=  n!n^3 + n!n^3 + n!n^3 + n!n^3
      = 4n!n^3
      = O(n!n^3)

如果您想找到另一个限制 n!n^3 的表达式，那很好，但我建议您为此提出另一个问题。