两个JavaScript函数的时间复杂度是否均为O(nlogn)？

这两个函数的时间复杂度并非均为O(nlogn)，具体分析如下：

函数loop1的时间复杂度 #

function loop1(arr) {
    for (let i = 0; i<arr.length; i++){
        for (let j=i; j<arr.length; j++){
            console.log(arr[j])
        }
    }
}

• 外层循环执行n次（n为数组长度）
• 内层循环的执行次数随i递减：i=0时执行n次，i=1时执行n-1次……直到i=n-1时执行1次
• 总执行次数为 n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，属于二次方级增长，因此时间复杂度为O(n²)

函数loop2的时间复杂度 #

function loop2(arr) {
    for (let i = 0; i<=arr.length; i++){
        for (let j=1; j<=Math.log(i); j++){
            console.log(arr[j])
        }
    }
}

• 外层循环执行n+1次（n为数组长度）
• 内层循环仅在i>1时有效（i=0和i=1时Math.log(i)为非正数，内层循环不执行），每次内层循环执行次数为Math.log(i)（对数底数不影响时间复杂度的阶）
• 总执行次数为 log2 + log3 + ... + logn，根据对数运算法则，该和等价于log(2×3×...×n) = log(n!)
• 结合斯特林公式，log(n!) ≈ nlogn - n，因此总执行次数的增长阶为O(nlogn)

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