请求验证：该三重嵌套循环的时间复杂度是否为O(N log N)

先看原函数代码：

function fun(N) {
    
    let k = 0;
    for(let i = N; i >= 1; i = i/2) {
        for (let g = 1; g <= N/i;g = g + 1) {
            for (let h =1; h <= i;h = h + 1) {
                k = k + 1;
            }
        }
    }
    return k;
}

你的结论**O(N log N)**是正确的，但分析过程存在错误，具体纠正如下：

• 外层循环迭代次数确实是log₂N（忽略常数项的近似值），这部分判断没问题。
• 中间循环执行次数是N/i，但不能直接认为其贡献因子是N，必须结合内层循环的执行次数一起计算：对于外层循环的每个i值，中间循环每执行1次，内层循环就执行i次，因此单轮外层循环的总操作数是(N/i) * i = N。
• 你错误地跳过了最内层循环的考量，但实际上正是内层与中层循环的次数相乘后抵消了i，才让单轮外层的操作数固定为N。

最终，外层循环共执行log₂N次，每次对应N次操作，总操作数为N * log₂N，所以时间复杂度为O(N log N)。

内容的提问来源于stack exchange，提问作者Javier Tan