Algoritmos y Crecimiento de las Funciones.
1 Algoritmos.
Cuando ejecutamos un programa sobre una gran cantidad de datos, debemos estar seguros
que el programa termina en plazo razonable. Esto es independiente del lenguaje de programación utilizado, compilador/interprete/maquina_virtual utilizada y la metodología utilizada
( si es procedimental u orientada a objetos).
¿Que es un Algoritmo? A esta altura sabemos por intuición que es, pero hay que decirlo.
Algoritmo: Un algoritmo es aquel procedimiento computacional bien definido, que toma
o setea valores como entrada y produce un valor como salida. De este modo es una secuencia de pasos computacionales que transforman una entrada en una salida. También
se puede ver como una herramienta para resolver un problema computacional bien
definido. La declaración del problema especifíca, en general, los términos que se desean
para la relación Entrada/salida. Los algoritmos describen el procedimiento computacional
específico para lograr que se relacionen la Entrada con la Salida.
El algoritmo tiene propiedades que lo hacen ver mejor/peor según el problema y circunstancia.
¿Que es un Problema? Es la definición de un objetivo de llevar una circunstancia actual
a otra. Por ejemplo: La ordenación es un problema si se puede definir formalmente el
objetivo de llevar la entrada a una salida deseada.
Definición formal del problema de ordenación:
Entrada: Una secuencia de n números (a1, a2, …, an).
Salida: Una permutación (reordenación) (a
0
1
, a0
2
, …, a0
n
) de la secuencia de entrada.
Tal que: a
0
1 ≤ a
0
2 ≤ …, ≤ a
0
n
.
Si el input es (31; 41; 59; 26; 41; 58), el algoritmo retorna (26; 31; 41; 41; 58; 59).
Esa entrada en especial, para el problema, se llama instancia del problema de ordenación.
Se llama instancia de un problema a una entrada particular del problema que satisface
cualquier obligación impuesta en la declaración del problema.
Un algoritmo es correcto, si para toda instancia del problema, termina con la respuesta
correcta como salida. El algoritmo correcto resuelve el problema computacional.
Un algoritmo es incorrecto, si no termina nunca para algunas instancias de entrada,
o si terminar con un valor incorrecto como respuesta para algunas instancias de entrada.
Contrario a lo que usted espera, un algoritmo incorrecto puede ser util, si controlamos su taza de error.
Suponga que tiene la computadora con velocidad infinita y la memoria infinita.
¿Para que perder el tiempo leyendo esto?
Esto le sirve para demostrar que su método de solución termina y que además el resultado
es correcto. Si posee la computadora con rapidez infinita cualquier método correcto basta.
Probablemente quiera estar en los margenes de «las buenas practicas de la ingeniería del
software» (diseñado, implementado y documentado, y cobrado por el trabajo realizado), pero
implementando el método más sencillo casi siempre. Las computadoras pueden ser rápidas,
pero no infinitamente rápidas. La memoria puede ser mucha, pero no infinita. El tiempo de
computo es por lo tanto una limitación de la fuente, y ocupa espacio en memoria. Programe
sabiamente para que los algoritmos sean eficientes en términos de tiempo y espacio.
4
2 Análisis de los Algoritmos.
Sabemos que nuestro algoritmo funciona. El Análisis de los Algoritmos es determinar los
recursos que consume.
Los recursos que consume los algoritmos son:
• Tiempo = Tiempo usado para resolver el problema.
• Espacio = Cantidad de memoria utilizada para resolver el problema.
El tiempo y el espacio están en función del tamaño del problema, llamado también tamaño
de entrada . El Análisis de los Algoritmos se concentra en el tiempo.
El tamaño de entrada(..es..) depende del tipo de problema que se estudie:
• Es el numero de elementos de entrada (por ejemplo en la ordenación).
• Es la tupla de variables, donde la cantidad de cálculos a realizar esta en función del
valor de cada variable.
¿Cómo es el análisis del tiempo?
Análisis de los Algoritmos tiene que ser independiente de la tecnología usada. A lo que me
refiero es que no vamos a decir: Sobre un pentium M, con X código en C, tardamos 15 minutos
en clasificar un archivo de 1 MegaByte sobre una Tabla Hash de 65mil entradas.
Ser independiente de la tecnología usada porque:
• Las instrucciones por segundo de los microprocesadores son diferentes. Por
eso no se puede medir en función con el tiempo que tarda. La medición Wall time, marca
el tiempo transcurrido en el reloj de pared y se emplea solo para testing de requisitos
no funcionales, etc.
• Los microprocesadores tienen sets de instrucciones diferentes, arquitecturas
diferentes, compiladores diferentes. Con esto descartamos la cantidad de instrucciones realizadas en asembler.
Se usa un análisis matemático asintótico sobre el crecimiento del algoritmo.
El running time de un algoritmo es el numero de operaciones primitivas o pasos
que se van a ejecutar. El running time depende de la magnitud del tamaño de la entrada.
Este análisis nos permite predecir cuanto tardara nuestro algoritmo para un tamaño de entrada mayor, al conocer el factor de crecimiento del running time.
De esta forma podemos comparar la relativa performance de algoritmos alternativos, en
caso de tenerlos y poder elegir en base a un poderoso fundamento, porque el running time
depende de la eficiencia del algoritmo.
No se puede mejorar el running time de un algoritmo en la fase de implementación, sin
cambiar al algoritmo. La filosofía de la materia dice: Mejore el algoritmo, no el código.
5
3 Crecimiento.
Consta de dos partes: Calculo del running time del algoritmo y establecer un limite para
poder usarlo para la predicción factor de crecimiento del tiempo del algoritmo.
El calculo del running time es el conteo de pasos elementales, tomando cada paso como de
tiempo constante y que vale el mismo tiempo cada paso. En tras palabras, podemos representar la cantidad de pasos que realiza un algoritmo en función del tamaño de la entrada. En la
literatura es la función T(N).
3.1 Notación Asintótica
El calculo del running time no da una expreción matemática que nos interese.
Las causas son:
• Los coeficientes de los términos no se conservan al cambiar la maquina ejecutora.
• Generalmente no se trabaja para tamaños de problema pequeños, por lo que los coeficientes de los términos no son importantes, tampoco los términos no dominantes.
• Para un tamaño de entrada suficientemente grande, es el que más repercute en el valor
final
El índice de crecimiento de las funciones nos indica quien converge al infinito de forma
más rápida, en otras palabras establece un orden relativo entre las funciones, mediante la
comparación de terminos dominantes.
El término dominante de la función, es el índice de crecimiento, los términos inferiores al
dominante se ignoran, la constante multiplicativa del termino dominante también se ignora.
Hacemos de cuenta que los términos inferiores valen cero y la constante multiplicativa del
término dominante vale uno.

