Unidad 2 – Análisis de Algoritmos

Introducción
Al momento de resolver un problema, frecuentemente se debe optar entre varios algoritmos. Qué
criterios se aplican para saber cuál elegir?. Existen dos enfoques para realizar dicha elección:

(1)Que el algoritmo sea fácil de entender, codificar y modificar.

(2)Que sea lo más eficiente posible en términos de tiempo de ejecución.

En general, cuando un programa será usado muy pocas veces, la mayor parte de su costo viene
dado por el costo de la tarea de programación, por lo que resulta preferible la opción (1).

En cambio, cuando el programa será utilizado con mucha frecuencia (la gran mayoría de los
casos), la mayor parte del costo la determina el propio programa al ejecutarse; parece entonces
más razonable optar por la opción (2). Esto quiere decir: es preferible destinar más tiempo a la
etapa de programación, para construir un algoritmo que a lo mejor es más complejo pero que sea
más eficiente en términos de tiempo de ejecución, a escribir un algoritmo sencillo, pero que a largo
plazo conduzca a un uso ineficiente del tiempo.

Como se señaló anteriormente, es más frecuente ésta forma de trabajo. En éste capítulo se
estudiarán formas de poder decidir si un algoritmo es mejor (más eficiente) que otro.

Tiempo de ejecución de un programa

Existen diversos factores que inciden en el tiempo de ejecución de un programa, los más
importantes son:

(1) La calidad del código objeto generado por el compilador.

(2) La velocidad con la cual la máquina ejecuta las instrucciones de bajo nivel.
(3) Los datos de entrada del programa.
(4) La complejidad de tiempo que tenga el algoritmo base.

Los primeros dos factores no dependen directamente del programador, ya que el primero depende
del compilador que se elija (puede haber más de uno, inclusive para el mismo lenguaje!). El
segundo es mas difícil de medir aún, debido a que información como ser en qué máquina será
ejecutado el programa que se está construyendo, no siempre se tiene disponible.

Si bien el tercer factor aparece como externo al algoritmo, en realidad su eficiencia está
estrechamente relacionada con aspectos como: (a) cuántos datos recibe el algoritmo, y (b) cómo
éstos vienen organizados. Para ejemplificar el significado de esto último, considérese el problema
de buscar un elemento en una secuencia: no es lo mismo buscar un elemento en una secuencia de
10 elementos que buscar en una secuencia de 10000. Además no es lo mismo buscar un elemento
que se encuentra aproximadamente a mitad de camino en la secuencia, que buscar un elemento
que se encuentra al final de la secuencia.

Por lo visto en (a) queda claro que el tiempo de ejecución depende de la cantidad de datos de
entrada, y por lo visto en (b) cada juego de datos de entrada, se puede clasificar en casos: el caso
en que el elemento a buscar se encuentra al final, se podría considerar como el peor caso, en
cambio el otro se podría considerar como el caso promedio. El caso promedio es más difícil de
estudiar, ya que en el influyen factores probabilísticos.
 Análisis de algoritmos

Por último, el factor (4) es de los que el programador puede manejar y más influye en la eficiencia
de un algoritmo. En general, la complejidad de un algoritmo, es directamente proporcional a su
eficiencia. Algoritmos sencillos, que no exploten las propiedades del problema que se esté
resolviendo, seguramente no harán un manejo “inteligente” de los datos, pasando por alto
oportunidades de mejorar el rendimiento.

Por último, es de esperarse que los algoritmos tengan mejor rendimiento en el denominado caso
promedio que en el peor caso. Por ejemplo, en un problema de búsqueda, si un algoritmo apenas
encuentra el elemento, no prosigue con la recorrida de la secuencia, será mejor en el caso
promedio que uno que no lo haga (en cuyo caso los casos promedio y peor coinciden, es decir se
debe recorrer la secuencia por entero).

En las siguientes secciones se tratarán con mayor detalle los dos últimos puntos mencionados, ya
que son estos los que pueden tenerse en cuenta al diseñar un algoritmo.

Medición de la complejidad de un algoritmo

