Complejidad de los algoritmos

📅   03. 08. 2021
👤   Jan Barášek
Cada algoritmo tiene su propia complejidad, que puede expresarse en notación matemática. Este resumen muestra la complejidad típica de los algoritmos según el tamaño de los datos de entrada (es decir, el número de elementos con los que trabajan) y qué tipos de algoritmos son adecuados para cada tipo de tarea.

En general, existe un mejor algoritmo especializado para cada tipo de problema. Ningún algoritmo es universalmente mejor, y siempre hay que conocer el contexto.

Notación Big O

La notación Big O se utiliza para clasificar los algoritmos en función de cómo aumentan sus requisitos de tiempo de ejecución o de memoria al aumentar el tamaño de la entrada.

El siguiente gráfico muestra los órdenes de crecimiento más comunes de los algoritmos especificados en notación Big O.

A continuación se presenta una lista de algunas de las notaciones Big O más utilizadas y una comparación de su rendimiento con respecto a diferentes tamaños de datos de entrada.

Notación Big O Complejidad para 10 elementos Complejidad para 100 elementos Complejidad para 1000 elementos
O(1)
O(log N)
O(N)
O(N log N)
O(N^2)
O(2^N)**
O(N!)**

Complejidad de las operaciones con estructuras de datos

Estructura de datos, Acceso, Búsqueda, Inserción, Eliminación, Comentario, etc.
Array
Stack
Cola
Lista enlazada
Tabla hash
Árbol de búsqueda binario
B-Tree
Árbol Rojo-Negro
Árbol AVL
Filtro Bloom

Complejidad de los algoritmos de clasificación

Nombre del Algoritmo Mejor, Promedio, Peor, Memoria, Estable, Comentario.
Ordenación por burbujas
Ordenación por inserción
Ordenación por selección
Heap sort
Merge sort
Ordenación rápida
Shell sort
Ordenación de conteo
Ordenación de la matriz

Jan Barášek     Más sobre el autor

El autor trabaja como desarrollador senior y arquitecto de software en Praga. Diseña y gestiona grandes aplicaciones web que usted conoce y utiliza. Desde 2009 ha adquirido una gran experiencia que transmite a través de este sitio web.

Estaré encantado de ayudarte:

Contacte con