Una matriz ordenada es una estructura de datos de matriz en la que cada elemento se ordena en orden numérico, alfabético o en algún otro orden, y se coloca en direcciones igualmente espaciadas en la memoria de la computadora. Por lo general, se usa en ciencias de la computación para implementar tablas de búsqueda estáticas para contener múltiples valores que tienen el mismo tipo de datos . Ordenar una matriz es útil para organizar los datos en forma ordenada y recuperarlos rápidamente.
Matriz ordenada | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | Formación | ||||||||||||||||||||
Inventado | 1945 | ||||||||||||||||||||
Inventado por | John von Neumann | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Métodos
Hay muchos métodos bien conocidos mediante los cuales se puede ordenar una matriz, que incluyen, entre otros: ordenación por selección , ordenación por burbujas , ordenación por inserción , ordenación por combinación , ordenación rápida , ordenación por heap y ordenación por recuento . [ cita requerida ] Estas técnicas de clasificación tienen diferentes algoritmos asociados, y por lo tanto existen diferentes ventajas al usar cada método.
Descripción general
Los arreglos ordenados son la estructura de datos más eficiente en el espacio con la mejor localidad de referencia para los datos almacenados secuencialmente. [ cita requerida ]
Los elementos dentro de una matriz ordenada se encuentran mediante una búsqueda binaria , en O (log n ); por lo tanto, las matrices ordenadas son adecuadas para casos en los que se necesita poder buscar elementos rápidamente, por ejemplo, como una estructura de datos de conjuntos o de conjuntos múltiples . Esta complejidad para las búsquedas es la misma que para los árboles de búsqueda binaria autoequilibrados .
En algunas estructuras de datos, se utiliza una matriz de estructuras. En tales casos, se pueden utilizar los mismos métodos de clasificación para clasificar las estructuras de acuerdo con alguna clave como elemento de estructura; por ejemplo, ordenar los registros de los estudiantes según los números de lista, los nombres o las calificaciones.
Si uno está usando una matriz dinámica ordenada , entonces es posible insertar y eliminar elementos. La inserción y eliminación de elementos en una matriz ordenada se ejecuta en O ( n ), debido a la necesidad de desplazar todos los elementos que siguen al elemento a insertar o eliminar; en comparación, un árbol de búsqueda binario autoequilibrado inserta y elimina en O (log n ). En el caso de que los elementos se eliminen o inserten al final, una matriz dinámica ordenada puede hacer esto en un tiempo amortizado O (1) mientras que un árbol de búsqueda binaria autoequilibrado siempre opera en O (log n ).
Los elementos en una matriz ordenada se pueden buscar por su índice ( acceso aleatorio ) en el momento O (1), una operación que toma O (log n ) u O ( n ) tiempo para estructuras de datos más complejas.
Historia
John von Neumann escribió el primer programa de clasificación de matrices (clasificación por fusión ) en 1945, cuando aún se estaba construyendo la primera computadora con programa almacenado . [1]
Aplicaciones de matrices ordenadas
Informática comercial [2]
Las organizaciones gubernamentales, las empresas privadas y muchas aplicaciones basadas en la web tienen que manejar grandes cantidades de datos. A menudo, será necesario acceder a los datos varias veces. Mantener los datos en un formato ordenado permite una recuperación rápida y sencilla.
En matemáticas discretas
Las matrices ordenadas se pueden utilizar para implementar el algoritmo de Dijkstra o el algoritmo de Prim . Además, algoritmos como el de Kruskal para encontrar árboles de expansión mínimos.
En programación prioritaria
A nivel del sistema operativo , muchos procesos están pendientes a la vez, pero solo pueden manejar un proceso en una sola instancia en el tiempo. Por tanto, las prioridades están asociadas a cada proceso. Luego, los procesos se envían a la CPU de acuerdo con la prioridad más alta mediante el uso de una matriz ordenada de ID de proceso. Aquí, los procesos se ordenaron según sus prioridades y luego se les asignó la CPU. El proceso que tiene la prioridad más alta ocupa la primera posición en la matriz ordenada. Por lo tanto, se realiza la programación de los procesos del sistema según la prioridad. [3]
En la programación más corta del trabajo primero
Este es el caso especial de la programación prioritaria. Aquí, los procesos se ordenan según el tiempo de ráfaga de los procesos. Primero se asignará CPU al proceso que requiera el menor tiempo. Por lo tanto, los procesos se envían a la CPU de acuerdo con su tiempo de ráfaga.
Proceso | Tiempo quemado |
---|---|
P1 | 3 |
P2 | 4 |
P3 | 1 |
P4 | 8 |
P5 | 6 |
Ver también
Referencias
- ^ Donald Knuth , El arte de la programación informática , vol. 3. Addison-Wesley
- ^ http://algs4.cs.princeton.edu/25applications/
- ^ Conceptos del sistema operativo por Peter B. Galvin . WILEY-INDIA Pvt. limitado. ISBN 978-81-265-2051-0.