咨询多维数组扁平化算法flatArray的时间复杂度

先看你提供的扁平化实现代码：

let flatArray = function(numsArr){
    let container = [];
        for(let i = 0;i<numsArr.length;i++){
            if(Array.isArray(numsArr[i])){
                container = [...container,...flatArray(numsArr[i])]
            }else{
                container.push(numsArr[i])
            }
            counter ++
        }
    return container;
};

时间复杂度结论 #

这个实现的最坏时间复杂度为O(N²)，其中N是扁平化后最终数组的元素总个数。

具体分析 #

1. 基础遍历开销：每个元素最终都会被访问一次，这部分是O(N)的固定开销。
2. 数组合并的额外开销：核心问题出在container = [...container,...flatArray(numsArr[i])]这行代码。扩展运算符会创建新数组，并且需要遍历当前container的所有元素和递归返回的子数组元素，把它们逐一复制到新数组中。
   • 在最坏嵌套场景下（比如深度嵌套的单元素数组[[[[...[1]...]]]]，或者每个元素都是独立子数组的结构[[1], [2], [3], ..., [N]]），每次合并都会重复遍历已有的结果元素。以深度嵌套的单元素数组为例，每次递归返回1个元素，合并时需要遍历已有k个元素+1个新元素，总操作次数是1+2+3+...+N = O(N²)。
   • 如果输入数组本身就是完全扁平化的，所有元素直接用push添加，此时时间复杂度是O(N)，这是最优情况，但算法的时间复杂度通常以最坏情况为准。

优化方向 #

要把时间复杂度降到O(N)，可以避免每次合并时复制整个数组：

• 改用container.push(...flatArray(numsArr[i]))，直接将子数组的扁平化结果追加到容器末尾，无需创建新数组；
• 或者将容器作为参数传入递归函数，递归过程中直接向同一个容器添加元素，避免多次数组复制操作。

内容的提问来源于stack exchange，提问作者Luka Fridonich Donadze