Estoy tratando de calcular la complejidad del tiempo de esta línea en particular en una de mis funciones:
return [...cache.keys()].sort((a, b) => a - b); Se supone que esta línea devuelve una matriz ordenada de las claves ( cache ) del mapa. Sé que Array.prototype.sort() tiene una complejidad de tiempo O (n log n). ¿Cuál es la complejidad temporal de Map.prototype.keys() ?
Crear el iterador es O(1) , iterar todas las entradas y crear una matriz a partir de ellas es lineal en el tamaño de la colección: O(n) .
Dependiendo de la implementación, la cantidad de entradas eliminadas recientemente puede tener un impacto, pero nunca debe ser lo suficientemente grande como para cambiar la complejidad del tiempo y volverse no lineal.