0 0 12:00

1 1 12:00

Temas

Teoría de la Complejidad

Análisis de Algoritmos

Complejidad temporal y espacial

Funciones Matemáticas

Ordenes

Notación Asintótica

Principios para determinar el orden de un algoritmo

Objetivo

Que el estudiante logre:

Entender los fundamentos de la Teoría de la Complejidad.

Medir la eficiencia de algoritmos.

Diferenciar entre los algoritmos de complejidad polinómica y no

polinómica.

2 2 12:00

Algoritmo es un procedimiento para resolver un problema cuyos pasos son concretos y no ambiguos. El algoritmo debe ser correcto, de longitud finita.

Un algoritmo debe satisfacer las siguientes condiciones:

1. Consiste en un conjunto finito de instrucciones simples y precisas, que son descritas por un

conjunto finito de símbolos.

2. Siempre producirá el resultado (la respuesta al problema) en un número finito de pasos.

3. Hay un agente computacional que lleva a cabo las instrucciones (guardar, recabar y realizar los

pasos de una computación). Este requerimiento es satisfecho tanto por las computadoras como

por los seres humanos, puesto que ambos tienen memoria.

4. El agente computacional debe realizar las instrucciones por medio de pasos discretos.

5. El agente computacional debe llevar a cabo las instrucciones determinísticamente o

mecánicamente.

Un algoritmo es una serie finita de pasos para resolver un problema.

¿Qué es un algoritmo?

¿Qué condiciones debe satisfacer?

3 3 12:00

¿Cómo construir algoritmos?

¿Cómo expresar algoritmos?

¿Cómo validar algoritmos?

¿Cómo analizar algoritmos?

4 4 12:00

La leyenda sobre el tablero de ajedrez Mucho tiempo atrás, el visir Sissa ben Dahir inventó el juego del ajedrez para el rey Shirham de la India. El rey ofreció a Sissa la posibilidad de elegir su propia recompensa. Sissa le dijo al rey que podía recompensarle: o bien con una cantidad equivalente a la cosecha de trigo en su reino de dos años, o bien con una cantidad de trigo que se calcularía de la siguiente forma:

• un grano de trigo en la primera casilla de un tablero de ajedrez, • más dos granos de trigo en la segunda casilla, • más cuatro granos de trigo en la tercera casilla, • y así sucesivamente, duplicando el número de granos en cada casilla, hasta llegar a la última casilla.

El rey pensó que la primera posibilidad era demasiado cara mientras que la segunda, medida además en simples granos de trigo, daba la impresión de serle claramente favorable. Así que sin pensárselo dos veces pidió que trajeran un saco de trigo para hacer la cuenta sobre el tablero de ajedrez y recompensar inmediatamente al visir.

5 5 12:00

El número de granos en la primera fila resultó ser: 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 = 255

La cantidad de granos en las dos primeras filas es: Al llegar a la tercera fila el rey empezó a pensar que su elección no había sido acertada, pues para llenar las tres filas necesitaba: granos, que pesan alrededor de 600 kilos . . En efecto, para rellenar las 64 casillas del tablero hacen falta granos, cantidad equivalente a las cosechas mundiales actuales de 1.000 años!!. La función 2n − 1 (exponencial) representa el número de granos adeudados en función del número n de casillas a rellenar. Toma valores desmesurados aunque el número de casillas sea pequeño. El coste en tiempo de algunos algoritmos expresado en función del tamaño de los datos de entrada es también exponencial. Por ello es importante estudiar el coste de los algoritmos y ser capaces de comparar los costes de algoritmos que resuelven un mismo problema.

6 6 12:00

La técnica que se utilizaba en los primeros años de la programación para comparar la eficiencia de distintos algoritmos consistía en ejecutarlos para datos diferentes y medir el tiempo consumido.

Dado que las máquinas y los lenguajes eran dispares, y que el tiempo de ejecución depende no sólo del tamaño sino también del contenido de los datos, resultaba muy difícil comparar tales resultados.

El primer estudio serio sobre la eficiencia de los algoritmos se lo debemos a Daniel Goldenberg del MIT. En 1952 realizó un análisis matemático del número de comparaciones necesarias, en el mejor y en el peor caso, de cinco algoritmos distintos de ordenación.

