時間複雜度（嵌套循環）

Question

你如何計算出這個的時間複雜度？

int count=0; 

for (int i=1 ; i < n; i*=4) 

    for (int j=1;j<=n;j++) 

       count++; 

Answer 1

TL;博士：在發佈代碼的複雜性：O(nlogn)

讓我們來分析它從內到外。對於i的每個值，內循環重複自己精確地爲n次。

外循環重複自身，而i < n和i每次乘以4。這意味着，在第一次迭代之後，i=1，然後i=4, i=16, i=64, ....和k'th迭代i = 4^(k-1)之後。
這意味着，在停止時：

i >= n 
4^(k-1) >= n 
log_4(4^(k-1)) >= log_4(n) 
k-1 >= log_4(n). 

這意味着外環將重複log_4(n) + 1。

總結它一起帶給你內在的循環重複n*(log_4(n)+1)倍，這是O(nlogn)