代碼O（nlog（n））的T（n）如何？

我沒有得到第二個for循環的T（n）是log（n）的部分。兩個循環都通過 i連接，並且令人困惑。代碼O（nlog（n））的T（n）如何使用基本乘積規則？代碼O（nlog（n））的T（n）如何？

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

來源

2014-10-05 Hari

看看'j = j + i' – tangrs 2014-10-05 11:49:26

是的j = j + i，我們如何繼續。如何計算依賴循環的T（n）？ – Hari 2014-10-05 11:51:20

非常類似的問題：http://stackoverflow.com/questions/18863422/asymptotic-analysis – 2014-10-05 12:02:58

對於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)。

來源

2014-10-05 11:55:06 saadtaame

真棒！但是，你能用產品規則找到T（n）來幫助我解決問題嗎？ @saadtaame – Hari 2014-10-05 11:56:49

這是一款產品！第二個因素與你習慣的有點不同。如果內循環執行了'm'次，例如你會寫'm + m + ... + m'，'m'出現'n'次。說得通？ – saadtaame 2014-10-05 12:06:15

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)

來源

2014-10-05 11:53:05 P0W

代碼O（nlog（n））的T（n）如何？

回答

相關問題