La tesis doctoral de Howard B. Demuth de la Universidad de Stanford estableció en 1956 las bases de lo que hoy llamamos análisis de la complejidad de los algoritmos.

7 7 12:00

Dado un problema computacional:

¿Existe un algoritmo óptimo para resolver el problema? en

tal caso,

¿Cuál será el criterio de optimalidad que deberá utilizarse?

¿Es posible medir el tiempo de ejecución o la memoria

necesaria para cada posible algoritmo que resuelva el

problema?

El área de las ciencias de la computación que se ocupa de estos temas

se denomina Teoría de la Complejidad y los resultados que produce

son medidas y criterios para determinar la eficiencia de los algoritmos.

8 8 12:00

TIPO DE ANÁLISIS

ANÁLISIS DE UN ALGORITMO EN PARTICULAR: se trata de investigar el costo de usar un determinado algoritmo para resolver un problema específico.

ANÁLISIS DE UNA CLASE DE ALGORITMOS: se investiga toda una familia de algoritmos que permiten resolver un problema, procurando obtener él que demande menor costo

SEGÚN EL MOMENTO

ESTIMACIÓN A PRIORI Hace uso de un modelo matemático, como lo es una función, basada en un computador idealizado y en un conjunto de operaciones con costos de ejecución perfectamente especificados. Proporciona sólo un RESULTADO APROXIMADO.

COMPROBACIÓN A POSTERIORI Se lleva a cabo en el momento de la ejecución del programa en un computador y consiste en medir los tiempos de corrida del programa en cuestión. Proporciona VALORES REALES.

9 9 12:00

¿CÓMO MEDIR LA EFICIENCIA DE LOS ALGORITMOS?

Contando el número de pasos (tiempo de ejecución del algoritmo.)

COMPLEJIDAD EN TIEMPO

Determinando el espacio utilizado por el agente computacional (máquina, persona) que lo ejecuta (espacio utilizado por el algoritmo.)

COMPLEJIDAD EN ESPACIO

LA COMPLEJIDAD DE UN ALGORITMO ES UNA MEDIDA DE LA CANTIDAD DE RECURSOS (TIEMPO, MEMORIA) QUE EL ALGORITMO REQUIERE.

10 10 12:00

COMPLEJIDAD TEMPORAL (ESPACIAL).

Tiempo (o espacio) requerido por un algoritmo, expresado en base a una función que depende del tamaño del problema.

COMPLEJIDAD TEMPORAL ASINTÓTICA (y ESPACIAL). Comportamiento límite conforme el tamaño del problema se incrementa. Determina el tamaño del problema que puede ser resuelto por un algoritmo.

11 11 12:00

Para evaluar la rapidez o viabilidad de un algoritmo (eficiencia) se imagina

que al algoritmo se le suministra entradas cada vez mayores y se observa

la razón de crecimiento del tiempo insumido para ejecutarlo.

Para analizar esto se consideran dos tipos de funciones matemáticas:

FUNCIÓN

POLINÓMICA

EXPONENCIAL

ALGORITMOS EFICIENTES

ALGORITMOS NO EFICIENTES

12 12 12:00

El objetivo primario del estudio de la complejidad es definir cuáles problemas son tratables y cuáles no, para luego considerar distintos grados de tratabilidad.

Problema

tratable: complejidad polinomial

intratable: complejidad exponencial

13 13 12:00

Si un algoritmo ejecuta n operaciones por microsegundo, el algoritmo daría:

Un microsegundo es la millonésima parte de un segundo

14 14 12:00

Ejemplo 1(search): problema de pertenencia a un conjunto.

procedure search (var X: int-set: y: integer, var found: boolean);

var i: integer;

begin

i := 1;

found := false;

while i <= n and not found do

if X [ i ] = y

then

found := true;

else

i := i + 1;

enddo

end { search}

15 15 12:00

Complejidad en espacio (número total de celdas requeridas): E = |X| + k donde |X| es la longitud del arreglo (es decir, n) y k es una constante que no depende del cardinal de X (celdas usadas para almacenar todas las otras variables y el código objeto).

