La complejidad de un algoritmo mide el tiempo y/o el espacio que necesita un algoritmo para una entrada de tamaño dado (n). Aunque la complejidad depende de factores concretos como: la arquitectura del ordenador (es decir, la plataforma de hardware), la representación del tipo abstracto de datos (ADT), la eficiencia del compilador, la complejidad del algoritmo subyacente y el tamaño de la entrada. Aun así, los factores más determinantes suelen ser la complejidad del algoritmo en sí y el tamaño de la entrada.
En el tutorial de estructuras de datos en Python del blog de DataCamp puedes conocer una visión general de las estructuras de datos y cómo implementarlas en Python. Este artículo introduce las estructuras de datos básicas de Python. Verás qué es un tipo abstracto de datos y una estructura de datos, las estructuras de datos primitivas y las no primitivas.
Análisis asintótico
El análisis asintótico consiste en calcular el tiempo de ejecución de un fragmento de código u operación en una unidad matemática de cómputo. Se expresa en términos de una función como f(n). En análisis matemático, el análisis asintótico (o asintótica) es un método para describir el comportamiento en el límite.
El tiempo requerido por un algoritmo se clasifica en tres tipos: peor caso: tiempo máximo que necesita un algoritmo y es el que más se usa al analizarlo; mejor caso: tiempo mínimo, que normalmente no se calcula; caso promedio: tiempo medio, que a veces se considera en el análisis.
Notación asintótica
Las notaciones más utilizadas para calcular la complejidad temporal de un algoritmo son:
- Notación Big O
- Notación Big θ
- Notación Big Ω
Notación Big Oh, Ο
Big O se usa para medir el rendimiento o la complejidad de un algoritmo. En términos matemáticos, es la cota superior de la tasa de crecimiento de una función: si una función g(x) no crece más rápido que una función f(x), entonces g pertenece a O(f). En general, se utiliza para expresar la cota superior de un algoritmo y sirve para estimar su complejidad temporal en el peor caso, es decir, el mayor tiempo que podría tardar en completarse.
Notación Big Omega, Ω
La notación Ω(n) es la forma formal de expresar la cota inferior del tiempo de ejecución de un algoritmo. Mide el mejor caso, el menor tiempo que podría tardar en completarse.
Notación Big Theta, θ
La notación θ(n) expresa formalmente tanto la cota inferior como la cota superior del tiempo de ejecución de un algoritmo.
La notación se usa para determinar la complejidad de distintos algoritmos
La notación Big O es la más usada y sirve para hallar la cota superior de un algoritmo. La notación Big θ se utiliza a veces para describir el caso promedio y la notación Ω es la menos frecuente de las tres.
A continuación verás ejemplos de cómo se usan estas notaciones para determinar la complejidad de algoritmos concretos.
Por ejemplo, para quicksort:
Quicksort es un algoritmo de divide y vencerás para ordenar. Es un método sistemático para colocar elementos en orden, por ejemplo, ordenar números de un array en orden ascendente o descendente. Este algoritmo elige un pivote (un índice) del array dado. El pivote puede seleccionarse de distintas formas; en el ejemplo de abajo se elige el último elemento como pivote.
La clave de quicksort es la partición. A partir de un array se elige un elemento de partición y se coloca en su posición correcta; los elementos mayores que la partición van a su derecha y los más pequeños a su izquierda.
def partition(array,low,high):
i = ( low-1 )
pivot = array[high]
for j in range
La complejidad de un algoritmo mide el tiempo y/o el espacio que necesita un algoritmo para una entrada de tamaño dado (n). Aunque la complejidad depende de factores concretos como: la arquitectura del ordenador (es decir, la plataforma de hardware), la representación del tipo abstracto de datos (ADT), la eficiencia del compilador, la complejidad del algoritmo subyacente y el tamaño de la entrada. Aun así, los factores más determinantes suelen ser la complejidad del algoritmo en sí y el tamaño de la entrada.
En el tutorial de estructuras de datos en Python del blog de DataCamp puedes conocer una visión general de las estructuras de datos y cómo implementarlas en Python. Este artículo introduce las estructuras de datos básicas de Python. Verás qué es un tipo abstracto de datos y una estructura de datos, las estructuras de datos primitivas y las no primitivas.
Análisis asintótico
El análisis asintótico consiste en calcular el tiempo de ejecución de un fragmento de código u operación en una unidad matemática de cómputo. Se expresa en términos de una función como f(n). En análisis matemático, el análisis asintótico (o asintótica) es un método para describir el comportamiento en el límite.
El tiempo requerido por un algoritmo se clasifica en tres tipos: peor caso: tiempo máximo que necesita un algoritmo y es el que más se usa al analizarlo; mejor caso: tiempo mínimo, que normalmente no se calcula; caso promedio: tiempo medio, que a veces se considera en el análisis.
Notación asintótica
Las notaciones más utilizadas para calcular la complejidad temporal de un algoritmo son:
Notación Big Oh, Ο
Big O se usa para medir el rendimiento o la complejidad de un algoritmo. En términos matemáticos, es la cota superior de la tasa de crecimiento de una función: si una función g(x) no crece más rápido que una función f(x), entonces g pertenece a O(f). En general, se utiliza para expresar la cota superior de un algoritmo y sirve para estimar su complejidad temporal en el peor caso, es decir, el mayor tiempo que podría tardar en completarse.
Notación Big Omega, Ω
La notación Ω(n) es la forma formal de expresar la cota inferior del tiempo de ejecución de un algoritmo. Mide el mejor caso, el menor tiempo que podría tardar en completarse.
Notación Big Theta, θ
La notación θ(n) expresa formalmente tanto la cota inferior como la cota superior del tiempo de ejecución de un algoritmo.
La notación se usa para determinar la complejidad de distintos algoritmos
La notación Big O es la más usada y sirve para hallar la cota superior de un algoritmo. La notación Big θ se utiliza a veces para describir el caso promedio y la notación Ω es la menos frecuente de las tres.
A continuación verás ejemplos de cómo se usan estas notaciones para determinar la complejidad de algoritmos concretos.
Por ejemplo, para quicksort:
Quicksort es un algoritmo de divide y vencerás para ordenar. Es un método sistemático para colocar elementos en orden, por ejemplo, ordenar números de un array en orden ascendente o descendente. Este algoritmo elige un pivote (un índice) del array dado. El pivote puede seleccionarse de distintas formas; en el ejemplo de abajo se elige el último elemento como pivote.
La clave de quicksort es la partición. A partir de un array se elige un elemento de partición y se coloca en su posición correcta; los elementos mayores que la partición van a su derecha y los más pequeños a su izquierda.