Análisis de algoritmos

Tema 04: Análisis temporal

M. en C. Edgardo Adrián Franco Martínez 1

http://www.eafranco.com
edfrancom@ipn.mx
@edfrancom edgardoadrianfrancom
Contenido

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
• Caso de entrada
• Ejemplo 1 (Búsqueda lineal)
• Operación básica
• Ejemplo 2 (Producto de 2 mayores)
• Elección de la operación básica
• Concepto de Instancia
• Análisis Peor Caso, Mejor Caso y Caso Promedio
• Análisis Temporal (mejor, peor y caso medio)
• Retomando el Ejemplo 1 (Búsqueda lineal)
• Retomando el Ejemplo 2 (Producto de 2 mayores)
2
Caso de entrada
• Un caso de entrada para un algoritmo es una instancia del

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
problema inicial.
• Un algoritmo para resolver un problema de tamaño n, puede
recibir una o más entradas, las cuales pueden definir el
número de operaciones que hará.
• Se puede determinar que tipos de operaciones utiliza y cuantas veces
las ejecuta para una entrada especifica k.
• Por ejemplo realizar una búsqueda lineal del 40 en un arreglo de 100,000
elementos (n=100,000).

Algoritmo
Entrada k
Problema de
tamaño n
3
Ejemplo 1 (Búsqueda lineal)

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
A= 49 12 56 90 2 5 11 32 22 7
func BusquedaLineal(Valor,A,n)
{
i=1; n=10
while(i<=n&&A[i]!=Valor)
{
i=i+1;
}
return i; Caso 0: Valor=11, A={49,12,56,90,2,5,11,32,22,7}, n=10
} Si el Valor=11 ⟹ 𝒔𝒆 𝒆𝒏𝒕𝒓𝒂 𝒂𝒍 𝒄𝒊𝒄𝒍𝒐 6 veces ⟹ k=6

Si el ciclo se ejecutará k veces

k sumas (una por cada iteración).
k + 2 asignaciones (las del ciclo y las realizadas fuera del ciclo).
k + 1 operaciones lógicas (la condición se debe probar k + 1 veces, la última es
para saber que el ciclo no debe volver a ejecutarse).
k + 1 comparaciones con el índice.
4
k + 1 comparaciones con elementos de A:
k + 1 accesos a elementos de A:
6k + 6 operaciones en total.
 func BusquedaLineal(Valor,A,n)
{
Operaciones a ejecutar: 6k + 6 i=1;
while(i<=n&&A[i]!=Valor)
k=Numero de veces que se entra al ciclo {

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
i=i+1;
}
return i;
}
k Instrucciones

0 6

1 12

10 66

100 606

500 3006

1000 6006
5
Operación básica
• Del ejemplo notamos que el número de veces que se

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
ejecutan algunas operaciones, para valores sucesivamente
mayores que k y/o n; se presenta un modelo de crecimiento
similar al que tiene el número total de operaciones que
ejecuta.

• Para hacer una estimación de la cantidad de tiempo que

tarda un algoritmo en ejecutarse, no es necesario contar el
número total de operaciones que realiza.

• Se puede elegir alguna, a la que se identificará como

operación básica que observe un comportamiento parecido
al del número total de operaciones realizadas y que, por lo 6
tanto, será proporcional al tiempo total de ejecución.
• En general, debe procurarse que la operación básica, en la
cual se basa el análisis, de alguna forma esté relacionada con

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
el tipo de problema que se intenta resolver, ignorando las
asignaciones de valores iniciales y las operaciones sobre
variables para control de ciclos (índices).

• Pg. la operación básica en el Algoritmo 3 (búsqueda lineal) es la

comparación entre los elementos del arreglo y el valor buscado.

func BusquedaLineal(Valor,A,n)
49 12 56 90 2 5 11 32 22 7
{
i=1; n
while(i<=n&&A[i]!=Valor)
{
i=i+1;
}
7
return i;
}
Operación básica “Compración A[i]!=Valor”
Ejemplo 2 (Producto de 2 mayores)
• El algoritmo siguiente obtiene el producto de los dos valores

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
más grandes contenidos en un arreglo A de n enteros