El tiempo requerido por el procedimiento search es muy variable mejor caso: Tb = h + r peor caso: Tw = h + r. n

Complejidad en tiempo: T = T1 + T2 donde T1 es el tiempo insumido fuera del ciclo while y T2 es el tiempo dentro de éste. Se observa que T1 es un valor constante (h) que no depende del conjunto X, en cambio T2 depende de él, así: T = h + T2 (X)

16 16 12:00

O(f(n)

Algoritmos de tiempo polinómico

Algoritmos de tiempo exponencial

O (p(n)) O (cn)

Los algoritmos se consideran efectivos o tratables hasta Complejidad polinómica.

Los exponenciales son válidos para valores pequeños de n.

Para diferenciar la eficiencia de los algoritmos se utilizan los órdenes de complejidad. Éstos se expresan en función de n que representa el tamaño (dado o estimado) de los datos de entrada.

17 17 12:00

f(n) = 0(f(n)): el orden de una función es igual al valor de la

función.

c * f(n) = 0(f(n)): el orden de una función multiplicada por

una constante es igual al valor de la función.

0 (0(f(n))) = 0 (f(n)): el orden del orden de una función es

igual al orden de la función.

0 (f(n)) + 0 (g (n)) = 0 (max f(n),g (n)): la suma de los

ordenes de dos funciones es igual al orden máximo de las

funciones.

0 (f(n)) * 0 (g (n)) = 0 (f(n) * g (n)): el producto de dos

ordenes de funciones es igual al orden del producto de las

mismas.

18 18 12:00

Notación Denominación

O(1) orden constante

O(log n) orden logarítmico

O([log n]c) orden polilogarítmico

O(n) orden lineal

O(n · log n) orden lineal logarítmico

O(n²) orden cuadrático

O(nc) orden polinómico

O(cn), n > 1 orden exponencial

O(n!) orden factorial

O(nn) orden doblemente exponencial

19 19 12:00

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.

20 20 12:00

Notación “O grande” (O mayúscula) (Omicron, "Big-O") : se utiliza para manejar la cota superior del tiempo de ejecución.

Notación “o minúscula”: denotar una cota superior que no es ajustada asintóticamente.

Notación “omega” (): se utiliza para manejar la cota inferior del tiempo de ejecución

Notación “theta”(): se utiliza para indicar el orden exacto de complejidad

21 21 12:00

Notación “O grande” (O(f)), denota el conjunto de las funciones g que crecen a lo sumo tan rápido como f (es decir, f llega a ser en algún momento una cota superior para g).

Formalmente:

Constante multiplicativa

n0 indica a partir de que punto f es realmente una cota superior para g.

Se dice que la función g(n) “es de orden f(n)” [O(f(n))], si existen constantes positivas c0 y n0 tales que g(n) <= c0 f(n) cuando n >= n0

22 22 12:00

Se trata de buscar una función sencilla, f(n), que acote superiormente el crecimiento de otra g(n), en cuyo caso se notará como g(n) O(f(n)) (g es del orden de f).

Cota asintótica superior

g(n)

cf(n)

n0

g(n)=O(f(n))

La función n²+200n está acotada superiormente por n². Quiere decir que cuando n tiende a infinito el valor de 200 n se puede despreciar con respecto al de n².

23

La función n² puede ser acotada inferiormente por la función n. Para demostrarlo basta notar que para todo valor de n≥1 se cumple n≤n². Por tanto n² = Ω(n) (sin embargo, n no sirve como cota inferior para n²). La función n²+200 n está acotada inferiormente por n². Quiere decir que cuando n tiende a infinito el valor de 200 n se puede despreciar con respecto al de n².

Cota asintótica inferior

g(n)=Ω(f(n))

g(n)

cf(n) n

0

g(n) cf(n) para un número infinito de valores de n.

24

g(n) = Θ(f(n)) si y

sólo si g(n) = O(f(n))

y g(n) = Ω(f(n))

La función n +10 puede ser acotada por la función n. Para demostrarlo basta notar que para todo valor de n ≥1 se cumple g(n)≤ h(n) ≤11g(n). Por tanto n+10 = Θ(x). La función n²+200 n está acotada de forma ajustada por n². Quiere decir que cuando n tiende a infinito el valor de 200 n se puede despreciar con respecto al de n².

g(n)= Θ (f(n))

g (n)

c1f(n) n

0

c2f(n)

25

DEFINICIÓN 1: Sean g, f dos funciones de números naturales a números reales. La función g es O(f(n)) si y sólo si existe una constante real c > 0 tal que:

cnf

ng

n

)(

)(lim

limg n

f nn

( )( )

0

DEFINICIÓN 2: Sean g y f dos funciones sobre los naturales. O(g(n)) < O(f(n)) si y sólo si

limg n

f nn

( )( )Similarmente, O (g(n)) > O (f(n)) si y sólo si

DEFINICIÓN 3 Si f(n) domina asintóticamente a g(n) se dice que g(n)=0(f(n)) , es decir, es de orden f(n) ya que f(n) es una cota superior a la tasa de crecimiento de g(n). Para especificar una cota inferior para la velocidad de crecimiento de g(n) se usa la notación (h(n)), que se lee "g(n) es omega mayúscula de h(n)" o "simplemente g(n) es omega de h(n)" lo cual significa que existe una constante c tal que: g(n) ch(n) para un número infinito de valores de n.

26 26 12:00

Asignación: variable = expresión

Si la expresión es sencilla, por ejemplo:

variable = 3.141592 variable = a +b etc.

Entonces el tiempo de ejecución sería del orden O(1); en caso contrario habría que determinar el orden de la expresión, siendo de ese orden la asignación.

27 27 12:00

Secuencia de comandos sentencia 1 sentencia 2 ... sentencia s

El tiempo total de ejecución sería la suma de los tiempos de ejecución de cada sentencia; por tanto, sería del orden de:

O(f1(n)+f2(n)+ ... +fs(n)) o lo que es lo mismo:

O(max(f1(n), f2(n), ..., fs(n)) (Regla de la suma) es decir la dominante de todas las funciones.

28 28 12:00

Instrucción de bifurcación

si expresión entonces bloque de sentencias

si no otro bloque de sentencias

fin si

La expresión, el primer bloque de sentencias y el segundo bloque de sentencias tendrán unos tiempos de ejecución determinados T1(n), T2(n), T3(n) con unos órdenes O(f1(n)), O(f2(n)) y O(f3(n)). El tiempo de ejecución de la estructura será la dominante de dichas funciones.

29 29 12:00

Estructura repetitiva:

desde i=a hasta f(n) hacer bloque de sentencias

fin desde El bucle anterior se ejecuta un número de veces que es función del

tamaño del problema (n); si el tiempo de ejecución del cuerpo del bucle es de orden O(g(n)) entonces el tiempo de ejecución del bucle completo será del orden O(f(n)·g(n)).

Si el bucle fuera un mientras o un repetir...hasta, entonces se debería tener en cuenta el orden de la expresión lógica, determinar la dominante entre dicha expresión y el cuerpo del bucle y aplicar la regla anterior.

30 30 12:00

1. El tamaño del problema viene definido en este caso por la variable n.

2. Se va a la zona más interna del bucle (escribir i+j).

3. Se trata de una sentencia elemental, por tanto, su tiempo de ejecución será de orden O(1).

4. El bucle más interno (desde j=1 a n) se ejecuta n veces y su cuerpo tiene complejidad O(1), por tanto, este bucle tiene complejidad O(n·1)=O(n).

5. El bucle más externo (desde i=1 a n) se ejecuta n veces y su cuerpo (el bucle anterior) tiene complejidad O(n), por tanto, este bucle (y el algoritmo) tiene complejidad O(n·n)=O(n2).

desde i=1 a n desde j=1 a n

escribir i+j fin desde

fin desde

Ejemplo 1:

31 31 12:00

1. El tamaño del problema viene definido en este caso por la variable n.

2. Se va a la zona más interna del bucle (f=f·i). 3. Se trata de dos sentencias elementales (producto y

asignación), por tanto, su tiempo de ejecución será de orden O(1).

4. El bucle (desde i=1 a n) se ejecuta n veces y su cuerpo tiene complejidad O(1), por tanto, este bucle (y el algoritmo que permite calcular el factorial de n) tiene complejidad O(n·1)=O(n).

f=1 desde i=1 a n

f=f·i fin desde

Ejemplo 2:

¿Qué significa esto? Significa que si el cálculo del factorial de 10 en un ordenador tardó, por ejemplo, 2 segundos; ese mismo algoritmo calcularía en ese mismo ordenador el factorial de 20 como máximo en 4 segundos y el de 30 un máximo de 6 segundos.

32 32 12:00

ORDENAR UN VECTOR DE N ELEMENTOS DE MENOR A MAYOR

procedimiento

begin

(1) For i = 1 to n-1 do

(2) For j = i to n do

(3) if A [i] > A [j] then begin

(4) T = A [i] O (1)

(5) A [i] = A [j] O (1)

(6) A [j] = T O (1)

next j

next i

end

Las proposiciones (4), (5) y (6) toman O(1), por la regla de la suma O (max (1,1,1)) = O (1)

(1) El ciclo de las i se ejecuta n-1 veces

(2) El ciclo de las j se ejecuta n-i veces

T = = n - 1 + n - 2 + ... + n - ( n - 1 ) = (n 2 - n) / 2 ( )n ii

n

1

1

T(n) = (n 2 - n) / 2

O (n2 )

33 33 12:00

El compromiso espacio-tiempo o tiempo-memoria es una situación en la que la memoria puede reducirse a costa de la ejecución más lenta de los programas, o viceversa, el tiempo de ejecución puede reducirse a costa de incrementar el uso de memoria. Ejemplos • Algoritmo que utiliza una tabla de búsqueda: una implementación puede incluir la tabla completa, lo que reduce el tiempo de ejecución, pero incrementa la cantidad de memoria necesitada, o puede calcular entradas de la tabla a medida que se necesiten, incrementando el tiempo de ejecución, pero reduciendo los requisitos de memoria.

• Problema de almacenamiento de datos: si los datos se almacenan de forma no comprimida se necesita más espacio pero menos tiempo que si los datos se almacenan de forma comprimida (ya que la compresión reduce la cantidad de espacio utilizado, pero utiliza tiempo de ejecución para procesar el algoritmo de compresión).

34 34 12:00

Estimación a priori Estimación a posteriori

Se analizan algoritmos Se analizan programas

Se obtienen valores aproximados Se obtienen valores exactos

Independiente de la máquina Dependiente de la máquina

Permite hacer predicciones sobre el comportamiento del algoritmo en cualquier máquina

Poco predictivo

Existen dos clases de complejidad: la complejidad de tiempo y la

complejidad de espacio. La complejidad de tiempo es más critica.

Existen dos estudios posibles sobre el tiempo de ejecución de un

algoritmo:

Obtener una medida teórica a priori mediante la función de

complejidad

Obtener una medida real del algoritmo, a posteriori, para unos

valores concretos en un computador determinado.

35 35 12:00

Los algoritmos eficientes se dice que son de orden de alguna

función polinómica: 0(p(n)) (no interesa la forma exacta del

polinomio p). Los del tiempo exponencial son 0(cn), para alguna

constante c.

La complejidad depende del tamaño de la entrada n. Se puede

realizar un análisis de complejidad para el peor, mejor y caso

promedio.

La complejidad depende del algoritmo diseñado para solucionar

un problema dado. Por ejemplo, el mismo problema (búsqueda en

un conjunto ordenado) puede ser resuelto con diferentes

complejidades por dos algoritmos diferentes (search y binary-

search).

Para determinar el tiempo de ejecución de un algoritmo se define

una función de costo o perfomance, usando como parámetro

de la misma el tamaño n de los datos del problema, escribiendo

f(n).

36 36 12:00

0 O (g (n)) < O (f (n))

c O (g (n)) = O (f (n))

O (g (n)) > O (f (n))

El orden de una función es una aproximación o estimación del

tiempo o espacio requerido para la ejecución de un algoritmo.

La dominancia asintótica permite comparar dos algoritmos y

determinar hasta que valor de n (datos de entrada) un algoritmo es

más eficiente que otro.