请求解析给定C++函数的时间复杂度，对循环复杂度存疑

先看给出的代码：

void fun(int n) { 
  int i,j,k, count = 0;
  for(i = n/2; i <= n; i++) 
    for(j = 1; j <= n; j = 2*j)
      for(k = 1; k <= n; k++) 
        count++;
}

我们逐个分析每个循环的迭代次数，再推导总时间复杂度：

• 第一层循环（i循环）：i从n/2开始，到n结束，每次加1。迭代次数为 n - n/2 + 1，当n足够大时常数项可忽略，近似为n/2，时间复杂度为O(n)。

• 第二层循环（j循环）：j从1开始，每次乘以2，直到j <= n停止。这是指数增长型循环，迭代次数等于满足2^k <= n的最大k值加1。比如n=8时，j取1、2、4、8，共4次，对应log₂(8)+1=4；n=16时迭代5次。所以迭代次数为O(log n)——你之前误以为是O(n)，是混淆了线性增长（每次加1）和指数增长（每次翻倍）的循环逻辑，这个循环的变量增长速度是指数级，因此次数是对数级而非线性级。

• 第三层循环（k循环）：k从1到n，每次加1，迭代n次，时间复杂度为O(n)。

总时间复杂度是三个循环的复杂度乘积：O(n) * O(log n) * O(n) = O(n² log n)。

内容的提问来源于stack exchange，提问作者b. tsutskiridze