const anagram = (str1, str2) => { str1 = str1.split(''); str2 = str2.split(''); let frequencyCounter1 = {}; let frequencyCounter2 = {}; for(let val of str1) { frequencyCounter1[val] = (frequencyCounter1[val] || 0) +1; } for(let val of str2) { frequencyCounter2[val] = (frequencyCounter2[val] || 0) +1; } for(let key in frequencyCounter1) { if(!(key in frequencyCounter2)) { return false; } if(frequencyCounter1[key] !== frequencyCounter2[key]) { return false; } } return true; } anagram('racecar', 'racecar');Este desafío pide usar un patrón de contador de frecuencia para probar si str2 es un anagrama de str1. La respuesta proporcionada es supuestamente O(n). ¿Cómo es esto posible con esta declaración if?
if(!(key in frequencyCounter2)) { return false; }¿No sugeriría esto que va a recorrer el objeto para asegurarse de que contiene esa clave, por lo tanto, tiene bucles anidados y O (n ^ 2)?
en realidad es O(n) porque
for(let key in frequencyCounter1) { if(!(key in frequencyCounter2)) { return false; } if(frequencyCounter1[key] !== frequencyCounter2[key]) { return false; } }está iterando sobre el contador de frecuencia 1 O (n) y luego encuentra cada clave de iteración del contador de frecuencia 1 en el contador de frecuencia 2 y los objetos js son básicamente pares clave-valor, por lo que encontrar una clave requerirá O (1). por lo tanto, la complejidad temporal total es O(n)