时间戳

首页 > 解决方案 > 循环中带有函数*函数的函数的时间复杂度

time-complexity - 循环中带有函数*函数的函数的时间复杂度

问题描述

你能帮我找出以下函数的复杂性吗：

proc (int n) 
{
 for (i=0 ; i<n ; i++)
 {
   x = g(n)+f(n) ;
   for (j=0 ; j<n ; j++)
    {
      y=h(j)*g(j) ;
    }
  }
return x+y ;
}

f = O(n^2)，g = O(n)，h = Θ(log(n))。

我不确定的事情：

  1. 对于我 n*log(n)，“y = h(j) * g(j)”的复杂度是多少？
  2. 如果在循环中是“y = h(j) * g(j)”还是只是“h(j) * g(j)”，复杂性是否存在差异？
  3. 是不是“x = g(n) + f(n)”的复杂度是n + n^2？

谢谢！

标签： time-complexity

解决方案

内循环的复杂度（总和h*g）

由于h(j) = Θ(log(j))和g(j) = O(j)的复杂度h(j).g(j)为O(j.log(j))，即<= K.j.log(j)K > 0。因此内循环产生

   K.(1.log(1) + 2.log(2) + ... + (n-1).log(n-1))
<= K'.n^2.log(n)

对于一个精心选择的常数K'，内循环给出了一个复杂性O(n^2.log(n))。

的复杂度g + f
g = O(n)，f = O(n^2)所以的复杂度f + g是O(n^2)。

总体复杂性
A：给定n项O(n^2)的总和。B：给定的项总和。f+gO(n^3)
j^2log(j)0 <= j < nO(n^3.log(n))

因此，您的方法的复杂性是O(n^3.log(n)).

推荐阅读