Soy relativamente nuevo en el aprendizaje de la notación Big-O y esperaba que alguien pudiera arrojar algo de luz sobre una pregunta que, aunque simple, me ha estado molestando. Esta pregunta surgió en un contexto diferente al que mostraré a continuación, pero responde a la misma inquietud. Digamos que tenemos una matriz de entrada de N elementos y un ciclo for que recorrerá estos N elementos. Sin embargo, dentro del ciclo, realizamos algunas creaciones de matrices de tamaño constante de tamaño 2. Además, ignore la trivialidad de esta operación, ayuda a simplificar el problema original en el que estaba trabajando.
for (let i = 0; i < array.length; i++) { const newArray = [array[i], array[i+1]]; // Do some other stuff... }Estoy pensando que la complejidad de esta operación sería O(2), pero realizamos esta operación N veces, lo que da como resultado O(2N) u O(N) ya que ignoramos las constantes. Y aunque asignamos memoria en cada ciclo, se limpia entre cada iteración posterior y luego una vez que finaliza el ciclo, por lo que la complejidad del espacio seguiría siendo O (1). ¿Estoy en el camino correcto? ¡¡Muchas gracias!!
O(N) ya que ignoramos las constantes.
Sí: esta es la complejidad del tiempo.
Y aunque asignamos memoria en cada ciclo, se limpia entre cada iteración posterior y luego una vez que finaliza el ciclo.
No necesariamente: la recolección de basura probablemente no ocurrirá exactamente en cada bucle. Los datos quedan fuera del alcance, pero el GC generalmente se procesa por lotes. Es un detalle de implementación que la teoría de la complejidad ignora.
Supongo también que no está empujando esta matriz a otra matriz ni a nada que aún haga referencia a ella después de que finalice el ciclo. Eso cambiaría la complejidad del espacio de la función.
la complejidad del espacio seguiría siendo O(1).
Sí.
Aunque la complejidad del espacio se ve bien, las asignaciones de memoria repetidas en un bucle potencialmente activo pueden ser costosas en una carga de trabajo real, por lo que no necesariamente puede ignorar esta asignación por completo. O (1) no es una garantía de que no tenga un problema de rendimiento, solo que a medida que n aumenta, el costo permanece igual. Una función que asigna una sola matriz de un tamaño fijo de 1 millón sigue siendo O(1).
Pero no me preocuparía prematuramente hasta que vea un problema de rendimiento real y lo haya identificado con éxito como un cuello de botella a través de la creación de perfiles. Algunos compiladores podrían optimizar esto en variables separadas para evitar la asignación.