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.