Si bien anteriormente se habló del tiempo de ejecución de un algoritmo, esta no resulta una buena
medida a la hora de observar cuán eficiente es el mismo ya que el tiempo de ejecución dependerá
de la computadora en la que se corra el programa. Por otra parte lo que interesa es diseñar
algoritmos eficientes, por lo cual se debe encontrar una forma de “medir” su costo antes de
implementarlo en un lenguaje de programación (y por lo tanto, antes de correrlo). Sin embargo todo
algoritmo tiene de por sí una complejidad implícita que tiene que ver con el método que aplica.

Operación básica
Todo algoritmo debe resolver un sólo problema. De este modo siempre será posible encontrar una
unidad (operación, instrucción, etc.) que caracteriza el método usado por el algoritmo y que resulta
esencial para resolver el problema. Esta unidad es llamada operación básica del algoritmo.

Ejemplo
Buscar el máximo en un array de n enteros.

int Maximo(arreglo A){

int i,max;

max=A[0];
for(i=1;i<n;i++)
if(A[i]>max)
max=A[i];
return max;
}

Este algoritmo se basa en la comparación de 2 elementos del array (en realidad de max con cada
elemento del array). Para encontrar el máximo se debe recorrer todo el array, pues el valor máximo
puede encontrarse en cualquier lugar. Por lo tanto, la operación básica de este algoritmo es la
comparación A[i]>max.

El resto de las operaciones e instrucciones que contiene un algoritmo suelen ser secundarias
respecto a aquella, aportando el marco necesario para que la operación básica se realice todas las
veces que sea necesario.
Análisis de algoritmos 3

Por lo tanto, una buena medida de la eficiencia de un algoritmo (o sea de su complejidad) es la

cantidad de veces que se ejecuta su operación básica. Un punto importante a la hora de
determinar dicha operación básica es tener presente que la misma debe ser tal que se ejecute
siempre, independientemente de los datos de entrada concretos que se le proporcione al algoritmo.

Por ejemplo, haber elegido como operación básica la sentencia max=A[i] no es un buen reflejo
de la complejidad del mismo porque podría ejecutarse muchas veces para un arreglo concreto y
pocas veces para otro arreglo concreto (dependiendo de cómo vengan ordenados los elementos
en cada uno de los dos arreglos). La comparación A[i]>max, en cambio, se ejecuta la misma
cantidad de veces independientemente del arreglo en concreto que le hayamos proporcionado
como parámetro.

Tamaño de la entrada
La cantidad de veces que se ejecuta la operación básica de un algoritmo depende, en la mayor
parte de los casos, del volumen de la información a procesar, o sea de los datos de entrada del
algoritmo. Este volumen de información se conoce como tamaño de la entrada. El tamaño de la
entrada es un número, estrechamente vinculado con los datos de entrada, que de alguna manera
indica el volumen de información que será procesada.

En el ejemplo del máximo del array, el tamaño de la entrada es la cantidad de elementos del array,
que es n.

En general, la cantidad de veces que se ejecuta la operación básica se puede ver como una
función del tamaño de la entrada.

T: N → N

La función T indica para cada valor del tamaño de la entrada (que por lo tanto es un número
natural), cuantas veces se ejecuta la operación básica del algoritmo. En el ejemplo anterior, puede
verse que la comparación A[i]>max se realiza n-1 veces, por lo tanto:

T(n) = n-1

Veamos ahora otro ejemplo en donde el tamaño de una entrada no siempre se asocia a la cantidad
de elementos de la entrada.

Ejemplo
Un procedimiento que imprima un rectángulo de n ocurrencias de un mismo carácter.

void Cuadricula (char c, int n){

int i,j;
for (i=0;i<n;i++)
for (j=0;j<n/2;j++)
printf(“%c”,c);
}

En este caso la entrada consiste solamente en dos elementos: el carácter a ser procesado y la
cantidad de veces que será procesado. Sin embargo, el tamaño de la entrada en este caso no es
2. El mismo viene dado por el parámetro n y el costo del algoritmo es T(n) = n * n / 2. Es decir, la
cantidad de veces que se ejecuta la operación básica (que en este caso es printf(“%c”,c)) es
n * n / 2 veces.
 Análisis de algoritmos

