代码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)。

Answer 2

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每个值。其运行时间为nxSum(n/i)所有i在[1，N]

=>O(nlogn)