JavaScript两种数组扁平化实现的时间复杂度是否一致？

时间复杂度判断是否正确 #

你的理解完全正确，两种手写实现的最坏时间复杂度确实都是O(n²)，其中n是原数组总元素个数，核心原因和你说的一致：展开运算符...和concat都需要遍历目标数组的所有元素完成复制操作，单次操作耗时和操作的数组长度正相关。

两种实现触发最坏时间复杂度的场景略有区别：

• 对flat2（使用concat的实现）：最坏场景是原数组为完全扁平化的一维数组。因为concat每次调用都会生成全新数组，需要把当前累加数组的所有元素和新元素全部复制到新数组中，长度为n的一维数组会触发1+2+3+...+n = n(n+1)/2次复制操作，直接达到O(n²)时间复杂度。
• 对flat1（使用push+展开的实现）：最坏场景是数组深度嵌套且每层仅包含1个嵌套子数组，比如结构为[[[[...[1,2,...,n]...]]]]。因为每一层递归都需要展开长度为n的子数组，总共有n层的情况下总遍历次数为n²，达到O(n²)时间复杂度。

两种实现的选择建议 #

更推荐使用flat1，原因如下：

• 常规场景下性能更优：flat1全程在同一个累加数组上做修改，不会像concat那样每次迭代都复制所有已有元素，大部分浅嵌套、元素分布均匀的场景下，时间复杂度接近O(n)，性能比flat2高出数倍。
• 内存效率更高：flat2每次调用concat都会生成临时数组，会产生大量无用的中间内存占用，GC压力远高于flat1。

注意flat1存在一个极端场景的限制：如果待展开的子数组长度超过JS引擎允许的函数最大参数数量（大部分引擎的上限是数万到数十万级别），push(...arr)会抛出参数过多的错误，这种场景可以把子数组遍历后逐个push，或者直接使用原生的Array.prototype.flat方法。

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