Big O de arrays JavaScript
Los arrays en JavaScript son muy fáciles de modificar añadiendo y eliminando elementos. Enmascara un poco el hecho de que la mayoría de las matrices de idiomas son de tamaño fijo y requieren operaciones complejas para cambiar el tamaño. Parece que JavaScript hace que sea fácil escribir código de matriz de mal rendimiento. Esto lleva a la pregunta:
¿Qué rendimiento (en términos de gran complejidad de tiempo O) puedo esperar de las implementaciones de JavaScript en lo que respecta al rendimiento de la matriz?
Asumo que todo lo razonable Las implementaciones de JavaScript tienen al menos las siguientes O grandes.
- Access-O (1)
- Apéndice-O(n)
- Anteponiendo-O (n)
- Inserción-O(n)
- Supresión-O (n)
- Intercambio - O (1)
JavaScript le permite rellenar previamente una matriz con un tamaño determinado, utilizando la sintaxis new Array(length). (Pregunta adicional: Está creando una matriz de esta manera O(1) u O (n)) Esto es más como una matriz convencional, y si se usa como una matriz de tamaño predeterminado, puede permitir O (1) anexar. Si se agrega lógica de búfer circular, puede lograr O (1) anteponiendo. Si se utiliza una matriz de expansión dinámica, O(log n) será el caso promedio para ambos.
¿Puedo esperar un mejor rendimiento para algunas cosas que mis suposiciones aquí? No espero que nada esté delineado en ninguna especificación, pero en la práctica podría ser que todas las implementaciones principales usen arrays optimizados detrás de escena. ¿Hay matrices de expansión dinámica o alguna otra mejora del rendimiento ¿algoritmos en funcionamiento?
P.d.
La razón por la que me pregunto esto es porque estoy investigando algunos algoritmos de ordenación, la mayoría de los cuales parecen asumir que anexar y eliminar son operaciones O(1) al describir su gran O general.
2 answers
En contraste con la mayoría de los lenguajes, que implementan arrays con, bueno, arrays, en Javascript Los Arrays son objetos, y los valores se almacenan en una tabla hash, al igual que los valores de objetos regulares. Como tal:
- Access-O (1)
- Appending-Amortized O(1) (a veces se requiere cambiar el tamaño de la tabla hash; generalmente solo se requiere inserción)
- Anteponiendo-O (n) vía
unshift, ya que requiere reasignar todos los índices - Inserción - Amortizado O(1) si el valor no existe. O (n)si desea cambiar los valores existentes (por ejemplo, usando
splice). - Deletion - Amortizado O(1) para eliminar un valor, O(n) si desea reasignar índices a través de
splice. - Intercambio - O (1)
En general, establecer o desactivar cualquier clave en un diccionario se amortiza O(1), y lo mismo ocurre con los arrays, independientemente de cuál sea el índice. Cualquier operación que requiera renumerar valores existentes es O (n) simplemente porque tiene que actualizar todos los valores afectados.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-18 12:57:04
Todas las complejidades que mencionaste parecen estar bien. Pero si el objeto array mantiene la longitud, entonces la adición también se puede hacer en tiempo O (1).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-06-08 13:15:03