Introducción a los Algoritmos – Parte III – Análisis de Algoritmos

Link a la Primera Parte            —            Link a la Segunda Parte

 

Como hemos visto, existen muchos enfoques para resolver un problema. ¿Cómo escogemos entre ellos? Generalmente hay dos metas en el diseño de programas de cómputo:

  • El diseño de un algoritmo que sea fácil de entender, codificar y depurar (Ingeniería de Software).
  • El diseño de un algoritmo que haga uso eficiente de los recursos de la computadora (Análisis y Diseño de algoritmos).

El análisis de algoritmos nos permite medir la dificultad inherente de un problema y evaluar la eficiencia de un algoritmo.

 

Tiempos de Ejecución

Una medida que suele ser útil conocer es el tiempo de ejecución de un algoritmo en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.

Así, un trozo sencillo de programa como:

S1; FOR i:= 1 TO N DO S2 END;

requiere:

T(N):= t1 + t2*N

siendo t1 el tiempo que lleve ejecutar la serie “S1″ de sentencias, y t2 el que lleve la serie “S2″.

Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que más que un valor T(N) debamos hablar de un rango de valores:

Tmin(N) <= T(N) <= Tmax(N)

los extremos son habitualmente conocidos como “caso peor” y “caso mejor“. Entre ambos se hallará algún “caso promedio” o más frecuente. Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes “Ti” que dependen de factores externos al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de
instrucciones del computador que lo ejecuta.

Dado que es fácil cambiar de compilador y que la potencia de los computadores crece a un ritmo vertiginoso (en la actualidad, se duplica anualmente), intentaremos analizar los algoritmos con algún nivel de independencia de estos factores; es decir, buscaremos estimaciones generales ampliamente válidas.

No se puede medir el tiempo en segundos porque no existe un computador estándar de referencia, en su lugar medimos el número de operaciones básicas o elementales.

Las operaciones básicas son las que realiza el computador en tiempo acotado por una constante, por ejemplo:

  • Operaciones aritméticas básicas
  • Asignaciones de tipos predefinidos
  • Saltos (llamadas a funciones, procedimientos y retorno)
  • Comparaciones lógicas
  • Acceso a estructuras indexadas básicas (vectores y matrices)

Es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentenc ias, por ejemplo, las que más influyen en el tiempo de ejecución.

Para medir el tiempo de ejecución de un algoritmo existen varios métodos. Veamos algunos de ellos:

a) Benchmarking 

La técnica de benchmark considera una colección de entradas típicas representativas de una carga de trabajo para un programa.

b) Profiling

Consiste en asociar a cada instrucción de un programa un número que representa la fracción del tiempo total tomada para ejecutar esa instrucción particular. Una de las técnicas más conocidas (e informal) es la Regla 90-10, que afirma que el 90% del tiempo de ejecución se invierte en el 10% del código.

c) Análisis

Consiste en agrupar las entradas de acuerdo a su tamaño, y estimar el tiempo de ejecución del programa en entradas de ese tamaño, T(n). Esta es la técnica que se estudiará en el curso.

De este modo, el tiempo de ejecución puede ser definido como una función de la entrada. Denotaremos T(n) como el tiempo de ejecución de un algoritmo para una entrada de tamaño n.

Concepto de Complejidad

La complejidad (o costo) de un algoritmo es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita. La complejidad de un algoritmo se expresa en función del tamaño (o talla) del problema.

La función de complejidad tiene como variable independiente el tamaño del problema y sirve para medir la complejidad (espacial o temporal). Mide el tiempo/espacio relativo en función del tamaño del problema.

El comportamiento de la función determina la eficiencia. No es única para un algoritmo: depende de los datos. Para un mismo tamaño del problema, las distintas presentaciones iniciales de los datos dan lugar a distintas funciones de complejidad. Es el caso de una ordenación si los datos están todos inicialmente desordenados, parcialmente ordenados o en orden inverso.

Ejemplo: f(n)= 3n2+2n+1 , en donde n es el tamaño del problema y expresa el tiempo en unidades de tiempo.

 

¿Una computadora más rápida o un algoritmo más rápido?

