问代码O(nlog(n))的T(n)是怎样的？

EN

对于i=1，内循环执行n次数。对于i=2，内环执行n/2时间等等。运行时间是T(n) = n + n/2 + n/3 + ... + n/n。这等于n(1 + 1/2 + 1/3 + ...+ 1/n) = nH(n)，其中H(n)是第n次调和数。H(n) ~ lg n导致了O(n lg n)的运行时间。

for(i = 1; i <= n; i++)  // Executes n times
{    
    for(j = 1; j <= n; j = j + i)
    {   // This loop executes j times with j increases by rate of i
        printf(“Hi”);
    }
}

内环对n/i的每个值执行i时间。它的运行时间为1，n中所有nxSum(n/i)的i。

=> O(nlogn)