func Producto2Mayores(A,n)
if(A[1] > A[2])
mayor1 = A[1];
mayor2 = A[2];
else
mayor1 = A[2];
mayor2 = A[1];
i = 3;

while(i<=n)
if(A[i] > mayor1)
mayor2 = mayor1;
mayor1 = A[i];
else if (A[i] > mayor2)
mayor2 = A[i];
i = i + 1;
8
return = mayor1 * mayor2;
• En este algoritmo se realizan las siguientes operaciones:
a) Comparación con los elementos del arreglo

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
b) Asignaciones a mayor1 y mayor2
c) Asignación al índice i
d) Asignación a la función
e) Producto de los mayores
f) Incremento al índice i
g) Comparación entre el índice i y la longitud del arreglo n

• Las operaciones (c), (f) y (g) no se consideran por realizarse

entre índices, las operaciones (d) y (e) se ejecutan una sola
vez y no son proporcionales al número total de operaciones.

• Entonces, se tiene que las operaciones que se pueden

considerar para hacer el análisis son: (a) Comparación con
los elementos del arreglo y (b) las asignaciones a los
9
elementos mayores.
• (c), (f), (g), (d) y (e) pueden omitirse para el análisis
• (a) y (b) operaciones básicas del algoritmo

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
func Producto2Mayores(A,n) (d)
if(A[1] > A[2]) (a)
mayor1 = A[1]; (b)
mayor2 = A[2]; (b)
else
mayor1 = A[2]; (b)
mayor2 = A[1]; (b)
i = 3;
(c)
(g)
while(i<=n)
(a)
if(A[i] > mayor1)
mayor2 = mayor1; (b)
mayor1 = A[i]; (b)
else if (A[i] > mayor2) (a)
mayor2 = A[i]; (b)
i = i + 1; (f)
10
return = mayor1 * mayor2; (e)
Elección de la operación básica

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
• El análisis de un algoritmo se puede hacer considerando sólo
aquella operación que cumpla los siguientes criterios:

a) Debe estar relacionada con el tipo de problema que se resuelve.

b) Debe ejecutarse un número de veces cuyo modelo de crecimiento
sea similar al del número total de operaciones que efectúa el
algoritmo.

• Si ninguna de las operaciones encontradas cumple con

ambos criterios, es posible declinar por el primero. Si aun así
no es posible encontrar una operación representativa, se
debe hacer un análisis global, contando todas las
operaciones. 11
• Elección de la operación básica para algunos
problemas:

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
• Búsqueda de un elemento en un conjunto
• Comparación entre el valor y los elementos del
conjunto
• Multiplicar dos matrices
• Producto de los elementos de las matrices
• Recorrer un árbol
• Visitar un nodo
• Resolver un sistema de ecuaciones lineales
• Suma y resta de las ecuaciones
• Ordenar un conjunto de valores 12
• Comparación entre valores
Concepto de Instancia

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
• Un problema computacional consiste en una caracterización
de un conjunto de datos de entrada, junto con la
especificación de la salida deseada con base a cada entrada.

• Un problema computacional tiene una o más instancias, que

son valores particulares para los datos de entrada, sobre los
cuales se puede ejecutar el algoritmo para resolver el
problema; i.e. un caso específico de un problema.

• Ejemplo: el problema computacional de multiplicar dos

números enteros tiene, las siguientes instancias: multiplicar
345 por 4653, multiplicar 2637 por 10000, multiplicar -32341
por 12, etc. 13
Análisis Peor Caso, Mejor Caso y Caso Promedio

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

02 El rol de los algoritmos en la Computación
• El comportamiento de un algoritmo puede variar
notablemente para diferentes instancias.

• Suelen estudiarse tres casos para un mismo algoritmo: caso

mejor, caso peor, caso medio.

• Tipos de análisis:
• Peor caso: indica el mayor tiempo obtenido, teniendo en
consideración todas las entradas posibles.

• Mejor caso: indica el menor tiempo obtenido, teniendo en

consideración todas las entradas posibles.
14
• Caso medio: indica el tiempo medio obtenido, considerando todas las
entradas posibles.
Retomando el ejemplo 01: Búsqueda lineal

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

