PDF de programación - Análisis de Algoritmos y Complejidad

Universidad Central de Venezuela

Facultad de Ciencias

Escuela de Computación

ND 2001– 05

Análisis de Algoritmos y Complejidad

Eugenio Scalise, Rhadamés Carmona

e-mail: [email protected], [email protected]

Caracas, Septiembre 2001

ND 2001–05

Análisis de Algoritmos y Complejidad

Eugenio Scalise1

Rhadamés Carmona 2

Septiembre 2001

RESUMEN

El presente trabajo presenta una recopilación de notas y apuntes de
docencia correspondientes al tema “Análisis de Algoritmos y
Complejidad” que puede ser utilizado en diversos cursos de la
Licenciatura en Computación e
inclusive como material
introductorio para algunos cursos de post-grado. Se presentan los
conceptos y herramientas básicas para el cálculo de complejidad
tanto en tiempo como en espacio, para algoritmos escritos en
lenguajes imperativos (incluyendo algoritmos recursivos). Estas
herramientas están acompañadas de ejemplos didácticos que
ilustran su utilización. Se presenta también una reseña sobre las
técnicas clásicas para
resolución de problemas y sus
correspondientes estudios de complejidad en tiempo. Finalmente,
se presenta una breve introducción a la teoría de problemas NP-
completos. Cabe destacar que estas notas de docencia están
acompañadas de un conjunto de referencias bibliográficas que
complementan significativamente los conceptos aquí introducidos.

la

Palabras Clave: análisis de algoritmos, complejidad, complejidad
en tiempo, complejidad en espacio, complejidad de algoritmos
recursivos, problemas NP, problemas NP-completos.


1 Laboratorio MeFIS - Centro ISYS

e-mail: [email protected]

2 Laboratorio de Computación Gráfica
e-mail: [email protected]

CONTENIDO

1

Introducción........................................................................................ 2

2 Herramientas para el Análisis de Complejidad .................................. 3
2.1 Tasas de crecimiento ............................................................................................ 3
2.2 Análisis de Complejidad de Tiempo ................................................................... 4
Regla de la suma............................................................................................... 5
Regla del producto............................................................................................ 5
Análisis de complejidad en tiempo de las instrucciones de un lenguaje.......... 6
2.3 Análisis de Complejidad en Espacio................................................................... 8
Requerimientos estáticos de espacio ................................................................ 8
Requerimientos dinámicos de espacio............................................................ 10
2.4 Ejemplo................................................................................................................ 10
2.5 Análisis de Complejidad en programas recursivos ......................................... 12
Cota Superior de T(n)..................................................................................... 13
Forma Cerrada de T(n)................................................................................... 14
Solución General para una clase de recurrencias........................................... 14

3 Técnicas clásicas para la resolución de problemas ........................... 15
3.1 Divide y Conquista ............................................................................................. 15
3.2 Balanceo .............................................................................................................. 16

4 Modelos de Computación.................................................................. 17
4.1 RAM (Random Access Machine)...................................................................... 17
4.2 RASP (Random Access Stored Program Machine) ........................................ 17
4.3 Turing Machine (Máquina de Turing)............................................................. 17

5 Clasificación de los problemas según su complejidad....................... 18

Referencias .............................................................................................. 19

-
-
-
-
-
-
-
-
los datos de entrada del programa
la calidad del código objeto generado por el compilador
la naturaleza y rapidez de las instrucciones de máquina utilizadas
la complejidad en tiempo del algoritmo base del programa

1 Introducción
Un algoritmo es "una secuencia finita de instrucciones, cada una de las cuales tiene un
significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo
finito" [AHU 83]. Un programa es un algoritmo expresado en un lenguaje de programación
específico.
Los criterios para evaluar programas son diversos: eficiencia, portabilidad, eficacia,
robustez, etc. El análisis de complejidad está relacionado con la eficiencia del programa. La
eficiencia mide el uso de los recursos del computador por un algoritmo. Por su parte, el
análisis de complejidad mide el tiempo de cálculo para ejecutar las operaciones
(complejidad en tiempo) y el espacio de memoria para contener y manipular el programa
más los datos (complejidad en espacio). Así, el objetivo del análisis de complejidad es
cuantificar las medidas físicas: "tiempo de ejecución y espacio de memoria" y comparar
distintos algoritmos que resuelven un mismo problema.
El tiempo de ejecución de un programa depende de factores como [AHU 83]:




