计算此函数的复杂度

Question

这是功能：

void f(int n)
{
 for(int i=0; i<n; ++i)
   for(int j=0; j<i; ++j)
     for(int k=i*j; k>0; k/=2)
       printf("~");
}

我认为，时间复杂度的计算最终将是这样的：

log((n-1)(n-2))+log((n-1)(n-3))+...+log(n-1)+log((n-2)(n-3))+...+log(n-2)+...log(2)

因此，我得到的时间复杂度为nlog(n!)（因为loga+logb=log(a*b)n-1，n-2，n-3，...总共出现n-1次。

但是，正确的答案是n^2*logn，我不知道我的错误在哪里。这里有人可以帮忙吗？

非常感谢！

Answer 1

log(n!)可以近似为(n+1/2)log(n) - n + constant（参见https://math.stackexchange.com/questions/138194/approximating-log-of-factorial）

所以复杂度是n*n*log(n)预料之中的。

更简单：独立地逐个循环地计算复杂度并将它们相乘。

前 2 个外循环：微不足道：n每个，这使得n^2

内循环：具有log(n**2)相同的复杂性log(n)

n^2log(n)正确答案也是如此。