Soy bastante nuevo en Big O y no estoy seguro de cuál será la complejidad temporal del siguiente código:
const items = [ {type: 'phone', name: 'iPhone', color: 'gold'}, {type: 'phone', name: 'Samsung', color: 'gold'}, {type: 'laptop', name: 'Chromebook', color: 'gray'}, {type: 'tv', name: 'LG', color: 'gray'}, {type: 'gooo', name: 'LG', color: 'silver'}, {type: 'phone', name: 'Nokia', color: 'gold'} ]; items.filter(item => { for(let i=0; i < Object.keys(item).length; i++) { console.log('item is', Object.keys(item)[i]) } }) ¿Podemos decir que esto es O(i + c) donde i son items y c es la console.log constante? ¿O necesitamos decir algo como O(i * j + c) donde j es el item individual, es decir, {type: 'phone', name: 'iPhone', color: 'gold'}
¿Alguien puede ayudarme? ¡Gracias de antemano!
El items.filter(() => { ... }) es un bucle => O(n) .
Tiene un bucle for dentro de él que recorre las claves de objeto => O(m * n) .
Object.keys() es O(m) en V8 y lo tiene dos veces en el bucle for (en la condición en que se llama en cada iteración y en el cuerpo del bucle), por lo que es => O(m ^ 2 * n) (donde m es el número de claves).
Además, puedes usar
for (let key in item) { // and do whatever you want with the key } en lugar de usar Object.keys .
Déjame cambiar un poco tu código:
items.filter(item => Object.keys(item).forEach(key => console.log("item is", key))); La lambda se ejecuta para cada elemento en items . La lambda itera sobre cada clave en un elemento y lo imprime. Por lo tanto, la complejidad temporal es O(n*m) para n = número de elementos ym = número de claves por elemento. Si el número de claves por artículo es fijo y relativamente pequeño, puede suponer O(n). La notación O grande es solo una estimación aproximada del tiempo de ejecución, los factores constantes no son tan interesantes.