La eficiencia de una colección se refiere a su capacidad para realizar operaciones de manera rápida y eficiente, minimizando el tiempo y los recursos utilizados.
Al evaluar la eficiencia de una colección, es importante considerar el tiempo de ejecución de las operaciones clave (como la lectura, inserción, eliminación y búsqueda de elementos)
Estas operaciones varían según el tipo de colección y su implementación interna.
Tabla de comparación de eficiencia
Vamos a ver una tabla de resumen de las eficiencias de las colecciones que hemos visto en el curso, ante distintas operaciones:
| Operación | Array | List | LinkedList | Pila | Cola | Set | Dict |
|---|---|---|---|---|---|---|---|
| Acceso secuencial | 🟢 | 🟢 | 🟢 | ⚫ | ⚫ | ⚫ | ⚫ |
| Acceso aleatorio | 🟢 | 🟢 | 🔴 | ⚫ | ⚫ | 🟢 | 🟢 |
| Añadir al principio | ⚫ | 🔴 | 🟢 | ⚫ | 🟢 | ⚫ | ⚫ |
| Eliminar al principio | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | ⚫ | ⚫ |
| Añadir al final | 🟢 | 🟡 | 🟢 | 🟢 | ⚫ | ⚫ | ⚫ |
| Eliminar al final | 🟢 | 🟢 | 🟢 | 🟢 | 🟢 | ⚫ | ⚫ |
| Inserción aleatoria | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | 🟡 | 🟡 |
| Eliminar aleatoria | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | 🟢 | 🟢 |
| Búsqueda | 🔴 | 🔴 | 🔴 | ⚫ | ⚫ | 🟢 | 🟢 |
Donde el significado de cada símbolo es,
- 🟢O(1): Tiempo de ejecución constante.
- 🟡O(1)-O(n): Tiempo de ejecución constante en el mejor caso, pero lineal en el peor caso.
- 🔴O(n): Tiempo de ejecución lineal, proporcional al tamaño de la colección.
- ⚫N/A: La operación no es aplicable o no tiene sentido para esa colección en particular.
Descripción de las operaciones
Aquí tenéis una descripción de cada una de las operaciones mencionadas en la tabla:
Acceso secuencial: Se refiere a la capacidad de acceder a los elementos de la colección en secuencia, uno tras otro, sin importar su posición.
Acceso aleatorio: Significa la habilidad de acceder directamente a un elemento en una posición específica de la colección, sin necesidad de recorrer secuencialmente desde el principio.
Añadir al principio: La operación de agregar un nuevo elemento al principio de la colección.
Eliminar al principio: Es la operación de eliminar el primer elemento de la colección.
Añadir al final: Agregar un nuevo elemento al final de la colección.
Eliminar al final: Se refiere a la operación de eliminar el último elemento de la colección.
Inserción aleatoria: Significa agregar un nuevo elemento en una posición arbitraria de la colección.
Eliminar aleatoria: Es la operación de eliminar un elemento en una posición arbitraria de la colección.
Búsqueda: Significa encontrar un elemento específico en la colección.