Big O notation
¿Qué es la notación Big O?
Big O describe cómo crece el tiempo o espacio requerido por un algoritmo a medida que aumenta el tamaño de la entrada. Es clave para comparar y elegir algoritmos eficientes.
Gráfico de Complejidad Big O: Este gráfico muestra cómo diferentes órdenes de complejidad (O(1), O(n), O(n²), etc.) afectan el rendimiento a medida que crece la cantidad de datos. Las curvas más bajas (O(1), O(log n)) son más eficientes para grandes volúmenes de datos.
Gráfico de Complejidad Big O
Horrible |
Bad |
Fair |
Good |
Excellent |
Operaciones comunes en estructuras de datos: La siguiente tabla compara el tiempo y espacio que requieren operaciones típicas (acceso, búsqueda, inserción, eliminación) en distintas estructuras de datos.
Ejemplo: Buscar un elemento en un array desordenado es O(n), pero en una tabla hash es O(1) en promedio.
Ejemplo: Buscar un elemento en un array desordenado es O(n), pero en una tabla hash es O(1) en promedio.
Operaciones Comunes en Estructuras de Datos
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | Θ(1) |
Θ(n) |
Θ(n) |
Θ(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Singly-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Skip List | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
| Hash Table | N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| Cartesian Tree | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| B-Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Red-Black Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Splay Tree | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| AVL Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| KD Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
Comparativa de algoritmos de ordenamiento: Aquí puedes ver cómo distintos algoritmos ordenan datos y cuán eficientes son en el mejor, promedio y peor caso.
Ejemplo: QuickSort es muy eficiente en promedio (O(n log n)), pero puede ser lento en el peor caso (O(n²)).
Ejemplo: QuickSort es muy eficiente en promedio (O(n log n)), pero puede ser lento en el peor caso (O(n²)).
Algoritmos de Ordenamiento de Arreglos
Los algoritmos de ordenamiento son métodos utilizados para reorganizar los elementos de un arreglo o lista en un orden específico, generalmente ascendente o descendente. El ordenamiento es una operación fundamental en informática, ya que facilita la búsqueda, la visualización y el procesamiento eficiente de los datos.
Existen muchos algoritmos de ordenamiento, cada uno con ventajas y desventajas según el tipo y tamaño de los datos. Algunos, como Bubble Sort o Insertion Sort, son fáciles de entender pero poco eficientes para grandes volúmenes de datos. Otros, como QuickSort o MergeSort, son mucho más rápidos y se utilizan en aplicaciones reales.
En la tabla a continuación puedes comparar la eficiencia de los algoritmos más conocidos en diferentes escenarios (mejor, promedio y peor caso), así como el espacio de memoria que requieren. Elegir el algoritmo adecuado puede marcar una gran diferencia en el rendimiento de tus programas.
Existen muchos algoritmos de ordenamiento, cada uno con ventajas y desventajas según el tipo y tamaño de los datos. Algunos, como Bubble Sort o Insertion Sort, son fáciles de entender pero poco eficientes para grandes volúmenes de datos. Otros, como QuickSort o MergeSort, son mucho más rápidos y se utilizan en aplicaciones reales.
En la tabla a continuación puedes comparar la eficiencia de los algoritmos más conocidos en diferentes escenarios (mejor, promedio y peor caso), así como el espacio de memoria que requieren. Elegir el algoritmo adecuado puede marcar una gran diferencia en el rendimiento de tus programas.
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Quicksort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(log(n)) |
| Mergesort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Timsort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Heapsort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(1) |
| Bubble Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Selection Sort | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| Tree Sort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(n) |
| Shell Sort | Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| Bucket Sort | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Counting Sort | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
Glosario de términos:
- Complejidad temporal: Medida de cuánto tiempo tarda un algoritmo en ejecutarse según el tamaño de la entrada.
- Complejidad espacial: Medida de cuánta memoria adicional necesita un algoritmo.
- Mejor caso: El escenario más favorable para el algoritmo.
- Peor caso: El escenario más desfavorable para el algoritmo.
- Promedio: El comportamiento esperado en la mayoría de los casos.
Recursos recomendados:
- Artículo de Wikipedia sobre Notación Big O
- Visualgo.net (visualizaciones de algoritmos)
- Big O Cheat Sheet (en inglés)
Consejos prácticos:
- No siempre el algoritmo con mejor Big O es el más rápido para entradas pequeñas.
- Considera la legibilidad y facilidad de implementación, no solo la eficiencia.
- La elección de la estructura de datos adecuada puede simplificar mucho tu código y mejorar el rendimiento.
Ejemplo práctico:
Supón que tienes una lista de 1,000 elementos y quieres buscar un valor:
- O(1): Acceso directo, como buscar por índice en un array. Solo 1 operación.
- O(n): Búsqueda lineal. Hasta 1,000 operaciones en el peor caso.
- O(log n): Búsqueda binaria en una lista ordenada. Solo unas 10 operaciones.
- O(n²): Algoritmo de ordenamiento ineficiente. ¡Hasta 1,000,000 de operaciones!
Esto muestra por qué elegir el algoritmo correcto es tan importante cuando los datos crecen.
Preguntas frecuentes:
- ¿Big O mide el tiempo real de ejecución? No, mide cómo crece el tiempo o espacio en función del tamaño de la entrada.
- ¿Siempre debo elegir el algoritmo con mejor Big O? No necesariamente. Para datos pequeños, la diferencia puede ser irrelevante.
- ¿Importa el hardware o el lenguaje? Big O es independiente del hardware y del lenguaje, pero en la práctica estos factores también influyen.
Nota sobre notaciones O, Θ (Theta) y Ω (Omega):
- O (Big O): Cota superior. El algoritmo nunca será más lento que esto. Ejemplo: O(n) significa que el tiempo de ejecución crece, como máximo, proporcionalmente a n.
- Ω (Omega): Cota inferior. El algoritmo nunca será más rápido que esto. Ejemplo: Ω(n) significa que, como mínimo, el tiempo de ejecución crece proporcionalmente a n.
- Θ (Theta): Cota ajustada. El algoritmo siempre se comporta así, tanto en el mejor como en el peor caso. Ejemplo: Θ(n) significa que el tiempo de ejecución crece exactamente proporcional a n.
Ejemplo:
- Para un algoritmo de búsqueda lineal en un arreglo de n elementos:
- O(n): En el peor caso, revisa todos los elementos.
- Ω(1): En el mejor caso, encuentra el elemento en la primera posición.
- Θ(n): En promedio, el tiempo de ejecución es proporcional a n.
En la práctica, la notación más utilizada es Big O, pero en análisis más detallados pueden aparecer las otras.
- Artículo de Wikipedia sobre Notación Big O
- Visualgo.net (visualizaciones de algoritmos)
- Big O Cheat Sheet (en inglés)
Consejos prácticos:
- No siempre el algoritmo con mejor Big O es el más rápido para entradas pequeñas.
- Considera la legibilidad y facilidad de implementación, no solo la eficiencia.
- La elección de la estructura de datos adecuada puede simplificar mucho tu código y mejorar el rendimiento.
Ejemplo práctico:
Supón que tienes una lista de 1,000 elementos y quieres buscar un valor:
- O(1): Acceso directo, como buscar por índice en un array. Solo 1 operación.
- O(n): Búsqueda lineal. Hasta 1,000 operaciones en el peor caso.
- O(log n): Búsqueda binaria en una lista ordenada. Solo unas 10 operaciones.
- O(n²): Algoritmo de ordenamiento ineficiente. ¡Hasta 1,000,000 de operaciones!
Esto muestra por qué elegir el algoritmo correcto es tan importante cuando los datos crecen.
Preguntas frecuentes:
- ¿Big O mide el tiempo real de ejecución? No, mide cómo crece el tiempo o espacio en función del tamaño de la entrada.
- ¿Siempre debo elegir el algoritmo con mejor Big O? No necesariamente. Para datos pequeños, la diferencia puede ser irrelevante.
- ¿Importa el hardware o el lenguaje? Big O es independiente del hardware y del lenguaje, pero en la práctica estos factores también influyen.
Nota sobre notaciones O, Θ (Theta) y Ω (Omega):
- O (Big O): Cota superior. El algoritmo nunca será más lento que esto. Ejemplo: O(n) significa que el tiempo de ejecución crece, como máximo, proporcionalmente a n.
- Ω (Omega): Cota inferior. El algoritmo nunca será más rápido que esto. Ejemplo: Ω(n) significa que, como mínimo, el tiempo de ejecución crece proporcionalmente a n.
- Θ (Theta): Cota ajustada. El algoritmo siempre se comporta así, tanto en el mejor como en el peor caso. Ejemplo: Θ(n) significa que el tiempo de ejecución crece exactamente proporcional a n.
Ejemplo:
- Para un algoritmo de búsqueda lineal en un arreglo de n elementos:
- O(n): En el peor caso, revisa todos los elementos.
- Ω(1): En el mejor caso, encuentra el elemento en la primera posición.
- Θ(n): En promedio, el tiempo de ejecución es proporcional a n.
En la práctica, la notación más utilizada es Big O, pero en análisis más detallados pueden aparecer las otras.
Ejemplo práctico:
Supón que tienes una lista de 1,000 elementos y quieres buscar un valor:- O(1): Acceso directo, como buscar por índice en un array. Solo 1 operación.
- O(n): Búsqueda lineal. Hasta 1,000 operaciones en el peor caso.
- O(log n): Búsqueda binaria en una lista ordenada. Solo unas 10 operaciones.
- O(n²): Algoritmo de ordenamiento ineficiente. ¡Hasta 1,000,000 de operaciones!
Preguntas frecuentes:
- ¿Big O mide el tiempo real de ejecución? No, mide cómo crece el tiempo o espacio en función del tamaño de la entrada.
- ¿Siempre debo elegir el algoritmo con mejor Big O? No necesariamente. Para datos pequeños, la diferencia puede ser irrelevante.
- ¿Importa el hardware o el lenguaje? Big O es independiente del hardware y del lenguaje, pero en la práctica estos factores también influyen.
Nota sobre notaciones O, Θ (Theta) y Ω (Omega):
- O (Big O): Cota superior. El algoritmo nunca será más lento que esto. Ejemplo: O(n) significa que el tiempo de ejecución crece, como máximo, proporcionalmente a n.
- Ω (Omega): Cota inferior. El algoritmo nunca será más rápido que esto. Ejemplo: Ω(n) significa que, como mínimo, el tiempo de ejecución crece proporcionalmente a n.
- Θ (Theta): Cota ajustada. El algoritmo siempre se comporta así, tanto en el mejor como en el peor caso. Ejemplo: Θ(n) significa que el tiempo de ejecución crece exactamente proporcional a n.
- Para un algoritmo de búsqueda lineal en un arreglo de n elementos:
- O(n): En el peor caso, revisa todos los elementos.
- Ω(1): En el mejor caso, encuentra el elemento en la primera posición.
- Θ(n): En promedio, el tiempo de ejecución es proporcional a n.
