algorithm - 给定 C 函数 theta(nlogn) 或 theta(n^2logn) 的时间复杂度？

Question

我计算了以下 C 函数的时间复杂度，它即将到来theta (nlogn)。你能告诉我我是否错了，给出的答案是theta(n^2logn)？我刚刚开始阅读这些概念。

int unk(int n)
{
  int i,j,k=0;
  for(i=n/2;i<=n;i++)
     for(j=2;j<=n;j=j*2)
        k=k+(n/2);
  return k;
}

我所做的是：外循环执行(n/2+2)次数，内循环执行次数，循环(n/2+1)(logn+1)体中的语句执行次数。(n/2+1)(logn)因此总运行时间为theta(nlogn)。（假设所有成本为1，日志为是二进制对数）。

Answer 1

我认为您的答案是正确的，确实是 theta(nlogn) 。但是，您的分析似乎有些错误。

外循环执行 O(n/2) 次。

内循环每次外循环迭代执行 O(logn) 次。

通过将两者相乘并去掉常数，您可以得到O(n) * O(logn) = O(nlogn).