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)
, donden
es el número de elementos en la matrizitems
ym
es el número de claves en cada objeto de elemento.El método filter itera sobre cada elemento en la matriz
items
usando un bucle for que va desde0
hasta el número de claves en el objeto de elemento actual. Esto significa que para cada elemento, el bucle se ejecutam
veces. Si hayn
elementos, entonces el bucle se ejecuta un total den*m
veces.La instrucción
console.log
dentro 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)
.