Este es un fragmento de código que escribí para verificar si dos cadenas son anagramas. Esto no es tarea, estoy aprendiendo DS&A por mi cuenta.
Me parece que la O grande debería ser O(N) porque hay 2 bucles for separados, pero el segundo bucle for me preocupa, específicamente la llamada Object.entries() . ¿La complejidad de tiempo final es O (N) u O (N ^ 2) aquí?
function isAnagram(origStr, checkStr) { if (origStr.length !== checkStr.length) { return false; } const origFreqCounter = {}; const checkFreqCounter = {}; let countFreq = (str, counter) => { for (const c of str) { counter[c] = counter[c] + 1 || 1; } }; countFreq(origStr, origFreqCounter); countFreq(checkStr, checkFreqCounter); // Is this O(N) or O(N^2)? for (const [key, value] of Object.entries(origFreqCounter)) { if (checkFreqCounter[key] !== value) return false; } return true; } console.log(isAnagram('', '')) // true console.log(isAnagram('aaz', 'zza')) // false console.log(isAnagram('anagram', 'nagaram')) // true console.log(isAnagram("rat","car")) // false) console.log(isAnagram('awesome', 'awesom')) // false console.log(isAnagram('amanaplanacanalpanama', 'acanalmanplanpamana')) // false console.log(isAnagram('qwerty', 'qeywrt')) // true console.log(isAnagram('texttwisttime', 'timetwisttext')) // trueSí, es O(n) .
Esta función itera sobre la longitud de la cadena, sin bucles anidados:
let countFreq = (str, counter) => { for (const c of str) { counter[c] = counter[c] + 1 || 1; } }; Esa función se llama dos veces, y no en un bucle, por lo que es O(n) .
Luego Object.entries itera sobre las entradas del objeto origFreqCounter . El objeto origFreqCounter no tendrá más entradas que la cantidad de caracteres en la cadena origStr , por lo que también es O(n) .
O(n) + O(n) + O(n) = O(n) .
O, para ser pedante: el algoritmo depende del tamaño de origStr y checkStr , que no son necesariamente iguales, por lo que sería más apropiado llamarlo O(n + m) .