02 El rol de los algoritmos en la Computación
49 12 56 90 2 5 11 32 22 7 99 02 35 1

• Problema: Encontrar la posición de un determinado

número en un arreglo desordenado.

• ¿Cuales serían el peor caso, mejor caso y caso

promedio?

*Conclusión: Si se conociera la distribución de los datos, podemos sacar provecho

de esto, para un mejor análisis y diseño del algoritmo. Por otra parte, sino
conocemos la distribución, entonces lo mejor es considerar el peor de los casos.
15
Análisis Temporal (mejor, peor y caso medio)

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
• Con los conceptos anteriores es posible llevar a cabo el
análisis temporal de un algoritmo i.e. calcular la función
complejidad temporal ft(n).

• Considérese el Algoritmo del ejemplo 3 (Búsqueda lineal),

para hacer el análisis de su comportamiento:
• Operación básica: Comparaciones con elementos del arreglo
• Caso muestra: A = [2, 7, 4, 1, 3] y n = 5:
• Si Valor = 2, se hace una comparación, ft (5) = 1
• Si Valor = 4, se hacen tres comparaciones, ft(5) = 3
• Si Valor = 8, se hacen cinco comparaciones, y ft(5) = 5
func BusquedaLineal(Valor,A,n)
2 7 4 1 3 {
i=1;
while(i<=n&&A[i]!=Valor) 16
{
n=5 i=i+1;
}
return i;
}
• Del análisis anterior es posible descubrir que la función
complejidad temporal no es tal, en realidad es una relación,

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
ya que para un mismo tamaño de problema se obtienen
distintos valores de la función complejidad.

• Par la mayoría de los algoritmos el número de operaciones

depende, no sólo del tamaño del problema, sino también de
la instancia específica que se presente (caso de entrada).
func BusquedaLineal(Valor,A,n) 49 11 23 90 2 5 11 32 22 7
{
i=1; n

while(i<=n&&A[i]!=Valor)
{ Caso a: 1 comparación (Valor = 49)
i=i+1;
Caso b: 2 comparaciones (Valor = 11)
}
Caso c: 3 comparaciones (Valor = 23) 17
return i;
…
}
Caso x: n+1 comparaciones. (Valor = 8)
Sea:
• I(n)={I1, I2, I3, …, Ik} el conjunto de instancias del problema de

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
tamaño n.

• O(n)={O1, O2, O3, …, Ok} el conjunto formado por el número de

operaciones que un algoritmo realiza para resolver cada instancia.

• Entonces, Oj es el número de operaciones ejecutadas para resolver

la instancia Ij , para 1 ≤ j ≤ k.

• Se distinguen tres casos en el valor de la función complejidad

temporal
Peor caso ft(n) = máx ( { O1, O2, O3, …, Ok } )
Mejor caso ft(n) = min( { O1, O2, O3, …, Ok } )
18
Caso medio ft(n) = 𝒌
𝒊=𝟏 𝑶𝒊 𝑷(𝒊)

𝑷(𝒊) es la probabilidad de que ocurra la instancia Ii

• El mejor caso se presenta cuando para un caso de entrada I1
a un problema de tamaño n; el algoritmo ejecuta el mínimo

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
número posible de operaciones.

• El peor caso se presenta cuando para un caso de entrada I2 a

un problema de tamaño n; el algoritmo ejecuta el máximo
número de operaciones.

• El caso medio se consideran todos los casos posibles para

calcular el promedio de las operaciones que se hacen
tomando en cuenta la probabilidad de que ocurra cada
instancia I3.

19
Retomando el Ejemplo 1 (Búsqueda lineal)
• Algoritmo: Búsqueda lineal

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
• Problema: Búsqueda lineal de un valor en un arreglo de
tamaño n:
• Tamaño del Problema: n = número de elementos en el
arreglo.
• Operación básica: Comparación del valor con los
elementos del arreglo.

Mejor caso 1 comparación (Ejemplo Buscar: Valor = 49)

Peor caso n+1 comparaciones. (Ejemplo Buscar: Valor = 8)

