依赖嵌套循环的时间复杂性

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）...