Tema 3
Algoritmia y Complejidad
Tema 3. Análisis de
algoritmos
Índice
Esquema
Ideas clave
3.1. Introducción y objetivos
3.2. Notación asintótica
3.3. Análisis matemático de algoritmos no recursivos
3.4. Análisis matemático de algoritmos recursivos
3.5. Análisis empírico de algoritmos
A fondo
Análisis de algoritmos
P, NP and mathematics – a computational complexity
perspective
Test
Esquema
Algoritmia y Complejidad 3
Tema 3. Esquema
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
3.1. Introducción y objetivos
Para estudiar este tema deberás leer el capítulo dos (pp. 15-31) del manual de la
asignatura, disponible en la Biblioteca Virtual de UNIR:
Joyanes, L. et al. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
Puedes completar el estudio, asistiendo o visualizando la clase presencial,
repasando el resumen de ideas clave que se dan a continuación y comprobando si
has comprendido los conceptos mediante la realización del test de autoevaluación
del tema.
En el tema anterior se introdujo cómo medir la eficiencia de los algoritmos.
Los objetivos de este tema son:
▸ Formalizar matemáticamente los ordenes de crecimiento.
▸ Analizar matemáticamente los algoritmos recursivos o no recursivos.
▸ Analizar empíricamente los algoritmos.
Algoritmia y Complejidad 4
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
3.2. Notación asintótica
El análisis de complejidad computacional busca identificar cómo crece el coste de
ejecución C(n) cuando el tamaño de la entrada crece. La notación asintótica
captura el orden de crecimiento de la operación básica según el tamaño de los datos
de entrada n se va haciendo grande.
En la siguiente discusión C(n) y g(n) son funciones no negativas definidas sobre los
números naturales. Además, t(n) representa el tiempo de ejecución, normalmente
representado por la cuenta de operaciones básicas C(n), y g(n) es una función
simple a comparar con C(n).
Para comparar las órdenes de crecimiento se utilizan tres notaciones:
▸ Big O (o cota superior asintótica). O(g(n)) es el conjunto de todas las funciones
con menor o igual orden de crecimiento que g(n). Por ejemplo, si C(n)=2n, C(n)
O(n2).
▸ Big (o cota inferior asintótica). (g(n)) es el conjunto de todas las funciones con
mayor o igual orden de crecimiento que g(n). Por ejemplo, si C(n)=n3, C(n) (n2).
▸ Big (o cota ajustada asintótica). (g(n)) es el conjunto de todas las funciones
que tienen el mismo orden de crecimiento que g(n). Por ejemplo, si C(n)=2n2+n,
C(n) (n2).
Obsérvese que:
Además de la notación big O, big y big , tenemos las notaciones little o, little y
little .
Algoritmia y Complejidad 5
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
La notación big O permite que g(n) esté multiplicada por una constante c, es decir:
La notación little o obliga a que la relación anterior se cumpla para cualquier valor de
c positivo, es decir:
Análogamente la notación little nos dice que:
Finalmente, la notación little nos dice que:
Algoritmia y Complejidad 6
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
3.3. Análisis matemático de algoritmos no
recursivos
El plan general para analizar la eficiencia temporal de un algoritmo no recursivo es:
Figura 1. Plan general. Eficiencia temporal de un algoritmo no recursivo.
L a s dos reglas más usadas para obtener fórmulas cerradas a partir de
sumatorios son:
▸ , donde l u
Algoritmia y Complejidad 7
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
Las dos reglas de manipulación de sumas más usadas son:
Algoritmia y Complejidad 8
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
3.4. Análisis matemático de algoritmos recursivos
El plan general para analizar la eficiencia temporal de un algoritmo recursivo es:
Figura 2. Plan general. Eficiencia temporal de un algoritmo recursivo.
Algoritmia y Complejidad 9
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
3.5. Análisis empírico de algoritmos
El plan general para análisis empírico de un algoritmo es:
Figura 3. Plan general para análisis empírico de un algoritmo.
Algoritmia y Complejidad 10
Tema 3. Ideas clave
© Universidad Internacional de La Rioja (UNIR)
A fondo
Análisis de algoritmos
Valenzuela Ruz, V. (2003). Manual. Análisis de algoritmos. Versión 1.0. Copiapó,
Chile:
Instituto Nacional de Capacitación. Recuperado de [Link]
om/2014/12/[Link]
Este documento te servirá para complementar lo estudiado en el tema. El capítulo
cuatro, Análisis de algoritmos (pp. 35-51) abarca los conceptos de órdenes de
complejidad y notación asintótica.
Algoritmia y Complejidad 11
Tema 3. A fondo
© Universidad Internacional de La Rioja (UNIR)
A fondo
P, NP and mathematics – a computational
complexity perspective
Wigderson, A. (2006). P, NP and mathematics – a computational complexity
perspective. Recuperado de [Link]
La cuestión P contra NP se distinguió como la cuestión central de la informática
teórica hace casi cuatro décadas. La búsqueda de solución y, más en general, de
entender el poder y los límites de eficiencia computacional, ha llevado al desarrollo
de la teoría de la complejidad. Si bien esta disciplina matemática, en general, y el P
vs NP, en particular, han ganado protagonismo en la comunidad matemática durante
la última década, todavía se percibe principalmente como un problema de la
informática. En este artículo en inglés se trata de explicar por qué este problema, y
otros en complejidad computacional, no son solo problemas informáticos, sino
también problemas acerca de las matemáticas.
Algoritmia y Complejidad 12
Tema 3. A fondo
© Universidad Internacional de La Rioja (UNIR)
Test
1. La notación asintótica captura:
A. El comportamiento de las operaciones básicas en el infinito.
B. El comportamiento de un algoritmo cuando n es infinito.
C. El orden de crecimiento de una operación básica en función de n.
D. Ninguna de las respuestas anteriores es correcta.
2. Las funciones que miden el coste computacional tienen:
A. Dominio positivo y entero.
B. Dominio positivo y racional.
C. Dominio positivo y real.
D. Dominio real.
3. En la notación asintótica la función g(n) es:
A. La que mide el tiempo de ejecución.
B. La que mide el número de operaciones básicas.
C. Las respuestas A o B pueden ser correctas.
D. Una función simple.
4. El conjunto de todas las funciones con menor o igual orden de crecimiento que
g(n) corresponde con:
A. Big O.
B. Little o.
C. Big
D. Big
Algoritmia y Complejidad 13
Tema 3. Test
© Universidad Internacional de La Rioja (UNIR)
Test
5. ¿Cuál es el orden de complejidad temporal del siguiente fragmento de código? int
i, j, k = 0; for (i = n / 2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n / 2; }}
A. O(n).
B. O(nlogn).
C. O(n2).
D. O(n2logn).
6. ¿Cuál es el orden de complejidad temporal del siguiente fragmento de código? for
(i = n / 2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n / 2; } }
A. O(n).
B. O(sqrt(n)).
C. O(log(n)).
D. O(n/2).
7. ¿Cuál de estos algoritmos requiere un análisis de caso medio y de caso peor?
A. La búsqueda de un elemento en una matriz.
B. La suma de matrices.
C. La multiplicación de matrices.
D. El inverso de una matriz.
8. ¿Dónde se usan habitualmente sumatorios?
A. En el análisis de algoritmos no recursivos.
B. En el análisis de algoritmos recursivos.
C. En el análisis de recurrencias.
D. En el análisis empírico de algoritmos.
Algoritmia y Complejidad 14
Tema 3. Test
© Universidad Internacional de La Rioja (UNIR)
Test
9. ¿Cuándo se acostumbra a determinar una unidad de medida de eficacia?
A. En el análisis de algoritmos no recursivos.
B. En el análisis de algoritmos recursivos.
C. En el análisis de recurrencias.
D. En el análisis empírico de algoritmos.
10. ¿Cuál de estas funciones de coste de ejecución pertenecen a O(n3) y a (n3)?
A. 1/3n3+2500n2
B. 0.00001·n4
C. 2500n2
D. Ninguna de las respuestas anteriores es correcta.
Algoritmia y Complejidad 15
Tema 3. Test
© Universidad Internacional de La Rioja (UNIR)
