这个程序的时间复杂度怎么这么大哦(n^2logn)？

Question

  int unknown(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;
    }

我说的复杂度是对的吗？如果是的话，怎么样？请详细说明。

Answer 1

外层循环执行n / 2次

内循环执行 (n - 2) / 2 次。

（忽略整数除法的截断效应）

所以复杂度是 O(n^2)。 （假设所有算术运算的复杂度为 O(1)）