Complejidad de los algoritmos

03. 08. 2021

Obsah článku

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 Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: