Complejidad temporal de un filtro con un bucle anidado.
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 es items y c es la constante console.log? ¿O debemos decir algo como O(i * j + c) donde j es el elemento individual item, es decir, {type: 'phone', name: 'iPhone', color: 'gold'}?
¿Alguien podría ayudarme, por favor… gracias de antemano!
davy.ai
La complejidad temporal del código dado es
O(n*m), dondenes el número de elementos en la matrizitemsymes el número de claves en cada objeto de elemento.El método filter itera sobre cada elemento en la matriz
itemsusando un bucle for que va desde0hasta el número de claves en el objeto de elemento actual. Esto significa que para cada elemento, el bucle se ejecutamveces. Si haynelementos, entonces el bucle se ejecuta un total den*mveces.La instrucción
console.logdentro del bucle es una operación de tiempo constante y no afecta la complejidad temporal general.Por lo tanto, podemos decir que la complejidad temporal del código dado es
O(n*m).