49 11 23 90 2 5 11 32 22 7 func BusquedaLineal(Valor,A,n)
{
i=1;
n while(i<=n&&A[i]!=Valor)
{
i=i+1; 20
}
return i;
}
• Análisis Temporal
• Mejor caso: ocurre cuando el valor es el primer elemento

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
del arreglo.
ft(n)= 1 (1 Comparación)
• Peor caso: sucede cuando el valor no se encuentra en el
arreglo.
ft(n)=n + 1 (n+1 Comparaciónes)
• Caso medio:
ft(n)=1P(1) + 2P(2) + 3P(3) + 4P(4) +... + nP(n) + (n+1)P(n + 1)

• Donde P(i) es la probabilidad de que el valor se encuentre en la

localidad i; (1 ≤ i ≤ n) y P(n + 1) es la probabilidad de que no esté
en el arreglo y el número que lo acompaña es la cantidad de
operaciones básicas para cada uno de ellos.
49 11 23 90 2 5 11 32 22 7
21

n
• Si se supone que todos los casos son igualmente probables:

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

04 Análisis temporal
1
𝑃 𝑖 =
𝑛+1
𝑂𝑏𝑠𝑒𝑟𝑣𝑎𝑐𝑖ó𝑛
𝑛
𝑛(𝑛 + 1)
• Caso médio:
𝑖=
2
𝑖=1
Número de operaciones básicas
por caso

ft(n)=1P(1) + 2P(2) + 3P(3) + 4P(4) +... + nP(n) + (n+1)P(n + 1)

𝑓𝑡 𝑛
𝑛+1
1 1 (𝑛 + 1)(𝑛 + 2) (𝑛 + 1)(𝑛 + 2) 𝑛 + 2
= 𝑖= = =
𝑛+1 𝑛+1 2 2(𝑛 + 1) 2
𝑖=1

𝑛+2
Comparaciones si la probabilidad de todos los casos es la misma
2
22
Retomando el Ejemplo 2 (Productos Mayores)
• Algoritmo: Producto mayores.

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
• Problema: Dado un arreglo de valores, encontrar el producto de los
dos números mayores.
• Tamaño del Problema: n =número de elementos en el arreglo.
• Operación básica: Comparación con los elementos del arreglo y las
asignaciones a los elementos mayores.
func Producto2Mayores(A,n)
if(A[1] > A[2])
mayor1 = A[1];
mayor2 = A[2];
else
mayor1 = A[2];
mayor2 = A[1];
i = 3;

while(i<=n)
if(A[i] > mayor1)
mayor2 = mayor1;
mayor1 = A[i];
else if (A[i] > mayor2) 23
mayor2 = A[i];
i = i + 1;

return = mayor1 * mayor2;

func Producto2Mayores(A,n)
if(A[1] > A[2]) Primer comparación
mayor1 = A[1];

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
Asignacion
mayor2 = A[2]; Asignacion
else
mayor1 = A[2]; Asignacion
mayor2 = A[1];
Asignacion
i = 3;

while(i<=n)
if(A[i] > mayor1) n-2 Comparaciones
mayor2 = mayor1; Asignacion
mayor1 = A[i]; Asignacion
else if (A[i] > mayor2) *Si A[i]≤mayor2
mayor2 = A[i]; Asignacion
i = i + 1;

return = mayor1 * mayor2;

24
• Análisis Temporal
• Mejor caso: ocurre cuando el arreglo está ordenado
descendentemente (se realiza la primer comparación y dos

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
asignaciones, posteriormente solo se compara n-2 veces el if y n-2
veces el else if).

Comparaciones Asignaciones 99 71 23 20 18 15 11 5 3 1

1+(n-2)+(n-2) 2
n

ft(n)=1+(n-2)+(n-2)+2=3+2(n-2)=2n-1
func Producto2Mayores(A,n)
if(A[1] > A[2])
mayor1 = A[1]; ft(2)=2(2)-1=3
mayor2 = A[2];
else
mayor1 = A[2]; ft(3)=2(3)-1=5
mayor2 = A[1];
i = 3; ft(5)=2(5)-1=9
while(i<=n)
if(A[i] > mayor1) ft(10)=2(10)-1=19
mayor2 = mayor1;
mayor1 = A[i]; ft(20)=2(20)-1=39
else if (A[i] > mayor2)
mayor2 = A[i]; 25
i = i + 1;

