Algoritmos

7.1 COMPLEJIDAD EN EL TIEMPO
El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N).
Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un sencillo código como:S1;for(x = 0; x < N; x++)S2;Demanda: T(N) = t1 + t2 * N Donde t1 es el tiempo que lleva ejecutar la serie S1 de sentencias, y t2 es el que lleva la serie S2. Habitualmente todos los algoritmos contienen alguna sentencia condicional o selectiva, haciendo que las sentencias ejecutadas dependan de la condición lógica, esto hace que aparezca más de un valor para T(N), es por ello que debemos hablar deun rango de valores. Cuando se habla del tiempo de ejecución de un algoritmo debe tenerse presente que el tiempo de ejecución exacto de un programa depende de varios factores:
1.- Los datos de entrada
2.- La calidad del condigo generado por el compilador
3.- La maquina donde se ejecuta el programa
4.- La complejidad del tiempo del algoritmo base del programa.
En el momento de diseñar y elegirentre posibles alternativas, sin embargo, los tres primero factores generalmente o no se conocían o nos vienen dados. Por lo tanto, el estudio de un algoritmo se centra en su complejidad de tiempo de ejecución. Mejorar su eficiencia generalmente implica reducir su complejidad de tiempo de ejecución. Cuando se estudia la complejidad de tiempo de ejecución de un algoritmo se define esta en funciónde los datos de entrada. El estudio sin embargo, depende del tamaño de los datos de entrada, no de los datos concretos. Por ejemplo, supongamos que se requiere estudiar un algoritmo de ordenación que, dada una lista de número, devuelva la misma lista ordenada ascendentemente. Así, si se quisiera ordenar la lista {2, 1, 3, 1, 5, 8}, se hablaría de una entrada de tamaño den=6.Denotemos, pues T(n)la función del tiempo de ejecución de un algoritmo con entrada de tamaño n. T(n) se expresa sin unidades, ya que el tiempo de ejecución exacto depende de muchos otros factores. T(n) representa el numero de operaciones elementales que realiza el algoritmo para obtener la solución. Se consideran operaciones elementales las asignaciones, comparaciones, operaciones aritméticas, etc.
Para tener unamedida del tiempo de ejecución de un programa, se debe pensar en los factores que tienen influencia en dicho valor.
Velocidad de procesamiento. El compilador utilizado (calidad del código generado). Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cadainstrucción. Así, un trozo sencillo de programa como:
S1; for (int i= 0; i < N; i++) S2; requiere T(N)= t1 + t2*N siendo t1 el tiempo que lleve ejecutar la serie “S1” de sentencias, y t2 el que lleve la serie “S2”. Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Estohace que mas que un valor T(N) debamos hablar de un rango de valores Tmin(N) ⇐ T(N) ⇐ Tmax(N) los extremos son habitualmente conocidos como “caso peor” y “caso mejor”.
Entre ambos se hallara algún “caso promedio” o más frecuente. Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes “Ti” que dependen de factores externos al algoritmo como pueden ser la calidad delcódigo generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta.

7.2 COMPLEJIDAD EN EL ESPACIO.

Es la memoria que utiliza un programa para su ejecución. Lo que implica que la eficiencia en memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo, es decir, el espacio memoria que ocupan todas las variables propias del...