En este ejemplo, el tamaño de la entrada no resultó una medida de la cantidad de elementos que
poseía la entrada (que siempre es 2; un carácter y un número) sino de la cantidad de veces que los
datos tuvieron que ser procesados (n veces). A la hora de determinar cuál es el tamaño de la
entrada para un algoritmo cualquiera, es importante ser cuidadoso a la hora de determinar de qué
manera los datos de entrada influyen en la cantidad de veces que se ejecutará la operación básica.
Esto evitará que hagamos un cálculo errado del tamaño de la entrada que posteriormente no
provea ser un buen indicador de la eficiencia real del algoritmo.

Ejemplo
Búsqueda de un elemento en un array de enteros.

boolean Pertenece(arreglo A,int x){

int i;
boolean esta;

esta=false;
i=0;
do {
if (x==A[i])
esta = true;
else
i=i+1;
} while (i<n && !esta);
return esta;
}

La entrada en este caso está conformada por el arreglo A y por el entero x. El tamaño de la entrada
en este caso sí se corresponde con la cantidad de elementos del arreglo (n). La operación básica
es la comparación por igualdad (x==A[i]).

En la determinación de la operación básica y del tamaño de la entrada debe tenerse en cuenta

también si los tipos considerados son básicos y sus operaciones pueden considerarse indivisibles.
Considérese una variante del ejemplo anterior, en la cual los elementos del arreglo fueran strings.
Si además no consideramos a la comparación entre strings como una operación atómica, sino
como un algoritmo que realiza comparaciones carácter a carácter, ésta sería la operación básica y
el tamaño de la entrada deberíamos medirlo en caracteres: m*n, donde m es el tamaño de los
strings y n es la cantidad de elementos del arreglo.

Con relación a la complejidad del algoritmo, para este ejemplo puede verse que no es posible
determinar una única expresión para T(n), (siendo n el tamaño de la entrada).

Podría suceder que el algoritmo recibiera un arreglo A y un valor x tales que el valor buscado se
encuentre en el primer lugar del arreglo. En ese caso la cantidad de comparaciones por igualdad
que se realizarían sería:

T(n) = 1 comparación.

Por otro lado si el valor buscado está en el último lugar o no está en el arreglo, puede verse que se
realizan:

T(n) = n comparaciones.

Esto es lo peor que podría suceder para el algoritmo dado, nunca realizará más comparaciones.
Se puede notar entonces que un mismo algoritmo tiene un desempeño completamente distinto
según la entrada. Cada ejecución del algoritmo, dependiendo de la entrada, tendrá distinto costo.
Análisis de algoritmos 5

Peor caso
A aquellas entradas que producen el mayor costo para un algoritmo, se les denomina peor caso del
algoritmo. En tal situación, nos concentraremos solamente en aquella función T(n) que
corresponda a la mayor cantidad de veces que se ejecuta la operación básica. Se le suele llamar
W(n) a dicha función T(n).

En el ejemplo anterior el peor caso corresponde al caso en que el elemento a buscar esté en el
último lugar o no esté en el arreglo. Notar que el peor caso de un algoritmo debe determinarse
luego de haber establecido el tamaño de la entrada y la operación básica del algoritmo.

A su vez el costo de un algoritmo en su peor caso, representa una cota superior para el costo de
cualquier otra entrada. Por tal razón y teniendo en cuenta que generalmente no se pueden
considerar todos los casos (de posibles entradas), en este curso tomaremos como criterio, medir la
complejidad de los algoritmos en su peor caso. Si logramos un algoritmo lo más eficiente posible
en su peor caso, lo será también en todos los demás casos.

Hay situaciones en las cuales hay un único caso posible para el algoritmo en cuestión. En tal
situación, dicho caso único es, naturalmente, el peor caso posible. Por ejemplo, para el algoritmo
que calcula el máximo de un array hay un único caso posible, y es que se deben recorrer todas las
celdas del arreglo, independientemente del arreglo concreto que se tenga. Para el algoritmo que
imprime un carácter n veces también hay un único caso posible, y es que se deben imprimir las n
ocurrencias del carácter en cuestión. En ambos ejemplos el peor caso se corresponde con el único
caso posible para el algoritmo.