El tiempo de ejecución debe definirse como una función que depende de la entrada; en
particular, de su tamaño. El tiempo requerido por un algoritmo expresado como una
función del tamaño de la entrada del problema se denomina complejidad en tiempo del
algoritmo y se denota T(n). El “comportamiento límite” de la complejidad a medida que
crece el tamaño del problema se denomina complejidad en tiempo asintótica. De manera
análoga se pueden establecer definiciones para la complejidad en espacio y la complejidad
en espacio asintótica.
En muchos casos, la complejidad de tiempo de un algoritmo es igual para todas las
instancias de tamaño n del problema. En otros casos, la complejidad de un algoritmo de
tamaño n es distinta dependiendo de las instancias de tamaño n del problema que resuelve.
Esto nos lleva a estudiar la complejidad del peor caso, mejor caso, y caso promedio.
Para un tamaño dado (n), la complejidad del algoritmo en el peor caso resulta de tomar el
máximo tiempo (complejidad máxima) en que se ejecuta el algoritmo, entre todas las
instancias del problema (que resuelve el algoritmo) de tamaño n; la complejidad en el caso
promedio es la esperanza matemática del tiempo de ejecución del algoritmo para entradas
de tamaño n, y la complejidad mejor caso es el menor tiempo en que se ejecuta el
algoritmo para entradas de tamaño n. Por defecto se toma la complejidad del peor caso
como medida de complejidad T(n) del algoritmo.
Aún cuando son los programas que consumen recursos computacionales (memoria, tiempo,
etc.) sobre una máquina concreta, se realiza el análisis sobre el algoritmo de base,
considerando que se ejecuta en una máquina hipotética.

2

-
-
-
-
2 Herramientas para el análisis de complejidad
Esta sección presenta un conjunto de herramientas utilizadas para el cálculo de complejidad
de algoritmos en tiempo y espacio. Para mayor detalles se recomienda [AHU 74] y [AHU
83].

´ + y n0˛

c.g(n). (N

´ +-{0}. Se dice que f = O

(g) (f es de orden
no incluye el

tal que " n>n0 se cumpla f(n) £

´ +-{0}, y además $ c˛
(n3).

c.g(n). Así, 3n3+2n2 = O

´ +, y f: N
´ +, y f: N
(g1) (cid:217)
(g1) (cid:217)
(g) (cid:217)

2.1 Tasas de crecimiento
Definición 1: Sean f y g dos funciones, f,g: N
g) si y sólo si existe c˛
0).
La relación O
denota una dominancia de funciones, en donde la función f está acotada
superiormente por un múltiplo de la función g (f es dominada por c.g(n)). Así, la expresión
f=O
(g) refleja que el orden de crecimiento asintótico de la función f es inferior o igual al de
la función g.
Ejemplo:
f(n) = 3n3+2n2 y g(n) = n3. Aunque f(0) está definida, podemos restringir su dominio a f(n)
con n>0. Así, que f,g:N
(n0 = 0) tal que " n>n0
se cumple f(n) £
A continuación se enumeran alguna propiedades de la relación O:
Si c˛
Si c˛
Si f1=O
Si f1=O
Si f1=O
(g)
Definición 2: Sean f y g dos funciones, f,g: N
orden de crecimiento (f=Q
d.g(n)£
Se puede demostrar también que Q
simétrica y transitiva: f = Q
(f), f = Q
Además, Q
Sean f y g dos funciones, f,g: N
Si c˛
Si c˛
Si f1=Q
Si f1=Q
Si f1=Q
(f+g)k = Q

´ +-{0}, entonces, c.f=O
(c.f)”
´ +-{0}, entonces O
(g2) entonces f1+f2=O
(g2) entonces f1.f2=O
(g) entonces f1+f2=O

´ +-{0}, entonces, c.f=Q
´ +-{0}, entonces Q
(c.f)”
(g2) entonces f1+f2=Q
(g2) entonces f1.f2=Q
(g) entonces f1+f2=Q

satisface las siguientes propiedades:
´ +-{0}. f=Q
(f)

´ +, y f: N
´ +, y f: N
f2=Q
(g1) (cid:217)
f2=Q
(g1) (cid:217)
f2=Q
(g) (cid:217)
(fk+gk)

´ +-{0}. Se dice que f y g tienen igual
tal que " n>n0 se cumpla

´ + y n0˛

es una relación de orden (total) por ser reflexiva,
(g) (cid:222)
(h).

(f), f = Q

g = Q

g = Q

f = Q

(Max{g1,g2})
(g1.g2)

(g)) si y sólo si existe c,d ˛

(g)(cid:219)

f=O

(g) (cid:217)

g=O

(f)

(f)

(f)

(g1+g2)
(g1.g2)

(f)

(g)

f2=O
f2=O
f2=O

f(n)£ c.g(n).

´ + (c = 5) y n0˛

(g) (cid:217)

(h) (cid:222)

3

fi
N
fi
N
-
fi
-
fi
O
-
-
-
fi
N
-
fi
-
fi
-
fi
Q
-
-
-
-
En la siguiente figura [Bro 89], se presenta un ejemplo de dos funciones f y g con la misma
tasa de crecimiento.

Fig. 1.- Do