嵌套嵌套循环的时间复杂度？

外循环执行了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]。