Soy consciente de que existe un método de matriz flat . pero me gustaría comprender mejor cómo ... y concat afectan la complejidad del tiempo.
function flat1(arr) { return arr.reduce( (flatArr, item) => { flatArr.push(...(Array.isArray(item) ? flat1(item) : [item])) return flatArr }, [] ) } function flat2(arr) { return arr.reduce( (flatArr, item) => { return flatArr.concat(Array.isArray(item) ? flat2(item) : item) }, [] ) } Mi intuición es que ambos enfoques toman O (n ^ 2) complejidad de tiempo en el peor de los casos, siendo n el número de elementos en la matriz original. Porque tanto concat como ... van a iterar a través de la matriz y tomará n para ambas operaciones. ¿Es correcto mi entendimiento?
¿Se prefiere un enfoque sobre el otro?
Necesitaré simplificar el problema al no aplanar recursivamente, sino solo un nivel:
function flat1(arr) { return arr.reduce((flatArr, item) => { flatArr.push(...(Array.isArray(item) ? item : [item])) return flatArr }, []) } function flat2(arr) { return arr.reduce((flatArr, item) => { return flatArr.concat(Array.isArray(item) ? item : [item]) }, []) } Supongamos que la cantidad de elementos en arr es n y la cantidad promedio de elementos en cada matriz de item es m . (Y los item que no son matrices cuentan en ese promedio como 1 ).
tanto
concatcomo...van a iterar a través de la matriz
Sí, ambos necesitan iterar a través del item que se les ha dado. Pero ese no es el punto. push modifica flatArr y toma O(m) tiempo para agregarle O(m) nuevos elementos.
Sin embargo, concat crea una nueva matriz, y para eso no necesita solo iterar item sino también flatArr . Dado flatArr contiene en promedio O(n/2*m) elementos, flatArr.concat(item) toma O(n/2*m + m) = O(n*m) .
Dado que cada una de estas operaciones se ejecuta una vez para cada elemento del arr , obtenemos
flat1 la complejidad temporal O(n*m) yflat2 la complejidad temporal O(n*n*m) que es peor.Las complejidades de tiempo de las funciones recursivas son mucho más complicadas ya que también dependen de cuántas matrices tenga en qué niveles de anidamiento. Ni siquiera se me ocurre una buena métrica para describir dicha estructura de datos :-)