algorithm - 算法时间复杂度计算

Question

下面程序的复杂度是多少:

void function(int n)
{
int i, j, k , count =0;
for(i=n/2; i<=n; i++)
  for(j=1; j=j + n/2<=n; j++)
      for(k=1; k<=n; k= k * 2)
         count++;
}

现在根据我的理解，外循环执行了 n/2 次。内循环执行 n/2 次，第三个内循环执行日志 n 次。现在，如果我们将算法的时间复杂度表示为函数 T(n)。

T(n)=n/2n/2log n=n^2/4*log n

现在，对于非常大的 n 项输入，log n 与项 n^2 相比变得太小了。所以根据我的理解，算法的时间复杂度必须是 O(n^2)。但是我已经检查了上面这个程序的答案，它说答案是 O(n^2logn)。

为什么我们不能忽略 n 值较大时的 log n 项？还是我算错了？

Answer 1

您只能忽略常量值。如果 n 增加，log(n) 也会增加。