Si compramos una computadora diez veces más rápida, ¿en qué tiempo podremos ahora ejecutar un algoritmo? La respuesta depende del tamaño de la entrada de datos, así como de la razón de crecimiento del algoritmo.

Si la razón de crecimiento es lineal (es decir, T(n)=cn) entonces por ejemplo, 100.000 números serán procesados en la nueva máquina en el mismo tiempo que 10.000 números en la antigua computadora.

¿De qué tamaño (valor de n) es el problema que podemos resolver con una computadora X veces más rápida (en un intervalo de tiempo fijo)?

Por ejemplo, supongamos que una computadora resuelve un problema de tamaño n en una hora. Ahora supongamos que tenemos una computadora  10 veces más rápida, ¿de qué tamaño es el problema que podemos resolver?

 

En la tabla de arriba, f(n) es la razón de crecimiento de un algoritmo. Supongamos que tenemos una computadora que puede ejecutar 10.000 operaciones básicas en una hora. La segunda columna muestra el máximo valor de n que puede ejecutarse con 10.000 operaciones básicas en una hora. Es decir f(n)=”total de operaciones básicas en un intervalo de tiempo”.

Por ejemplo, f(n)=10.000 operaciones básicas por hora. Si suponemos que tenemos una computadora 10 veces más rápida, entonces podremos ejecutar 100.000 operaciones básicas en una hora. Por lo cual f(n’)=100.000 operaciones básicas por hora.
Ejercicio: Comentar sobre la razón n´/n según el incremento de velocidad de la computadora y la razón de crecimiento del algoritmo en cuestión.

Nota: los factores constantes nunca afectan la mejora relativa obtenida por una computadora más rápida.

Órdenes de Complejidad

Se dice que O(f(n)) define un “orden de complejidad”. Escogeremos como representante de este orden a la función f(n) más sencilla del mismo.

Así tendremos:

  • O(1) orden constante
  • O(log n) orden logarítmico
  • O(n) orden lineal
  • O(n2 ) orden cuadrático
  • O(na) orden polinomial (a > 2)
  • O(an) orden exponencial (a > 2)
  • O(n!) orden factorial

Es más, se puede identificar una jerarquía de órdenes de complejidad que coincide con el orden de la tabla anterior; jerarquía en el sentido de que cada orden de complejidad superior tiene a los inferiores como  subconjuntos. Si un algoritmo A se puede demostrar de un cierto orden O1 , es cierto que también pertenece a todos los órdenes superiores (la relación de orden cota superior es transitiva); pero en la práctica lo útil es encontrar la “menor cota superior”, es decir el menor orden de complejidad que lo cubra.

Antes de realizar un programa conviene elegir un buen algoritmo, donde por bueno entendemos que utilice pocos recursos, siendo usualmente los más importantes el tiempo que lleve ejecutarse y la cantidad de espacio en memoria que requiera. Es engañoso pensar que todos los algoritmos son “más o menos iguales” y confiar en nuestra habilidad como programadores para convertir un mal algoritmo en un producto eficaz. Es asimismo engañoso confiar en la creciente potencia de las máquinas y el abaratamiento de las mismas como remedio de todos los problemas que puedan aparecer.

Un ejemplo de algunas de las funciones más comunes en análisis de algoritmos son:

 

La mejor técnica para diferenciar la eficiencia de los algoritmos es el estudio de los órdenes de complejidad. El orden de complejidad se expresa generalmente en términos de la cantidad de datos procesados por el programa, denominada n, que puede ser el tamaño dado o estimado.

En el análisis de algoritmos se considera usualmente el caso peor, si bien a veces conviene analizar igualmente el caso mejor y hacer alguna estimación sobre un caso promedio. Para independizarse de factores coyunturales, tales como el lenguaje de programación, la habilidad del codificador, la máquina de soporte, etc. se suele trabajar con un cálculo asintótico que indica cómo se comporta el algoritmo para datos muy grandes y salvo algún coeficiente multiplicativo. Para problemas pequeños es cierto que casi todos los algoritmos son “más o menos iguales”, primando otros aspectos como esfuerzo de codificación, legibilidad, etc. Los órdenes de complejidad sólo son importantes para grandes problemas.

Notación Asintótica

