2.3 Anlisis matemtico de algoritmos no recursivos En esta seccin, se aplica sistemticamente el marco general descrito en la Seccin 2,1 para el
anlisis de la eficiencia del tiempo de los algoritmos no recursivos.
Comencemos con un ejemplo muy sencillo que muestra todas las etapas principales tpicamente
tomadas en el anlisis de este tipo de algoritmos.
Ejemplo 1 Considrese el problema de encontrar el valor del elemento ms grande en una lista de
n nmeros. Por simplicidad, se supone que la lista se implementa como una matriz. La siguiente es
pseudocdigo de un algoritmo estndar para resolver el problema.
ALGORITMO maxelement (A [0..n - 1])
// Determina el valor del elemento ms grande en una matriz dada
// Entrada: Una matriz A [0..n - 1] de los nmeros reales
// Salida: El valor del elemento ms grande en A
maxval A [0]
para i 1 hasta n - 1 hacer
si A [i]> maxval
maxval A [i]
retorno maxval
La medida obvia del tamao de una entrada aqu es el nmero de elementos en la matriz, es decir,
n. Las operaciones que se van a ejecutar con mayor frecuencia se encuentran en el
el algoritmo de bucle. Hay dos operaciones en el cuerpo del bucle: la comparacin
A [i]> maxval y la asignacin Maxval A [i] .Qu de estas dos operaciones
debemos considerar bsica? Puesto que la comparacin se ejecuta en cada repeticin
del bucle y la asignacin no es, deberamos considerar la comparacin de ser
funcionamiento bsico del algoritmo. Tenga en cuenta que el nmero de comparaciones ser la
igual para todas las matrices de tamao n; Por lo tanto, en trminos de esta mtrica, no hay
necesidad de distinguir entre los peores, promedio y mejor de los casos aqu.
Denotemos C (n) el nmero de veces que se ejecuta esta comparacin y tratamos
encontrar una frmula que expresa como una funcin del tamao de n. El algoritmo hace una
comparacin en cada ejecucin del bucle, que se repite para cada valor de
la variable del bucle i dentro de los lmites 1 y n - 1, ambos inclusive. Por lo tanto, se obtiene la
siguiente suma de C (n):
Esta es una suma fcil de calcular, ya que no es ms que 1 repite n - 1
veces. Por lo tanto,
Aqu es un plan general a seguir en el anlisis de algoritmos no recursivos.
Plan General de Anlisis de la Eficiencia Tiempo de no recursivas Algoritmos
1. Decidir sobre un parmetro (o parmetros) que indica el tamao de una entrada.
2. Identificar el funcionamiento bsico del algoritmo. (Por regla general, se encuentra en lo ms
profundo.)
3. Compruebe si el nmero de veces que se ejecuta la operacin bsica depende slo en el tamao
de una entrada. Si tambin depende de alguna propiedad adicional, el peor de los casos, la media
de los casos, y, en caso necesario, la eficiencia, mejor de los casos tienen que ser investigado por
separado.
4. Establecer una suma que expresa el nmero de tiempos de operacin bsica del algoritmo es
ejecutado.
5. Uso de frmulas estndar y reglas de manipulacin de suma, o bien encontrar un formula de
forma cerrada para el recuento o, por lo menos, establecer su orden de crecimiento.
Antes de continuar con ms ejemplos, es posible que desee revisar el Apndice A, que contiene una
lista de frmulas de adicin y reglas que son a menudo tiles en el anlisis de algoritmos. En
particular, se utiliza con frecuencia en especial dos reglas bsicas de la manipulacin suma
y dos frmulas de adicin
La primera es un caso especial del ejemplo 1
Ejemplo 2 Considere el problema singularidad elemento: comprobar si todos los elementos de un
array dado de n elementos son distintos. Este problema puede ser resuelto por el siguiente
algoritmo sencillo.
ALGORITHM UniqueElements(A[0..n 1])
// Determina si todos los elementos de un array dado son distintos
// Entrada: Una matriz A [0..n - 1]
// Salida: Devuelve "true" si todos los elementos de A son distintos
// Y "falso" de otro modo
for i 0 to n 2 do
for j i + 1 to n 1 do
if A[i]= A[j ] return false
return true
La medida natural del tamao de la entrada aqu est de nuevo n, el nmero de elementos en la
matriz. Puesto que el bucle ms interior contiene una sola operacin (la comparacin de dos
elementos), debemos considerar como operacin bsica del algoritmo. Nota, sin embargo, que el
nmero de comparaciones de elementos no slo depende de n, sino tambin de si hay elementos
iguales en la matriz y, si existen, que array posiciones que ocupan. Nos limitaremos nuestra
investigacin al nico peor de los casos. Por definicin, el peor caso de entrada es una matriz para
la cual el nmero de elemento comparaciones Cpeor (n) es el ms grande entre todas las matrices
de tamao n. Una inspeccin del bucle ms interno revela que hay dos tipos de peor caso entradas
de entradas para los que el algoritmo no salir del bucle prematuramente: arrays sin igual elementos
y matrices en las que los dos ltimos elementos son el nico par de igual elementos. Para tales
entradas, una comparacin se hace para cada repeticin del bucle ms interior, es decir, para cada
valor de la variable de bucle j entre sus lmites i + 1y n - 1; Esto se repite para cada valor del lazo
externo, es decir, para cada valor dela variable del bucle i entre sus lmites 0 y n - 2. En consecuencia,
obtenemos
Fundamentos del Anlisis del algoritmo Eficiencia
donde la ltima igualdad se obtiene aplicando la frmula de sumatorias (S2). Nota que este
resultado era perfectamente previsible: en el peor de los casos, el algoritmo necesita comparar
todos n (n - 1) / 2 pares distintos de sus n elementos.
Ejemplo 3 dado dos n n matrices A y B, busca la eficiencia del tiempo del algoritmo basado en la
definicin para el clculo de su producto C = AB. Por definicin, C es una matriz n n cuyos
elementos se calcula como el escalar (punto) los productos de las filas de la matriz A y las columnas
de la matriz B:
donde C [i, j] = A [i, 0] B [0, j] +. . . + A [i, k] B [k, j] +. . . + A [i, n - 1] B [n - 1, j] para cada par de ndices
0 i, j n - 1.
ALGORITHM MatrixMultiplication(A[0..n 1, 0..n 1], B[0..n 1, 0..n 1])
// Multiplica dos matrices cuadradas de orden n por el algoritmo basado en la definicin
// Entrada: Dos n n matrices A y B
// Salida: Matrix C = AB
for i 0 to n 1 do
for j 0 to n 1 do
C[i, j ]0.0
for k0 to n 1 do
C[i, j ]C[i, j ]+ A[i, k] B[k, j]
return C
Medimos el tamao de una entrada por orden de la matriz n. Hay aritmtica de dos operaciones
en el bucle ms interior aqu-multiplicacin y adicin que, en principio, puede competir para ser
designado como el funcionamiento bsico del algoritmo. En realidad, no tenemos que elegir entre
ellos, porque en cada repeticin del bucle ms interior de cada uno de los dos se ejecuta
exactamente una vez. As contando un solo contamos automticamente el otro. Sin embargo,
siguiendo una tradicin bien establecida, que considerar la multiplicacin como la operacin
bsica (ver seccin 2.1). Dejmonos establecimos una suma para el nmero total de
multiplicaciones hombre) ejecutados por el algoritmo. (Desde esto recuento depende slo del
tamao de las matrices de entrada, no tenemos para investigar el peor de los casos, la eficiencia
promedio de los casos, y el mejor de los casos por separado). Obviamente, no es slo una
multiplicacin ejecutado en cada repeticin del bucle ms interior del algoritmo, que se rige por la
variable k van desde el lmite inferior 0 a la parte superior unida n - 1. Por lo tanto, el nmero de
multiplicaciones realizado para cada par de valores especficos de las variables i y j es
y el nmero total de multiplicaciones M (n) se expresa por la siguiente triple de la suma:
Ahora, podemos calcular esta suma mediante el uso de la frmula (S1) y la regla (R1) da arriba. A
partir de la suma ms interna n-1 k = 0 1, que es igual a n (por qu?), obtenemos
Este ejemplo es bastante simple para que pudiramos obtener este resultado sin todas las
maquinaciones de suma. Cmo? El algoritmo calcula elementos n2 de la matriz del producto.
Cada uno de los elementos del producto se calcula como el escalar (punto) producto de una fila n-
elemento de la primera matriz y una columna n-elemento de la segunda matriz, que tiene n
multiplicaciones. Por lo tanto, el nmero total de multiplicaciones es n. = n2 * n3. (Este es el tipo
de razonamiento que nos esperaba a que emplea al responder a esta pregunta en el problema 2
de los Ejercicios 2.1.) Si ahora queremos estimar el tiempo de ejecucin del algoritmo en un
particular, mquina, podemos hacerlo por el producto
donde cm es el tiempo de una multiplicacin en la mquina en question. We hara obtener una
estimacin ms precisa si tomamos en cuenta el tiempo dedicado a las adiciones, tambin:
donde ca es el momento de una adicin. Tenga en cuenta que las estimaciones difieren slo por su
constante multiplicativa y no por su orden de crecimiento. Usted no debera tener la impresin
errnea de que el plan esbozado anteriormente siempre tiene xito en el anlisis de un algoritmo
no recursivo. Un cambio irregular en un variable de bucle, una suma demasiado complicado de
analizar, y de las dificultades intrnsecas a el anlisis del caso promedio, son slo algunos de los
obstculos que pueden resultar insuperables. Estas advertencias, no obstante, el plan funciona
para muchos sencilla algoritmos no recursivos, como se ver a lo largo de los siguientes captulos
del libro. Como ltimo ejemplo, consideremos un algoritmo en el que la variable del bucle los
cambios en una manera diferente de la de los ejemplos anteriores.
Ejemplo 4 El siguiente algoritmo encuentra el nmero de dgitos binarios en la representacin binaria de un entero decimal positivo. ALGORITHM Binary(n)
// Entrada: Un positivo entero decimal n
// Salida: El nmero de dgitos binarios en la representacin binaria de
count 1
while n > 1 do
count count + 1
n_n/2_
return count
En primer lugar, observe que la operacin ms frecuentemente ejecutadas aqu no est dentro del
while sino ms bien la comparacin n> 1 que determina si el bucle de cuerpo va a ser ejecutado.
Dado que el nmero de veces que se ejecuta la comparaciones mayor que el nmero de
repeticiones del cuerpo del bucle por exactamente 1, la eleccin no es tan importante. Una
caracterstica ms importante de este ejemplo es el hecho de que la variable de bucle lleva en slo
unos pocos valores entre los lmites inferior y superior; Por lo tanto, tener que utilizar una forma
alternativa de calcular el nmero de veces que el bucle es ejecutado. Dado que el valor de n es
aproximadamente reduce a la mitad en cada repeticin del bucle, la respuesta debe ser
aproximadamente log2 n. La frmula exacta para el nmero de veces la comparacin > 1 se
ejecutar es en realidad? log2 n? + 1-el nmero de bits en la representacin binaria de n segn la
frmula (2.1). Tambin podramos obtener esta respuesta mediante la aplicacin de la tcnica de
anlisis basado en relaciones de recurrencia; nosotros hablar de esta tcnica en la siguiente
seccin porque es ms pertinente para el anlisis de algoritmos recursivos.