算法的時間複雜度分析

Question

我沒有得到的時間複雜度足夠的知識，所以我的問題是：

是否有任何直接的公式來計算時間的算法的複雜性，示例 - 我讀的地方，像個大O這個代碼就是n * LOG 2（N），所以你可以告訴我，他們是如何得到這體現在哪裏？

for(i=1;i<=n;i=i*2) 

for this loop我無法計算出大的O.這個循環將對n = 100的值進行7次迭代。如何能夠幫助到給定的公式？

Answer 1

本身，此循環將遍歷ceil(log(n))次。這是log(n)與2的對數基數。這是因爲在ceiling(log(n))乘法後，i將達到或通過n，任何n。一個簡單的例子：

對於​​

Iteration:  i: 
    1   1 
    2   2 
    3   4 
    4   8 
    5   16 
    6   32 
    7   64 
    8   128 

所以i將在8日反覆檢查，你不進入循環，因爲它不是<= 100。這將是nlog2(n)你的建議，如果有另一個內部循環，通過n次完全循環。然後兩個環路兩次獲得相乘得到的總時間。的代碼