Ordenes
Como en general es muy complicado calcular exactamente la cantidad de operaciones básicas que
realiza un cierto algoritmo, se presentará un concepto igual de útil pero más simple, el concepto de
orden.

Definición
Se dice que T(n) es O(f(n)) (T(n) tiene orden f(n)) si existen constantes positivas c y n0 tales que:

T(n) ≤ c.f(n) cuando n≥n0.

Esto quiere decir que T(n) “nunca va a sobrepasar” a f(n) a partir de un n0, donde f(n) es en general
una función mas sencilla que la propia T. Entonces f(n) es una cota para T(n).

El orden de un algoritmo es una medida indirecta de la eficiencia del mismo en relación a otros
algoritmos. Muchas veces no necesitamos (o directamente es muy trabajoso) conocer exactamente
la cantidad de veces que se ejecuta la operación básica en el peor caso. Nos basta con tener una
idea intuitiva del grado de eficiencia del algoritmo considerado en relación con otros algoritmos.
Esta idea intuitiva es la que se asocia a la noción de orden.

Propiedad

La definición de Orden muchas veces es difícil de manipular directamente. Para algunas funciones
T: N → N es difícil aplicar directamente la definición anterior a la hora de determinar el orden del
algoritmo. Dado que la mayoría de las funciones T: N → N que veremos en este curso son
polinómicas, enunciaremos la siguiente propiedad que nos será de utilidad a la hora de determinar
el orden de un algoritmo:
 Análisis de algoritmos

2 m m
Si T(n) = a0 + a1n + a2n + ... + amn entonces T(n) es O(n ).

Es decir, que si T(n) es un polinomio de grado m, entonces tiene orden m.

Ejemplo
Considere la operación Maximo vista anteriormente, se tiene que T(n)=n-1.
Dicha función tiene O(n), dado que se trata de un polinomio de primer grado. Por lo tanto
concluimos que el algoritmo en cuestión es O(n).

Ejemplo
Considere la operación Cuadricula vista anteriormente, se tiene que T(n)= n * n / 2.
2 2
Dicha función (que puede expresarse T(n)= n / 2) tiene O(n ), dado que se trata de un
2
polinomio de segundo grado. Por lo tanto concluimos que el algoritmo en cuestión es O(n ).

Ejemplo

Considere la operación Pertenece vista anteriormente, se tiene que W(n)= n (nótese que
a diferencia de los dos ejemplos previos, aquí debemos considerar explìcitamente el peor
caso). Dicha función tiene O(n), dado que se trata de un polinomio de primer grado. Por lo
tanto concluimos que el algoritmo en cuestión es O(n).

Los órdenes de magnitud son una medida conceptual del nivel de eficiencia de un algoritmo. Ante
dos algoritmos que resuelvan un mismo problema, optaremos por aquel cuyo orden de magnitud
sea menor, ya que claramente será más eficiente que el otro. No obstante, en el caso en que los
dos algortimos tuvieran el mismo orden de magnitud, no puede afirmarse que son igualmente
eficientes, ya que ello depende de la cantidad concreta de veces que se ejecute la operación
básica en cada uno de ellos. Será necesario pues, hacer un estudio más detallado de ambos
algoritmos antes de determinar si uno es más eficiente que el otro o no. Por ejemplo, si el primer
algoritmo es tal que T(n) = n+1 y el segundo algoritmo es tal que T(n) = 2n se cumple que ambos
son O(n), pero el primero de ellos ejecuta una menor cantidad de veces su operación básica, por lo
que lo elegiremos en lugar del segundo.

Hasta el momento nos hemos concentrado fundamentalmente en analizar algoritmos sencillos.

Vamos a finalizar enunciando dos propiedades que son de utilidad a la hora de calcular el orden de
magnitud de algoritmos más complejos que a su vez requieren la ayuda de algoritmos auxiliares..

