询问双层循环反转后的时间复杂度：O(n)、O(nlogn)还是O(logn)？

已知如下双层循环的时间复杂度为O(N)：

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

现分析内外层反转后的循环时间复杂度，反转后的代码如下，需判断其复杂度为O(n)、O(nlogn)还是O(logn)：

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

复杂度推导 #

1. 外层循环次数：i从1遍历到n-1，共执行n-1次，近似为n次。
2. 内层循环次数：对于每个i，j从1开始以2的倍数递增，直到j < i停止。内层循环的执行次数等于满足2^k < i的最大整数k，也就是**⌊log₂i⌋**次（比如i=4时，j取1、2，共2次，对应log₂4=2）。
3. 总执行次数求和：
   总语句执行次数是所有i从1到n-1的⌊log₂i⌋之和，即：

   S = log₂1 + log₂2 + log₂3 + ... + log₂(n-1)
   

   利用对数加法性质logₐx + logₐy = logₐ(xy)，可转化为：

   S = log₂(1×2×3×...×(n-1)) = log₂((n-1)!)
   

4. 渐近复杂度简化：
   根据斯特林公式，阶乘(n-1)!的近似值为(n-1)^(n-1)/e^(n-1) × √(2π(n-1))。对其取以2为底的对数后，主导项为(n-1)log₂(n-1)，忽略低阶项和常数后，总复杂度的主导项是nlogn。

结论 #

Answer: O(nlogn)

内容的提问来源于stack exchange，提问作者Mr Right