3.3 Notación asintótica (eficiencia asintótica)
Recapitulando la matemática, teníamos algo llamado asíntotas, las cuales nos imponían un
limite horizontal o vertical en el plano cartesiano. Del cual nos acercábamos mucho pero
nunca lo tocábamos. Aquí la asíntota es una función, de esta manera logramos un estudio de
la eficiencia mediante asíntotas. Mejor asíntota, mejor certeza.
El siguiente gráfico fue copiado desde el libro de Cormen, porque ilustra como una función
g(n) trabaja como asíntota de la función f(n).
La notación-O (big o), sirve para dar una cota superior para el crecimiento de nuestro
algoritmo, esta afirma que hay un punto n0, tal que para los valores n después de este punto,
el valor múltiplo de la función g(n) supera o esta en el mismo orden que nuestro algoritmo
f(n), es decir que:
Existe un c y un n tal que 0 ≤ f(n) ≤ cg(n) para todo n0 ≤ n .
7
Y lo representamos como: f(n) = O(g(n)).
Matemáticamente podemos acotar f(n) con un orden muy superior, pero no hacemos eso,
porque queremos saber cuanto tardará nuestro algoritmo con el calculo más justo que podamos.
La notación-Ω (notación omega), sirve para dar una cota inferior para el crecimiento
de nuestro algoritmo, esta afirma que hay un punto n0, tal que para los valores n después de
este punto, el valor múltiplo de la función g(n) esta en un orden inferior o esta en el mismo
orden que nuestro algoritmo f(n), es decir que:
Existe un c y un n tal que 0 ≤ cg(n) ≤ f(n) para todo n0 ≤ n .
Y lo representamos como: f(n) = Ω(g(n)).
La notación-Θ (notación theta), sirve para dar una cota superior e inferior para el
crecimiento de nuestro algoritmo, esta afirma que hay un punto n0, tal que para los valores
n después de este punto, un valor múltiplo de la función g(n) esta en el mismo orden que
nuestro algoritmo f(n), es decir que:
Existe un c1 , c2 y un n tal que 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) para todo n0 ≤ n .
Y lo representamos como: f(n) = Θ(g(n)).
La notación o-chica, sirve para dar una cota estrictamente superior para el crecimiento
de nuestro algoritmo.
esta afirma que hay un punto n0, tal que para los valores n después de este punto, un
valor múltiplo de la función g(n) esta en un orden superior a nuestro algoritmo f(n), es decir
que:
Existe un c y un n tal que 0 ≤ f(n) < cg(n) para todo n0 ≤ n .
limn→∞
f(n)
g(n) = 0
Y lo representamos como: f(n) = o(g(n)).
La notación ω, sirve para dar una cota estrictamente inferior para el crecimiento de
nuestro algoritmo.
esta afirma que hay un punto n0, tal que para los valores n después de este punto, un
valor múltiplo de la función g(n) esta en un orden inferior a nuestro algoritmo f(n), es decir
que:
Existe un c y un n tal que 0 ≤ cg(n) < f(n) para todo n0 ≤ n .
limn→∞
f(n)
g(n) = ∞
Y lo representamos como: f(n) = ω(g(n)).
Aclaración de notación: En notación O, el igual ’=’ se debe leer como ’ES’. T(n) =
O(F(n))0
se debe leer como T(n)esO(F(n)).
3.4 ejemplo de notación asintótica
El algoritmo insertion-sort crece T(n) = n
2
, para ordenar n elementos hace n
2 operaciones.
El algoritmo merge-sort crece T(n) = nlog(n), para ordenar n elementos hace nlog(n)
operaciones.
Esto significa que para n pequeños combine insertion-sort pero para casos grandes es
mejor merge-sort.
Si n=1000, insertion-sort hace 1 millon de pasos, y mere-sort 3 mil.
Tenemos 2 computadoras:
• A (la rápida) 10 billones instrucciones
segundo .
• B (la lenta) mil millones instrucciones
segundo .
A, esta ordenando un arreglo de 10 millones de números mediante insertion-sort. Con el
mejor programador del mundo , por lo que implementa al algoritmo insertion-sort con un
running time T(n) = 2n
2
. B, esta ordenando un arreglo de 10 millones de números mediante
merge-sort. Con pepe, que aprendió ayer a programar con un compilador que esta seteado
para no optimizar, por lo que lo implementa mere-sort con dificultad con un running time
T(n) = 50nlog(n).
¿Quien ganara? A es 1000 veces más rapida que B, en poder de computo. A tiene mejor
programador que B.
Pero el ganador es B:
8
A tarda: 2(107
)
2
10billones = 20segundos.
B tarda: 50(107
) log 107
milmillones = 11.62674 segundos.

Vaya sorpresa la que me encontré ._.