Aunque puede haber muchos parámetros. Ocurre con frecuencia que ambos parámetros están fijados por otras razones y se plantea la pregunta inversa: ¿cuál es el tamaño del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En lo que sigue nos centraremos casi siempre en el parámetro tiempo de ejecución.

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

Para cada problema determinaremos una medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N. Así, para un vector se suele utilizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es más importante considerar el número de arcos, dependiendo del tipo de problema a resolver); en un fichero se suele usar el número de registros, etc.

7.1 Análisis del algoritmo

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega y theta se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado está relacionada por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden suponer

que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso esté acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000 dígitos).

7.2 Complejidad en el tiempo

Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). 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 cada instrucció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. Esto hace que más 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 del código generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta. Dado que es fácil cambiar de compilador y que la potencia de los ordenadores crece a un ritmo vertiginoso (en la actualidad, se duplica anualmente), intentaremos analizar los algoritmos con algún nivel de

independencia de estos factores; es decir, buscaremos estimaciones generales ampliamente válidas.

La complejidad en cuanto al tiempo de un programa es la cantidad de tiempo que se ejecuta. La evaluación del tiempo de computación resulta más importante que la del espacio de almacenamiento. Este tiempo no es posible expresarlo en segundos, pues entonces dependería de la maquina en la que estuviera siendo ejecutado, es necesario considerar la maquina donde se ejecuta un algoritmo o el lenguaje en el que se implementa los tiempos de ejecución no difieren más que en una constante multiplicativa.

El enfoque matemático considera el consumo de tiempo por parte el algoritmo como una función del total de sus datos o ejemplar de los mismos. Por consiguientes, se definirá el tamaño de un ejemplar como el número de unidades lógicas necesarias para presentarles en el ordenador, pudiéndose, en último extremo, llegar a considerar estas como dígitos binarios. En este sentido, a medida que crece el tamaño de un ejemplar de un problema, generalmente crece el tiempo de ejecución.

Observando como varia el tiempo de ejecución con el tamaño de la entrada, se puede determinar la tasa de crecimiento del programa de algoritmo, expresado normalmente en términos de n, donde n es una medida de tamaño del ejemplar de entrada. Por tanto, en la evaluación de un algoritmo es importante considerar que el tiempo que tarda un programa en ejecutarse depende del número de datos y determinar el algoritmo más eficiente cuando haya que procesar un número elevado.

Hay que tener en cuenta que el tiempo de ejecución puede depender también la entrada específica, por ejemplo, al ordenar un lista de tiempo empleando en ello puede dependerse del numero elementos de la lista (burbuja), pero a veces puede variar con el orden en el que se encuentra los elementos de una lista y según este se podrá tardar más o menos en ordenarla (inserción).

Considerando todas las reflexiones anteriores, si t(n) es el tiempo de ejecución de un programa con entrada de tamaño n, será posible valorar t(n) como el número de sentencias, en nuestro caso en pascal, ejecutadas por el programa. Y la evaluación se podrá efectuar desde diferente punto de vistas.

• Peor caso: se puede hablar de t(n) como el tiempo para el peor caso. Indica el tiempo peor que podemos tener, este análisis es perfectamente adecuado para algoritmos cuyo tiempo de respuestas sea crítico.

• Mejor caso: se hablar de t(n) como el tiempo para el mejor caso. Indica el tiempo mejor que podemos tener.

• Caso medio: se puede computar t(n) como el tiempo medio de todos los casos posibles. En teoría es mejor el tiempo medio, para su evaluación se hace general complica mucho el tema. El

estudio del tiempo medio es muy útil en algoritmos cuyo tiempo de respuestas no sea crítico y sea usado frecuentemente.

7.3 Complejidad en el espacio

Es la memoria que utiliza un programa para su ejecución; es decir el espacio de memoria que ocupan todas las variables propias del algoritmo.

Esta se divide en Memoria Estática y Memoria Dinámica.

Memoria estática. Para calcularla se suma de memoria que ocupan las variables declaradas en el algoritmo.

Memoria dinámica. Su cálculo no es tan simple ya que depende de cada ejecución del algoritmo

La misma idea que se utiliza para medir la complejidad en tiempo de un algoritmo se utiliza para medir su complejidad en espacio. Decir que un programa es O( N ) en espacio significa que sus requerimientos de memoria aumentan proporcionalmente con el tamaño del problema. Esto es, si el problema se duplica, se necesita el doble de memoria. Del mismo modo, para un programa de complejidad O( N2 ) en espacio, la cantidad de memoria que se necesita para almacenar los datos crece con el cuadrado del tamaño del problema: si el problema se duplica, se requiere cuatro veces más memoria. En general, el cálculo de la complejidad en espacio de un algoritmo es un proceso sencillo que se realiza mediante el estudio de las estructuras de datos y su relación con el tamaño del problema.

