代码O(nlog(n))的T(n)如何？

Question

我没有得到第二个for循环的T(n)是log(n)的部分.两个循环都是由i连接而且令人困惑.使用基本产品规则的代码O(nlog(n))的T(n)是多少？

for(i = 1; i <= n; i++)
{
   for(j = 1; j <= n; j = j + i)
   {
      printf("Hi");
   }
}

Answer 1

对于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).