您能解释一下如何找到时间复杂度吗？
sum=0; for(k=1;k<=n;k*=2) for(j=1;j<=k;j++) sum++;
因此，我知道外循环的时间复杂度为O（logn），但是由于内循环的迭代取决于外循环的值，因此该算法的复杂度不是O（nlogn）。
这本书说是O（n）。
我真的不明白这是怎么回事（n）…有人可以解释一下…如果您能详细介绍一下，我将非常感激：D
数学解决方案将帮助我更好地理解…
外循环执行了log（Base2）n次，所以它是O（log（Base2）n）。
内循环对于外循环的每次迭代执行k次。现在在外循环的每次迭代中，k递增为k * 2。
因此内部循环迭代的总数= 1 + 2 + 4 + 8 + … + 2 ^（log（Base2）n） = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + … + 2 ^ log（ Base2）n （几何级数） = 2 ^（（log（base2）n + 1）-1 /（2-1） = 2n-1。 = O（n） 因此内环为O（n）。因此总计时间复杂度= O（n），因为O（n + log（base2）n）= O（n）
更新：它也是O（nlogn），因为对于大的n值，nlogn >> n，但是它不是渐近紧的。您可以说它是o（nlogn）[Small o]。