El interés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece. Esto es la eficiencia asintótica del algoritmo. Se denomina “asintótica” porque analiza el comportamiento de las funciones en el límite, es decir, su tasa de crecimiento.

La notación asintótica se describe por medio de una función cuyo dominio es los números naturales (N ) estimado a partir de tiempo de ejecución o de espacio de memoria de algoritmos en base a la longitud de la entrada. Se consideran las funciones asintóticamente no negativas.

La notación asintótica captura el comportamiento de la función para valores grandes de N.

Las notaciones no son dependientes de los tres casos anteriormente vistos, es por eso que una notación que determine el peor caso puede estar presente en una o en todas las situaciones.


La O Mayúscula

La notación O se utiliza para comparar funciones. Resulta particularmente útil cuando se quiere analizar la complejidad de un algoritmo, en otras palabras, la cantidad de tiempo que le toma a un computador ejecutar un programa.

Definición: Sean f y g funciones con dominio en R £ 0 o N es imagen en R. Si existen constantes C y k tales que:

x > k, | f (x) | £ C | g (x) | es decir, que para x > k, f es menor o igual a un multiplo de g, decimos que:

f (x) = O ( g (x) )

La definición formal es:

f (x) = O ( g (x) ) $ k , N | ” x > N, | f (x) | £ k| g (x) |

¿Qué quiere decir todo esto? Básicamente, que una función es siempre menor que otra función (por ejemplo, el tiempo en ejecutar tu programa es menor que x2 ) si no tenemos en cuenta los factores constantes (eso es lo que significa la k) y si no tenemos en cuenta los valores pequeños (eso es lo que significa la N).

¿Por qué no tenemos en cuenta los valores pequeños de N? Porqué para entradas pequeñas, el tiempo que tarda el programa no es significativo y casi siempre el algoritmo será sufic ientemente rápido para lo que queremos.

Así 3 + 5 – 9 = O () no significa que existe una función O() que es igual a 3N ³ + 5N ² – 9.

Debe leerse como: “3 + 5 – 9 es O-Grande de ” que significa: “3 + 5 – 9 está asintóticamente dominada por

La notación puede resultar un poco confusa. Veamos algunos ejemplos.

Ejemplo 1: Muestre que 3 + 5 – 9= O ().

De nuestra experiencia anterior pareciera tener sentido que C = 5.

Encontremos k tal que:

3 + 5 – 9 £ 5 for N > k :

  1. Agrupamos: 5 = 2 + 9
  2. Cuál k asegura que 5 =  para N > k?
  3. = 5
  4. Así que para N > 5, 5 =  = 2 + 9.
  5. = 5, k = 5 (no es único!)

Ejemplo 2: Muestre que N^4 ≠ O (3 + 5 – 9) .

Hay que mostrar que no existen C y k tales que para N > k, C* (3 + 5 – 9) ³ N4 es siempre cierto (usamos límites, recordando el curso de Cálculo).

lim x^4 / C(3 + 5  – 9) = lim x / C(3 + 5/x – 9/)
x → ∞                                   x → ∞
= lim x / C(3 + 0 – 0) = (1/3C) . lim x = ∞
x →  ∞                                          x → ∞

Así que sin importar cual sea el C que se elija, N4 siempre alcanzará y rebasará C* (3 + 5 – 9).

Podemos considerarnos afortunados porque sabemos calcular límites! Límites serán útiles para probar relaciones (como veremos en el próximo teorema).

 

Lema: Si el límite cuando x → ∞ del cociente |f (x)/g (x)| existe (es finito) entonces f (x) = O ( g (x) ). 

Ejemplo 3: 3N3 + 5N2 – 9 = O (N3 ). Calculamos:

lim  / (3 + 5  – 9) = lim 1 /(3 + 5/x – 9/) = 1 /3
x → ∞                                x → 

Listo!


La o Minúscula

La cota superior asintótica dada por la notación O puede o no ser ajustada asintóticamente. La cota 2n² = O(n²) es ajustada asintóticamente, pero la cota 2n = O(n²) no lo es. Utilizaremos la notación o para denotar una cota superior que no es ajustada asintóticamente.

Definimos formalmente o(g(n)) (“o pequeña”) como el conjunto: o(g(n)) = {f(n): para cualquier constante positiva c > 0, existe una constante n0 > 0 tal que: 0 £ f(n) £ cg(n) para toda n ³ n0 }.