El problema de eficiencia de un programa se puede plantear como un compromiso entre el tiempo y el espacio utilizados. En general, al aumentar el espacio utilizado para almacenar la información, se puede conseguir un mejor desempeño, y, entre más compactas sean las estructuras de datos, menos veloces resultan los algoritmos. Lo mismo sucede con el tipo de estructura de datos que utilice un programa, puesto que cada una de ellas lleva implícitas unas limitaciones de eficiencia para sus operaciones básicas de administración. Por eso, la etapa de diseño es tan importante dentro del proceso de construcción de software, ya que va a determinar en muchos aspectos la calidad del producto obtenido

7.4 Eficiencia de los algoritmos

1. Noción de complejidad

Complejidad temporal, tamaño del problema y paso

2. Cotas de complejidad

Cota superior, inferior y promedio

3. Notación asintótica

?, O, T

4. Obtención de cotas de complejidad

1. Noción de complejidad

Cálculo de complejidad: determinación de dos parámetros o

Funciones de coste:

Complejidad espacial : Cantidad de recursos espaciales ( de almacén) que un algoritmo consume o necesita para su ejecución Complejidad temporal : Cantidad de tiempo que un algoritmo necesita para su ejecución

Posibilidad de hacer

Valoraciones

El algoritmo es: “bueno”, “el mejor”, “prohibitivo”

Comparaciones

El algoritmo A es mejor que el B

Factores de complejidad temporal:

Externos

La máquina en la que se va a ejecutar

El compilador: variables y modelo de memoria

La experiencia del programador

Internos

El número de instrucciones asociadas al algoritmo

Complejidad temporal : Tiempo(A) = C + f (T)

C es la contribución de los factores externos (constante)

f(T) es una función que depende de T (talla o tamaño del problema).

Sólo nos ocuparemos de la complejidad temporal. Normalmente son objetivos contrapuestos. (complejidad temporal <--> complejidad espacial)

Cálculo de la complejidad temporal:

a priori: contando pasos

a posteriori: generando instancias para distintos valores y cronometrando el tiempo. Se trata de obtener la función. Las unidades de medida (paso, sg, msg, ...) no son relevantes (todo se traduce a un cambio de escala) El nº de pasos que se ejecutan siempre es función del tamaño (o talla)

del problema.

COTAS DE COMPLEJIDAD.

Dado un vector X de n números naturales y dado un número

natural z:

encontrar el índice i : Xi = z

Calcular el número de pasos que realiza.

Cuando aparecen diferentes casos para una misma talla

genérica n, se introducen las cotas de complejidad:

Caso peor: cota superior del algoritmo ? Cs(n)

Caso mejor: cota inferior del algoritmo? Ci(n)

Término medio: cota promedio ? Cm(n)

Todas son funciones del tamaño del problema (n)

La cota promedio es difícil de evaluar a priori

Es necesario conocer la distribución de la probabilidad de

Entrada. No es la media de la inferior y de la superior (ni están todas

ni tienen la misma proporción).

La cota promedio no la calcularemos. Sólo se hablará de complejidad por término medio cuando la cota superior y la inferior coinciden. El estudio de la complejidad se hace para tamaños grandes del problema por varios motivos:

Los resultados para tamaños pequeños o no son fiables o proporcionan poca información sobre el algoritmo Es lógico invertir tiempo en el desarrollo de un buen algoritmo sólo si se prevé que éste realizará un gran volumen de operaciones A la complejidad que resulta de tamaños grandes de problema se le denomina complejidad asintótica y la notación utilizada es la notación asintótica.

7.6 Notacion asintota

Notación matemática utilizada para representar la

complejidad espacial y temporal cuando n ? 8

Se definen tres tipos de notación:

Notación O (big-omicron) ? caso peor

Notación O (omega) ? caso mejor

Notación T (big-theta) ? caso promedio.

Obtención de cotas de complejidad

Etapas para obtener las cotas de complejidad:

1. Determinación de la talla o tamaño (de la instancia ) del

problema

2. Determinación del caso mejor y peor: instancias para las que

el algoritmo tarda más o menos

No siempre existe mejor y peor caso ya que existen algoritmos que se

comportan de igual forma para cualquier instancia del mismo tamaño

3. Obtención de las cotas para cada caso. Métodos:

cuenta de pasos relaciones de recurrencia (funciones recursivas).

Conclusion

Las estructuras de datos y algoritmos constituyen elementos básicos en el almacenamiento y tratamiento de información.

El conocimiento del concepto de algoritmos, sus representaciones y métodos que finalizan en el desarrollo de programas, constituyen un paso previo indispensable para introducirse en el ámbito de la programación.

Se deben conocer y manejar con gran facilidad los tipos de datos y las técnicas de creación, representación y refinamiento de algoritmos para la futura construcción de programas de calidad.

Para lograr compilar programas de mejor calidad y rendimiento, efectuando el programa una mayor cantidad de trabajo en una menor cantidad de tiempo y usando menos recursos, también para facilitar el acceso a estos programas y siendo más entendibles para el usuario.