你能告诉我这个算法的运行时复杂度是多少吗

Question

此函数只接受多维数组并使其成为平面

例如flatArray([1，[1，2，4，[2,3]]，1](->[1,1,2,4,2,3,1]

我想知道这个算法的时间复杂度是多少。

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;
};

Answer 1

函数需要O(n²(时间。最坏的情况是类似[1,[2,[3,[4,[5,[6...]]]]]]的情况，其中每个元素将被复制到一个新列表中n-1次。

要在O(n(时间内实现此功能，您必须避免所有复制：

let flatArray = function(numsArr){
let container = [];
function addArray(arr) {
for (const val of arr) {
if (Array.isArray(val)) {
addArray(val);
} else {
container.push(val);
}
}
}
addArray(numsArr);
return container;
}