return = mayor1 * mayor2;

 • Peor caso: el arreglo está ordenado de manera ascendente (se realiza
la primer comparación y dos asignaciones, posteriormente solo se
compara n-2 veces el if y siempre se cumplirá por lo que hará 2(n-2)

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
asignaciones.
ft(n)=1+(n-2)+2(n-2)+2=3+3(n-2)=3n-3

Comparaciones Asignaciones 9 11 23 30 38 45 61 70 80 90

1+(n-2) 2+2(n-2)
n

func Producto2Mayores(A,n)
if(A[1] > A[2])
mayor1 = A[1]; ft(2)=3(2)-3=3
mayor2 = A[2];
else
mayor1 = A[2]; ft(3)=3(3)-3=6
mayor2 = A[1];
i = 3; ft(5)=3(5)-3=12
while(i<=n)
if(A[i] > mayor1) ft(10)=3(10)-3=27
mayor2 = mayor1;
mayor1 = A[i]; ft(20)=3(20)-3=57
else if (A[i] > mayor2)
mayor2 = A[i];
i = i + 1; 26
return = mayor1 * mayor2;
 𝑈
• Caso medio: en este problema se tienen 𝑛! casos, donde U es el
𝑛
conjunto del que se extraen los elementos del arreglo.

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
𝑈
• Determina el número de posibles conjuntos de n elementos del
𝑛
conjunto U.
• 𝑛! Determina el número de maneras de acomodar los n elementos
• Para hacer el cálculo se deben de contar las operaciones que se harían en
cada caso. (Laborioso y complicado)

• El algoritmo hace siempre una comparación al inicio y dos

asignaciones y en el interior del ciclo puede ser que se realice una
comparación con dos asignaciones, dos comparaciones con una
asignación o dos comparaciones y ninguna asignación; obsérvese que
para cada A[i] puede ser cierta una de tres aseveraciones:
• A[i] > mayor1: Se hace una comparación y dos asignaciones
• A[i]≤mayor1 && A[i]>mayor2: Se hacen dos comparaciones y una
asignación
• A[i]≤mayor1 && A[i]≤mayor2 : Se hacen dos comparaciones 27
• Caso medio
• Si cada caso tiene la misma probabilidad de ocurrencia en

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
promedio se harán:
• Caso: A[i] > mayor1
1 1 1
• 1+2+ 𝑛−2 +2 𝑛−2 = (3 + 3 𝑛 − 2 ) = (3𝑛 − 3)
3 3 3
• Caso: A[i]≤mayor1 && A[i]>mayor2
1 1 1
• 1+2+2 𝑛−2 + 𝑛−2 = (3 + 3 𝑛 − 2 ) = (3𝑛 − 3)
3 3 3
• Caso: A[i]≤mayor1 && A[i]≤mayor2
1 1 1
• 1+2+ 𝑛−2 + 𝑛−2 = (3 + 2 𝑛 − 2 ) = (2𝑛 − 1)
3 3 3

ft(2)=3
• Caso medio:
ft(3)=5.6
1 1
𝑓𝑡 𝑛 = 2 3𝑛 − 3 + (2n−1) = 8n − 7 ft(5)=11
3 3
𝟖𝒏 − 𝟕 ft(10)=24.3
𝒇𝒕 𝒏 = 𝒐𝒑𝒆𝒓𝒂𝒄𝒊𝒐𝒏𝒆𝒔 𝒃á𝒔𝒊𝒄𝒂𝒔 28
𝟑 ft(20)=51
• Es importante mencionar que no todos los algoritmos
presentan casos, y resulta interesante tener una

Análisis de algoritmos

Prof. Edgardo Adrián Franco Martínez

Clase 06 y 07: Análisis temporal (Ejercicios)
herramienta para detectar cuándo se particionará el
análisis en casos; por el momento la única ayuda con la
que se cuenta es la intuición y preguntarse: ¿Se puede
resolver el problema de manera trivial para alguna
instancia específica?. Si la respuesta es afirmativa el
algoritmo tendrá casos, por lo que el problema de
detección se reduce a contestar esta “simple” pregunta.

29