依賴嵌套循環的時間複雜性

Question

您好我一直在試圖瞭解這個嵌套循環的時間複雜度將是一段時間了。

int i = 1; 
while(i < n) { 
    int j = 0; 
    while(j < n/i){ 
     j++; 
    } 
    i = 2 * i; 
} 

基於夫婦計算我已經做了我認爲它的大O符號是O（日誌（n））的，但我不知道這是正確的。我試過尋找一些內部循環以這種速度加速的例子，但我找不到任何東西。

感謝

令人驚訝很少有人使用時，計算的複雜性是

Answer 1

一個信息：項之和等於平均乘以項的數量。換句話說，你可以用平均值替換一個變化的項，並得到相同的結果。

因此，您的外圍while循環重複O（log n）次。但是內部的while循環重複：n，n/2，n/4，n/8，...，1，這取決於我們的外部while的哪一步。但是（n，n/2，n/4，...，1）是幾何級數，其中log（n）項和比率1/2，其和爲n。（1-1/n）/ 1/2）= 2n-2 \在O（n）中。因此其平均值爲O（n/log（n））。由於它重複O（log（n））次，整個複雜度爲O（log（n）* n/log（n））= O（n）...