Propiedad
Sean P1 y P2 dos fragmentos de programa tales que P1 es O(f(n)) y P2 es O(g(n)). Entonces, el
orden de magnitud de algoritmo P1 seguido por P2 es O (max(f(n),g(n)).

Ejemplo
void MinMax (arreglo arre, int &min, int &max)
{
min=Minimo(arre);
max=Maximo(arre);
}

Como se vio anteriormente, Maximo es O(n) y claramente también Minimo es O(n),

entonces aplicando la propiedad anterior, el procedimiento MinMax es O(n).
Análisis de algoritmos 7

Propiedad
Sean P1 y P2 dos fragmentos de programa tales que P1 es O(f(n)) y P2 es O(g(n)). Entonces, el
orden de magnitud de algoritmo P1 anidado en una iteración del algoritmo P2 es O (f(n)*g(n)).

Ejemplo
int CuantosExisten (arreglo arre, int m)
{
int i, cant=0;
for (i=0; i<m; i++)
if (Pertenece(arre,i))
cant++;
}

La operación básica de esta función es la condición del if que determina el criterio para
contar o no al valor en cuestión. Dicha operación se ejecuta m veces. A simple vista,
diríamos que la función CuantosExisten es O(m). Sin embargo, su operación básica
consiste en una llamada a Pertenece, que a su vez es O(n). Por tanto, aplicando la
propiedad anterior, tenemos que esta función es O(m*n).

Casos de Estudio
Árboles binarios de búsqueda:

Una de las mayores ventajas de los árboles binarios de búsqueda, desde el punto de vista de la
complejidad de los algoritmos es que, en general, se recorren menos elementos que en una
estructura lineal (como podría ser una lista o un arreglo). El caso ideal es cuando el árbol es
completo en todos sus niveles, es decir, totalmente balanceado (no le faltan nodos en ningún
nivel). De esta forma, puede verse que la altura del árbol es mínima (respecto a otros árboles con
la misma cantidad de elementos).

Puede demostrarse que la altura de un árbol binario completo es log n, siendo n la cantidad de
nodos. Se cumple, en general que log n << n. Teniendo en cuenta esto, los algoritmos sobre ABB
que realizan operaciones de búsqueda aprovechando la propiedad del árbol binario de búsqueda
(por ejemplo insertar o pertenece) son O(log n). En efecto, en dichos algoritmos sólo se recorren
los nodos que están en un único camino de la raíz a una hoja, por lo tanto la cantidad de nodos
inspeccionados es igual a la altura del árbol.

Lo anterior es cierto solamente cuando el árbol es completo en todos sus niveles. Nótese que si se
llena un árbol binario inicialmente vacío con elementos que vienen dados en orden creciente, el
árbol queda con forma de “lista”, todos sus nodos siempre se insertan a la derecha. En este caso el
árbol se asemeja a una lista y cualquier operación será O(n).

Algoritmo de DFS para Grafos:

Es posible demostrar (pero no lo vamos a hacer) que el orden del algoritmo DFS es
O (max {|G(V)|, |G(A)|}) suponiendo un grafo conexo. Esto es, el máximo entre la cantidad de
vértices y la cantidad de aristas del grafo. Esto bajo la hipótesis de que el procesamiento que le
queramos dar al vértice actual es de O(1). En otro caso, se debe multiplicarle al orden de DFS el
orden de ejecución de dicho procesamiento.

DFS es un caso particular de backtracking. Los algoritmos de backtracking consisten en la

búsqueda exhaustiva de soluciones a problemas que pueden modelarse en forma arborescente, y
n
en muchos casos, mediante grafos. Usualmente tienen orden de ejecución exponencial O(a ) que
 Análisis de algoritmos

es mucho mayor que todos los órdenes estudiados anteriormente. Sin embargo, DFS tiene un
orden de ejecución notoriamente menor que muchos otros algoritmos de backtracking debido a
que, por su naturaleza, aplica una estrategia que descarta muchas recorridas, reduciendo
notoriamente su tiempo de ejecución.