algorithm => Complejidad de algoritmos

Observaciones

Todos los algoritmos son una lista de pasos para resolver un problema. Cada paso tiene dependencias en algún conjunto de pasos anteriores, o el inicio del algoritmo. Un pequeño problema podría parecerse al siguiente:

Esta estructura se llama un gráfico acíclico dirigido, o DAG para abreviar. Los enlaces entre cada nodo en el gráfico representan dependencias en el orden de las operaciones, y no hay ciclos en el gráfico.

¿Cómo ocurren las dependencias? Tomemos por ejemplo el siguiente código:

total = 0
for(i = 1; i < 10; i++)
    total = total + i

En este psuedocode, cada iteración del bucle for depende del resultado de la iteración anterior porque estamos usando el valor calculado en la iteración anterior en la siguiente iteración. El DAG para este código podría tener este aspecto:

Si comprende esta representación de algoritmos, puede usarla para comprender la complejidad de los algoritmos en términos de trabajo y espacio.

Trabajo

Trabajo es el número real de operaciones que deben ejecutarse para lograr el objetivo del algoritmo para un tamaño de entrada dado n .

Lapso

En ocasiones, se hace referencia al intervalo como la ruta crítica, y es el menor número de pasos que debe realizar un algoritmo para alcanzar el objetivo del algoritmo.

La siguiente imagen resalta el gráfico para mostrar las diferencias entre el trabajo y el intervalo en nuestro DAG de muestra.

El trabajo es el número de nodos en el gráfico en su conjunto. Esto está representado por el gráfico de la izquierda arriba. El tramo es la ruta crítica, o la ruta más larga desde el principio hasta el final. Cuando se puede trabajar en paralelo, los nodos resaltados en amarillo a la derecha representan el intervalo, el menor número de pasos necesarios. Cuando el trabajo debe realizarse en serie, el intervalo es el mismo que el trabajo.

Tanto el trabajo como el lapso pueden evaluarse independientemente en términos de análisis. La velocidad de un algoritmo está determinada por el intervalo. La cantidad de potencia computacional requerida está determinada por el trabajo.

Notación Big-Theta

A diferencia de la notación Big-O, que representa solo el límite superior del tiempo de ejecución de algunos algoritmos, Big-Theta es un límite ajustado; Ambos límites superior e inferior. La unión estrecha es más precisa, pero también más difícil de calcular.

La notación Big-Theta es simétrica: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

Una forma intuitiva de comprenderlo es que f(x) = Ө(g(x)) significa que los gráficos de f (x) yg (x) crecen en la misma tasa, o que los gráficos se "comportan" de manera similar para grandes suficientes valores de x.

La expresión matemática completa de la notación Big-Theta es la siguiente:
Ө (f (x)) = {g: N ₀ -> R y c ₁ , c ₂ , n ₀ > 0, donde c ₁ <abs (g (n) / f (n)), para cada n> n ₀ y abs es el valor absoluto}

Un ejemplo

Si el algoritmo para la entrada n necesita 42n^2 + 25n + 4 operaciones para finalizar, decimos que es O(n^2) , pero también es O(n^3) y O(n^100) . Sin embargo, es Ө(n^2) y no es Ө(n^3) , Ө(n^4) etc. El algoritmo que es Ө(f(n)) también es O(f(n)) , pero ¡no viceversa!

Definicion matematica formal

Ө(g(x)) es un conjunto de funciones.

Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}

Como Ө(g(x)) es un conjunto, podríamos escribir f(x) ∈ Ө(g(x)) para indicar que f(x) es un miembro de Ө(g(x)) . En su lugar, normalmente escribiremos f(x) = Ө(g(x)) para expresar la misma noción, esa es la forma común.

Cuando aparece Ө(g(x)) en una fórmula, interpretamos que representa una función anónima que no nos interesa nombrar. Por ejemplo, la ecuación T(n) = T(n/2) + Ө(n) , significa T(n) = T(n/2) + f(n) donde f(n) es una función en el conjunto Ө(n) .

