递归结合循环实现数组扁平化的最坏时间复杂度是多少？

你贴的这个flattenDeep函数，最坏情况的时间复杂度是线性O(n)，其中n是原数组所有层级的元素总个数。

为什么是线性复杂度？ #

• 不管数组嵌套多深，每个元素只会被处理一次：要么直接被push到结果数组，要么作为子数组的元素被递归遍历后push。
• 递归调用的本质是遍历嵌套的子数组，每一层递归都不会重复处理已经遍历过的元素，所有元素的处理次数加起来就是总元素数n。

为什么会有指数级复杂度的误解？ #

可能是把这种扁平化递归和一些重复计算的递归场景搞混了（比如无缓存的斐波那契递归）。但这个扁平化逻辑里没有重复计算，每个元素只经过一次遍历和一次push操作，不存在指数级的重复处理。

举个最坏情况的例子：像[[[[[1]]]]]这种深度嵌套的单元素数组，总元素数是1，处理次数就是1次；如果是多层嵌套多元素的数组，比如[1, [2, [3, 4]], 5]，总元素数是5，每个元素都只被处理一次，时间复杂度还是O(5)也就是O(n)。

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