Por ejemplo, 2n = o(n²), pero 2n² no pertenece a o(n²). Las notaciones de O y o son similares. La diferencia principal es, que en f(n)
= O(g(n)), la cota 0 £ f(n) £ cg(n) se cumple para alguna constante c > 0, pero en f(n) = o(g(n)), la cota 0 £ f(n) £ cg(n) se cumple para todas las constantes c> 0. Intuitivamente en la notación o, la función f(n) se vuelve insignificante con respecto a g(n) a medida que n se acerca a infinito, es decir:

lim (f(n)/g(n)) = 0.
x →

 


Diferencia entre O y o

Para o la desigualdad se mantiene para todas las constantes positivas, mientras que para O la desigualdad se mantiene sólo para algunas constantes positivas.

 


Las Notaciones Ω y θ

Ω Es el reverso de θ.

f (x ) = Ω(g (x )) →← g (x ) = O (f (x ))

Ω Grande dice que asintóticamente f (x ) domina a g (x ). Q Grande dice que ambas funciones se dominan mutuamente, en otras
palabras, son asintóticamente equivalentes.

f (x ) = θ(g (x ))
àß
f (x ) = O (g (x )) ^ f (x ) =Ω(g (x ))
f = θ (g): “f es de orden g

Propiedades y Cotas más Usuales

Propiedades de las notaciones asintóticas:

Relaciones de orden 

La notación asintótica nos permite definir relaciones de orden entre el conjunto de las funciones sobre los enteros positivos:

  • f ∈ O (g (x )) ↔ f £ g (se dice que f es asintóticamente menor o igual que g)
  • f ∈  o (g (x )) ↔ f <
  • f ∈  Q (g (x )) ↔ f =
  • f ∈  W (g (x )) ↔ f ³ g
  • f ∈  w (g (x )) ↔ f > g

Relaciones entre cotas 

  1. f(n) ∈ O(f (n))
  2. f(n) ∈ O(f (n)) ^ g(n) ∈ O(f (n )) ⇒ f(n) ∈ O(h (n ))
  3. f(n) ∈ O(g (n)) ⇒ g(n) ∈ W(h(n ))
  4. lim f(n)/g(n) = 0 ⇒ O(f (n)) ⊂ O(g (n))
    n →
  5. O(f (n)) = O(g (n)) ⇔ f(n) ∈ O(g (n)) ^ g(n) ∈ O(f (n ))
  6. O(f (n)) ⊂  O(g (n)) ⇔ f(n) ∈ O(g (n)) ^ g(n) ∉ O(f (n ))
  7. W(f(n )) ⊂ W(g (n)) ⇔ f(n) ∈ W(g (n)) ^ g(n) ∉ W(f (n ))

Relaciones de inclusión 

Son muy útiles a la hora de comparar funciones de coste en el caso asintótico. ∀x, y, a, e ∈ R >0

  • loga n O(logbn)
  • O(loga^x n) ∈ O(loga^(x+d) n)
  • O(loga^x n) ⊂  O(n)
  • O(n^x) ⊂  O(n^x+d )
  • O(n^x logay n) ⊂  O(n^x+d )
  • O(n^x) ⊂  O(2^n )

Propiedades de clausura: El conjunto de funciones del orden de f(n) es cerrado respecto de la suma y la multiplicación de funciones:

f1(n) ∈  O(g1(n)) ^ f2(n) ∈  O(g2(n)) ⇒ f1(n) + f2(n) ∈  O(g1(n) + g2(n))

f1(n) ∈  O(g1(n)) ^ f2(n) ∈  O(g2(n)) ⇒ f1(n) * f2(n) ∈  O(g1(n) * g2(n))

f1(n) ∈  O(g1(n)) ^ f2(n) ∈  O(g2(n)) ⇒ f1(n)+f2(n) ∈  O(max(g1(n), g2(n))

como consecuencia es que los polinomios de grado k en n son exactamente del orden de nk aknk + … + a1n + a0 ∈  Q(nk)

Cotas Asintóticas Más Usuales

 


Se nos complicó un toque… seguimos la próxima.

Dejá un comentario