Sean f y g dos funciones definidas en algún subconjunto de números reales. Escribimos f(x) = Ө(g(x)) como x->infinity si y solo si hay constantes positivas K y L y un número real x0 tal que se mantenga:

K|g(x)| <= f(x) <= L|g(x)| para todos x >= x0 .

La definición es igual a:

f(x) = O(g(x)) and f(x) = Ω(g(x))

Un método que utiliza límites.

si el limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) es decir, el límite existe y es positivo, entonces f(x) = Ө(g(x))

Clases de complejidad común

Nombre	Notación	n = 10	n = 100
Constante	Ө (1)	1	1
Logarítmica	Ө (log (n))	3	7
Lineal	Ө (n)	10	100
Linealista	Ө (n * log (n))	30	700
Cuadrático	Ө (n ^ 2)	100	10 000
Exponencial	Ө (2 ^ n)	1 024	1.267650e + 30
Factorial	Ө (n!)	3 628 800	9.332622e + 157

Notación Big-Omega

La notación se utiliza para el límite inferior asintótico.

Definicion formal

Sean f(n) g(n) dos funciones definidas en el conjunto de los números reales positivos. Escribimos f(n) = Ω(g(n)) si hay constantes positivas c y n0 tales que:

0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .

Notas

f(n) = Ω(g(n)) significa que f(n) crece asintóticamente no más lento que g(n) . También podemos decir acerca de Ω(g(n)) cuando el análisis de algoritmos no es suficiente para la declaración sobre Θ(g(n)) y / y O(g(n)) .

De las definiciones de notaciones sigue el teorema:

Para dos funciones de f(n) g(n) tenemos f(n) = Ө(g(n)) si y solo si f(n) = O(g(n)) and f(n) = Ω(g(n)) .

Gráficamente la notación Ω se puede representar de la siguiente manera:

Por ejemplo, vamos a tener f(n) = 3n^2 + 5n - 4 . Entonces f(n) = Ω(n^2) . También es correcto f(n) = Ω(n) , o incluso f(n) = Ω(1) .

Otro ejemplo para resolver el algoritmo de coincidencia perfecta: si el número de vértices es impar, emita "Sin coincidencia perfecta"; de lo contrario, intente todas las coincidencias posibles.

Nos gustaría decir que el algoritmo requiere tiempo exponencial, pero en realidad no puede probar un límite inferior de Ω(n^2) usando la definición habitual de Ω ya que el algoritmo se ejecuta en tiempo lineal para n impar. En su lugar, deberíamos definir f(n)=Ω(g(n)) diciendo que para alguna constante c>0 , f(n)≥ cg(n) para infinitamente muchos n . Esto proporciona una buena correspondencia entre los límites superior e inferior: f(n)=Ω(g(n)) iff f(n) != o(g(n)) .

Referencias

La definición formal y el teorema están tomados del libro "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introducción a los algoritmos".

Comparación de las notaciones asintóticas.

Sean f(n) g(n) dos funciones definidas en el conjunto de los números reales positivos, c, c1, c2, n0 son constantes reales positivas.

Notación	f (n) = O (g (n))	f (n) = Ω (g (n))	f (n) = Θ (g (n))	f (n) = o (g (n))	f (n) = ω (g (n))
Definicion formal	`∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n)`	`∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n)`	`∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)`	`∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n)`	`∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n)`
Analogía entre la comparación asintótica de `f, g` y números reales `a, b`	`a ≤ b`	`a ≥ b`	`a = b`	`a < b`	`a > b`
Ejemplo	`7n + 10 = O(n^2 + n - 9)`	`n^3 - 34 = Ω(10n^2 - 7n + 1)`	`1/2 n^2 - 7n = Θ(n^2)`	`5n^2 = o(n^3)`	`7n^2 = ω(n)`
Interpretación grafica