FC-FISC-1-8-2016)
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
COMPLEJIDAD ALGORITMICA
Facilitador(a): Ing. Samuel Jiménez Asignatura: Análisis y Diseño de Algoritmos
A. TÍTULO DE LA EXPERIENCIA: M ó d u l o 2: Complejidad Algorítmica
B. TEMAS:
• Definición de comportamiento asintótico
• Función T(n)
C.
D.
E.
C. OBJETIVO(S):
✓ Identificar los conceptos básicos de la complejidad algorítmica.
✓ Comparar los tiempos de ejecución de los distintos algoritmos propuestos.
✓ Distinguir el coste de un algoritmo en cuanto al mejor, el peor o el caso promedio a la solución de
un problema.
✓ Analizar la complejidad de un algoritmo por medio de las medidas asintóticas.
✓ Aplicar reglas prácticas para el cálculo de la complejidad algorítmica.
✓ Ilustrar la complejidad algorítmica en los algoritmos de búsquedas y ordenamiento.
1. ¿Qué es comportamiento asintótico?
En computación, la notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de
un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el
tamaño de la entrada (input).
Desde este punto de vista, el algoritmo más eficiente posible sería aquel en el que el número de
operaciones llevadas a cabo no varíe según crezca la entrada. Esto es lo que sería una función constante.
Por ejemplo:
El número de operaciones realizados es
independiente del tamaño de la entrada (el
trabajo realizado es el mismo para n = 1 que
para n = 1000). Por esto, decimos que son
constantes, y su Big O (O Grande) es O (1).
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ FC-FISC-1-8-2016)
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
COMPLEJIDAD ALGORITMICA
El siguiente ejemplo:
En esta función, el número de operaciones va a ir aumentando según aumente el valor de n. En este caso el
aumento va a ser lineal, ya que el bloque principal de nuestro código se va a ejecutar una vez para cada
iteración, y así n = 1 resulta en 1 operación y n = 1000 resulta en 1000 operaciones. Por ello, en notación
asintótica diríamos que nuestro algoritmo tiene una O grande (Big O) de O(n). Si tuviéramos un algoritmo
que hace la misma iteración dos veces (una después de otra), diríamos que es O(2n), y si la segunda
iteración estuviera anidada entonces sería O(n^2) (n al cuadrado).
Ahora observemos ambos ejemplos y encontremos donde esta la eficiencia de nuestro algoritmo:
Ambos códigos muestran el mismo resultado, pero podemos observar que el primer algoritmo tiene una O
Grande de O(n), es lineal, mientras que el segundo, tiene una O Grande de O (1), es constante, ya que el
número de operaciones es siempre 1, independientemente del valor de n; es mucho más eficiente.
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ FC-FISC-1-8-2016)
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
COMPLEJIDAD ALGORITMICA
Para realizar el análisis de un algoritmo, es necesario:
• Conocer la complejidad del problema que resuelve el algoritmo
• Conocer la dimensión de la entrada (Número de elementos)
• Determinar el número de operaciones a realizar
La complejidad de un algoritmo se representa a través de una función matemática:
• Polinomial
• Logarítmica
• Exponencial
Un algoritmo puede estar compuesto de dos o mas operaciones, por lo que determinar la complejidad
depende de identificar la operación más costosa en el algoritmo.
Para determinar la complejidad de un algoritmo, se siguen los siguientes pasos:
• Se analiza el algoritmo para determinar una función que represente el número de operaciones a
realizar por el mismo.
• Se define en términos de funciones matemáticas el orden de la función.
• Se clasifica de acuerdo con su complejidad.
Notación Omega
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ FC-FISC-1-8-2016)
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
COMPLEJIDAD ALGORITMICA
Notación O
Notación Theta
2. Función T(n)
El tiempo de ejecución de un algoritmo depende de cuánto tiempo le tome a una computadora ejecutar las
líneas de código del algoritmo, y eso depende de la velocidad de la computadora, el lenguaje de
programación y el compilador que traduce el programa del lenguaje de programación al código que se
ejecuta directamente en la computadora, entre otros factores.
Ejemplo:
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ FC-FISC-1-8-2016)
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
COMPLEJIDAD ALGORITMICA
Análisis:
• En la primera 4 línea de nuestro código no existe ninguna operación elemental.
• A partir de la línea quinta, encontramos las operaciones de asignación, mayor igual que son operaciones
elementales.
2 operación
elemental
(Incremento)
1 operación 1 operación
elemental elemental
(Inicialización) (comparación)
1 operación 1 operación
elemental elemental (La
(Impresión) variable)
1 operación
elemental
(Retorno)
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ FC-FISC-1-8-2016)
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
COMPLEJIDAD ALGORITMICA
La función se repite 8 veces
La función T(n) seria:
T (n) = 1+1+∑18(2 + 1 + 2)+1
T (n)= 3 + 8*5
T (n) = 43 (Complejidad Constante)
