complejidad de algoritmos

UNIDAD I
ANÁLISIS DE ALGORITMOS
1.1. Conceptos de complejidad de algoritmos
Cuando se analiza y compara el desempeño de diferentes algoritmos, se presta una especial atención al
tiempo de corridadel algoritmo. El tiempo de corrida de un algoritmo, se entiende como el tiempo
que le toma al algoritmo calcular el resultado a partir de los datos de entrada.
¿Por qué es importante el tiempo decorrida de un algoritmo?
Porque si conocemos o al menos tenemos una idea del tiempo de corrida de un algoritmo podemos
saber que tanto va a tardar en entregarnos la respuesta, y podemos decidir, sila esperamos, nos vamos a
tomar un café o si mejor regresamos después de una semana.
Aunque las computadoras de hoy en día son muy rápidas comparadas con sus similares de hace
algunos años, y soncapaces de llevar a cabo millones de operaciones en un segundo, resulta fácil
encontrar ejemplos de problemas y soluciones que tardarían años en solucionarse.
Cuando se analiza el tiempo de corridade un algoritmo, más que el tiempo exacto que tardará el
algoritmo en milisegundos, lo que importa es la función de crecimiento del algoritmo, la función de
crecimiento de un algoritmo, nos da unaidea de que tanto aumentará el tiempo de corrida según
aumente el tamaño de la entrada. Por lo general, la función de crecimiento de un algoritmo se expresa
como la multiplicación de una constante yuna función que depende del tamaño de la entrada, es decir,
c f(n) donde n es el tamaño de la entrada.
Tomemos por ejemplo el problema de ordenar una lista de números. Se tiene un conjunto de númerosA{x1, x2, ... , xn} un algoritmo de ordenación debe entregar como salida una permutación del conjunto
A tal que xi 100.
Si nuestro problema no va a tratar jamás problemas de tamaño mayor que 100,es mejor solución
usar el algoritmo "g".

El ejemplo anterior muestra que las constantes que aparecen en las fórmulas para T(n), y que
desaparecen al calcular las funciones de complejidad,...